Вставка 4 или 5 чисел в двоичное дерево, но получение только 3 чисел в выводе

Question

Это часть школьной лаборатории, занимающейся рекурсией и бинарным деревом. Если я введу 4 или 5 цифр и выведу результат, я получу только 3 цифры. Вот код для вставки:

Node *insert(Node *t, int key) {
    Node *insertParent;
    Node *result=NULL;

    if (t!=NULL) {
        result=search(t,key,insertParent);
    } else {
        t=new Node;
        t->data=key;
        t->leftchild=NULL;
        t->rightchild=NULL;
        return t;
    }

    if (result==NULL) {
        if (insertParent->data>key) {
            insertParent->leftchild=new Node;
            insertParent->leftchild->data=key;
            insertParent->leftchild->leftchild=NULL;
            insertParent->leftchild->rightchild=NULL;
            return insertParent->leftchild;
        } else if (insertParent->data<key) {
            insertParent->rightchild=new Node;
            insertParent->rightchild->data=key;
            insertParent->rightchild->leftchild=NULL;
            insertParent->rightchild->rightchild=NULL;
            return insertParent->rightchild;
        }
    } else
        return NULL;
}

Но я считаю, что проблема заключается в функции поиска, в частности указателя узла по родительскому элементу ссылки:

Node* search(Node *t, int key, Node *&parent) {
    if (t!=NULL) {
        parent=t;
        if (t->data==key)
            return t;
        else if (t->data>key)
            return search(t->leftchild,key,t);
        else 
            return search(t->rightchild,key,t);
    } else
        return NULL;
}

У меня есть функция, которая выводит дерево и проверила его по дереву, которое я построил вручную, и оно отлично работает:

void inorder(Node *t)
{
    if (t!=NULL) {
        if (t->leftchild!=NULL)
            inorder(t->leftchild);

        cout << t->data << ", ";

        if (t->rightchild!=NULL)
            inorder(t->rightchild);                     
    }  
}

Не ищу ответа, просто ищу область, на которую мне следует взглянуть.

Answer 1

Ваше подозрение верно. Проследите, как обновляется родительский параметр верхнего уровня, когда вы выполняете поиск более чем на одном узле.

Answer 2

Итак, я обнаружил, что моя проблема была с функцией поиска.Это было связано со ссылочной родительской переменной узла.Мне пришлось использовать четыре оператора else / ifelse, чтобы решить, какой путь идти, рекурсивно или нет.

Node* search(Node *t, int key, Node *&parent) {
    if (t!=NULL) {
        if (t->data==key) {
            parent=NULL;
            return t;
        } else if (t->data>key && t->leftchild!=NULL) {
            return search(t->leftchild,key,parent); // think this needs returned
        } else if (t->data>key && t->leftchild==NULL) {
            parent=t;
            return NULL;
        } else if (t->data<key && t->rightchild!=NULL) {
            return search(t->rightchild,key,parent); //think this needs returned
        } else if (t->data<key && t->rightchild==NULL) {
            parent=t;
            return NULL;
        }
    } else {
        parent=NULL;
        return NULL;
    }
}

Это изменение в функции поиска потребовало изменения в функции вставки:

Node *insert(Node *t, int key) {
    Node *insertParent=NULL;
    Node *result=NULL;

    if (t!=NULL) {
        result=search(t,key,insertParent);
    } else {
        t=new Node;
        t->data=key;
        t->leftchild=NULL;
        t->rightchild=NULL;
        return t;  
    }

    if (insertParent==NULL && result!=NULL) {
        return NULL;
    } else if (insertParent!=NULL && result==NULL) {
        //key not found need to add
        if (insertParent->data>key) {
            insertParent->leftchild=new Node;
            insertParent->leftchild->data=key;
            insertParent->leftchild->leftchild=NULL;
            insertParent->leftchild->rightchild=NULL;
            return insertParent->leftchild;
        } else {
            insertParent->rightchild=new Node;
            insertParent->rightchild->data=key;
            insertParent->rightchild->leftchild=NULL;
            insertParent->rightchild->rightchild=NULL;
            return insertParent->rightchild;
        }
    }
}

Спасибо всем, кто помог ...

(Также: я ответил на свой вопрос. Это то, что я должен сделать, или я должен отредактировать свой пост? Думаю, что людипредпочел бы увидеть весь процесс и не дать мне удалить старый нерабочий код ...)

Answer 3

Node* search(Node *t, int key, Node *&parent)
{
    if(t!=NULL)
    {
    parent=t;
    if (t->data==key)
        return t;

    else if (t->data>key)
        return search(t->leftchild, key, parent); // use “parent” because you want to assign parent to this variable

    else 
        return search(t->rightchild,key, parent);
    }
    else     return NULL;

}