Даны два элемента дерева, надо найти их ближайшего общего предка.
Решение такое. Начинаем с корня.
Если один слева, а другой справа — предок найден (корень).
Если слева никого — идём рекурсивно направо.
Если справа никого — идёи рекурсивно налево.
Если оба элемента на одной ветви, то этот алгоритм не работает.
Ну и фиг с ним, ибо тогда один из элементов является предком другого.
#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