c++ - 在二叉树中插入 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

您的猜测是正确的。一旦您深入搜索一个以上的节点，跟踪顶级“parent”参数是如何更新的。