Как найти родителя заданного элемента в бинарном дереве?

Question

[ColdHandGuy]

Приветствую! Сейчас знакомлюсь с бинарными деревьями и необходимо найти родителя введённого элемента. Написал следующую рекурсивную функцию, но работать она не хочет. Подскажите, что я делаю не так?

struct node* searchParent(struct node* root, int x)
{
    if(root->left_child->data == x || root->right_child->data == x)
    {
        return root;
    }
    else
    {
        return searchParent(root->left_child, x);
        return searchParent(root->left_child, x);
    }
}

Сама структура:

struct node
{
    int data; //node will store an integer
    struct node *right_child; // right child
    struct node *left_child; // left child
};

Answer 1

[ColdHandGuy]

Оставлю решение для потенциальных следующих искателей:

struct node* searchParent(struct node* root, int x)
{
    if((root->left_child != NULL && root->left_child->data == x) || (root->right_child != NULL && root->right_child->data == x))
    {
        return root;
    }
    else
    {
        if(root->left_child != NULL && x < root->data)
        {
            return searchParent(root->left_child, x);
        }
        else
            if(root->right_child != NULL && x > root->data)
            {
                return searchParent(root->right_child, x);
            }
    
    }
}

Answer 2

[res2001]

Потому что в блоке else оба вызова идут с left_child.
А так же после первого вызова сразу будет возврат, т.к. вызовы находятся в операторе return.
И вам нужно сначала проверить, что указатели на потомков не nullptr.
На самом деле вам нужно ещё одно условие в блоке else:

If(root->data < x) return searchParent(root->left_child, x);
Else return searchParent(root->right_child, x);

Comments

[ColdHandGuy]

Работает только если искать потомки корня, а вот другие уже нет. Сделал вроде уже ближе к истине, но что не так не догоняю..
Усовершенствовал следующим образом:

struct node* searchParent(struct node* root, int x)
{
    if(root->left_child->data == x || root->right_child->data == x)
    {
        return root;
    }
    else
    {

        if(root->left_child->data < x)
            if(root->left_child != NULL)
                return searchParent(root->left_child, x);
        else
            if(root->right_child != NULL)
                return searchParent(root->right_child, x);

    }
}

[res2001]

ColdHandGuy, Проверку на NULL указателей на потомков надо делать до любого обращения по этим указателям, иначе эта проверка не имеет смысла. Напомню, если вы обратитесь по не действительному указателю или указателю содержащему NULL ваша программа будет аварийно остановлена.

if((root->left_child != NULL && root->left_child->data == x) || (root->right_child != NULL && root->right_child->data == x))
...
if(root->left_child != NULL && root->left_child->data < x)

Работает только если искать потомки корня

Если не считать не корректной проверки на NULL, то все остальное выглядит нормально, по идее должна искать и глубже.
Дерево у вас правильно сформировано? Перед поиском выведите дерево на экран. Можете сюда его выложить.

[ColdHandGuy]

res2001, спасибо, направили на верный ответ, проблема заключалась в том, что я шёл по левому/правому поддереву в случае если потомок проверяемого узла(root->left/right_child) меньше/больше X, а надо было сравнивать с текущим (root->data).