Блог

У меня есть код для поиска узла в двоичном дереве. Как я могу найти родительский узел узла, который KEY указан в качестве аргумента?

Вот код для обычного поиска двоичного дерева —

 struct Tree* search(struct Tree *root, int KEY)
{
    struct Tree *temp;
    if(root == NULL) return NULL; //Base condition
    else
    {
        if(root-> data == KEY) return root;
        else
        {
            temp = search(root-> Lchild, KEY);
            if(temp != NULL) return temp;
            else return(search(root-> Rchild, KEY));
        }
    }
    return NULL;
}
  

Вы возвращаете адрес Tree узла, значение которого совпадает с KEY , а не с родительским. Предполагая, что все значения узла различны в этом дереве, вы должны следовать приведенному ниже коду, чтобы вернуть Tree адрес родительского узла, если его дочернее значение узла (левого или правого дочернего узла) совпадает с KEY .

 struct Tree* search(struct Tree *root, int KEY){
    if(root == NULL){
        return NULL;
    }
    if(root->Lchild != NULL amp;amp; root->Lchild->data == KEY){
        return root;
    }
    if(root->Rchild != NULL amp;amp; root->Rchild->data == KEY){
        return root;
    }
    struct Tree *left = search(root->Lchild, KEY);
    struct Tree *right = search(root->Rchild, KEY);
    if(left != NULL){
        return left;
    }else if(right != NULL){
        return right;
    }
    return NULL;
}