Игорь Пашев - Поиск общего предка в двоичном дереве

Mar. 2nd, 2011

06:31 pm - Поиск общего предка в двоичном дереве

Previous Entry Add to Memories Tell A Friend Next Entry

Даны два элемента дерева, надо найти их ближайшего общего предка.

Решение такое. Начинаем с корня.
Если один слева, а другой справа — предок найден (корень).
Если слева никого — идём рекурсивно направо.
Если справа никого — идёи рекурсивно налево.

Если оба элемента на одной ветви, то этот алгоритм не работает.
Ну и фиг с ним, ибо тогда один из элементов является предком другого.


#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct _Leaf Leaf;
struct _Leaf {
    char *name;
    int value;
    Leaf *left;
    Leaf *right;
};

Leaf *insert(Leaf *root, Leaf *newl)
{
    int cmp;
    if (root == NULL)
        return newl;

    cmp = strcmp(newl->name, root->name);
    if (cmp == 0) {
        /* Dublicate */
        fprintf(stderr, "Dublicate: %d, %d\n", newl->value, root->value);
    }
    else if (cmp < 0) {
        root->left = insert(root->left, newl);
    }
    else /* cmp > 0 */ {
        root->right = insert(root->right, newl);
    }

    return root;
}

Leaf *lookup(Leaf *leaf, const char *name)
{
    int cmp;
    if (leaf == NULL)
        return NULL;

    cmp = strcmp(leaf->name, name);
    if (cmp == 0) {
        return leaf;
    }
    else if (cmp < 0) {
        return lookup(leaf->right, name);
    }
    else /* cmp > 0 */ {
        return lookup(leaf->left, name);
    }
}

void print_digraph(Leaf *root)
{
    if (root == NULL) return;
    if (root->left) {
        printf("\"%s\" -> \"%s\"\n", root->name, root->left->name);
        print_digraph(root->left);
    }
    if (root->right) {
        printf("\"%s\" -> \"%s\"\n", root->name, root->right->name);
        print_digraph(root->right);
    }
}

Leaf* find_parent (Leaf *root, const char *s1, const char *s2)
{
    if (root == NULL) return NULL;

    if (lookup(root->right, s1)) {
        fprintf(stderr, "Found %s on the right of %s.\n", s1, root->name);
        if (lookup(root->left, s2)) {
            fprintf(stderr, "Found %s on the left of %s.\n", s2, root->name);
            return root;
        }
        else
            return find_parent(root->right, s1, s2);
    }
    else if (lookup(root->right, s2)) {
        fprintf(stderr, "Found %s on the right of %s.\n", s2, root->name);
        if (lookup(root->left, s1)) {
            fprintf(stderr, "Found %s on the left of %s.\n", s1, root->name);
            return root;
        }
        else {
            fprintf(stderr, "Going to the right of %s.\n", root->name);
            return find_parent(root->right, s1, s2);
        }
    }
    else {
        fprintf(stderr, "Going to the left of %s.\n", root->name);
        return find_parent(root->left, s1, s2);
    }
}

int main (int argc, char *argv[])
{
    int i;
    Leaf *leaf, *root = NULL;

    /* Use last two for search */
    for (i = 1; i < argc-2; ++i) {
        leaf = malloc(sizeof(Leaf));
        leaf->name = strdup(argv[i]);
        leaf->value = i;
        root = insert(root, leaf);
    }

    printf("digraph {\n");
    print_digraph(root);
    printf("}\n");


    leaf = find_parent(root, argv[argc-1], argv[argc-2]);
    if (leaf != NULL)
        fprintf(stderr, "Common parent: %s = %d\n", leaf->name, leaf->value);

	return EXIT_SUCCESS;
}



Пример:
Альбом: Screenshots

# ./tree moon name lame bar foo lock stone tree heap block stock trace price   lock bar> 1.gv
Going to the left of moon.
Found lock on the right of lame.
Found bar on the left of lame.
Common parent: lame = 3

# ./tree moon name lame bar foo lock stone tree heap block stock trace price   lame bar> 1.gv
Going to the left of moon.
Going to the left of lame.
Going to the left of bar.

# ./tree moon name lame bar foo lock stone tree heap block stock trace price   lock stone> 1.gv
Found stone on the right of moon.
Found lock on the left of moon.
Common parent: moon = 1

# ./tree moon name lame bar foo lock stone tree heap block stock trace price   lock block> 1.gv
Going to the left of moon.
Found lock on the right of lame.
Found block on the left of lame.
Common parent: lame = 3

Tags: ,
(1 комментарий | Оставить комментарий)

Comments:

From:(Anonymous)
Date:November 11th, 2012 - 09:51 pm
(Link)
Только не говорите, что это убожество применялось где-либо в продакшене.
(Reply to this)