c++ - 二叉搜索树插入如何使用递归工作？

Question

我在理解二叉搜索树插入的递归部分时遇到一些问题。

bstnode* insert(bstnode* root,int data)
{
    if(root==NULL){
        bstnode* tmp= new bstnode();
        tmp->data=data;
        tmp->left=tmp->right=NULL;
        return tmp;
    }

    if(data<root->data)     
        root->left = insert(root->left, data); 
    else 
        root->right = insert(root->right, data); //can't understand the logic here
    return root; 
}

/* consider following BST with their addresses[]:
              15 [100]
             /  \
           10    20 [200]
                   \
                   tmp [300]  
*/

据我所知root->right = insert(root->right, data);应将新创建节点的地址存储在 root->right 中所以此代码不适用于高度> 2 的树。
然而，它对任何数量的节点都能完美地工作。
我一定在这里遗漏了一些关键细节。

假设我想在 BST 中插入 25 即 insert(root,25);
as 25>15:-

我在这里分解递归部分:
root->right = insert(root->right, 25);
或 15->right = insert(15->right,25);在这里，再次递归调用它，因为 25>20
insert(root->right, 25) => root->right->right = insert(root->right->right, 25);
或 insert(15->right, 25) => 20->right = insert(20->right, 25);

insert(20->right,25)是NULL所以一个新节点 tmp已创建。
insert(20->right,25);返回 tmp .

现在展开递归。

//20->right = insert(20->right, 25);

所以，

20->right= 300(临时地址)；

//insert(15->right, 25) => 20->right
//and 15->right = insert(15->right,25);

15->right = 20->next;
因此15->right = [300] 地址。
或者 root->right = [300] 地址。
我的方法有什么问题？

再次概述递归调用:

15->right = insert(15->right,25);
15->right = [20->right = insert(20->right,25)]; //20->right is NULL so creating new node
15->right = [20->right=   300 address of tmp];
15->right = [20->right or 300]
15->right = [300] // but in reality 15->right = [200]

Answer 1

您忘记了 root->right 是您作为 root 传递给函数的地址的 root->right。根据您遍历的方式，每次调用 insert 都会在 root->right 或 root->left 中传递。

这个说法是错误的:

root->right = root->right->right = tmp;

一旦返回函数的迭代，它就会从堆栈中移除，所以在这种情况下我们有 3 次调用，我将把你的数字放在指针值的位置。

insert(15->right,25)
insert(20->right,25) 

最后一个为 null，因此它创建了带有 25 的节点并将其返回给调用 insert(20->right,25) 并将 25 设置为 20->right 这样您就有了一个看起来像这样的树

/* consider following BST with their addresses[]:

              20 [200]
               \
                25 [300]  
*/

然后它将这棵树返回到调用 insert(15->right,25) 并将该树设置为我们刚刚返回的树，这样我们就得到了最终的树

/* consider following BST with their addresses[]:
          15 [100]
         /  \
       30    20 [200]
               \
                25 [300]  
*/

编辑:让我看看是否可以澄清。让我们再看看你的树

/* consider following BST with their addresses[]:
          15 [100]
         /  \
       10    20 [200]
               \
               tmp [300]  
*/

我们想插入 25 所以我们调用(我将再次使用树的那个节点处的值来表示我们传递的指针) 插入(15, 25)

然后调用 root->right 上的 insert，恰好是 20

insert(20, 25)

这会在右节点 20 上再次调用插入，该节点恰好为 null

insert(null,25)

现在让我们看看返回

insert(null,25) 返回一个包含 25 的节点，然后从栈中移除

 return 25;

insert(20,25) 返回一个值为 25 的节点。它将其右子节点设置为 25，如下所示

 20->right = 25;
 return 20;

现在我们回到最初的 insert(15,25) 调用。它被返回 20. 所以它确实如此

15->right = 20;
return 15;