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

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); returns 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

在某种程度上你是对的。您永远不能拥有高度 >2 的子树（不是树）。

在这段代码中，你永远不会有 root->right->right 因为，就代码而言，当你调用 root->left = insert(root->left, data);

（本地）根指针现在指向您刚刚插入的节点。（本地）根指向 root->left.

因此，你可以拥有任意高度的树（但是，本地根指针指向高度<2的子树）

Answer 2

请注意 insert() 总是 return 作为参数传递给它的 root 除非 root == NULL。因此，您插入的新节点无法进入"walk up the tree"。递归调用中发生的事情并不重要——你总是 return 与你在非 NULL 情况下传递的相同 root。

尽管有些人教授递归的方式，但我认为不尝试展开递归，而是考虑逻辑是否有意义，这有助于（无论如何对我的大脑）：

如果您传递了一个非 NULL 节点和 data < root->data，如果您这样做 root->left = insert(root->left, data) 并假设 insert() 神奇地 "just works"（即，它将 data 插入到左树中，并且 return 是该树的根）？

如果逻辑检查了左右两种情况，那么您将考虑基本情况：如果传递给您 NULL 节点，您是否会 return 正确的单元素树？

如果逻辑也检查了基本情况，那么您就知道您的代码一定是正确的，因为递归步骤是有意义的，并且您知道您将进入一个同样有意义的基本情况（因为您将当你沿着树走下去时，最终会到达一个 NULL 节点。

Answer 3

我认为您的困惑可能来自两个不同的来源。首先，将树注释到您的代码中是不可能的。其次是只有在函数传入空指针时才会创建新节点。只有小于 15 的值才能向左移动。它会是这样的（取决于添加顺序）：

当你去添加 25 时，结果如下：

我将尝试逐句通过代码对此进行解释。在第一次函数调用时将 25 添加到原始树时，第一个节点不是 NULL 并且 25 > 15 所以

else
{ 
    root->right = insert(root->right, data);
}

被调用。这递归调用相同的插入函数，但现在使用 20 节点作为比较。再次不为 null 且 25 > 20 因此如上所述在右节点上调用插入。这再次调用递归函数，但现在在 30. 25<30 上，因此它调用左节点上的函数。在这一点上，函数被传递到一个 NULL 指针中，因为那里什么都没有，一个新节点被创建并放置在这个地方。

Answer 4

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

这种说法是错误的：

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

一旦函数的迭代被 return 编辑，它就会从堆栈中移除，所以在这种情况下我们有 3 次调用，我将用你的数字代替指针值。

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

最后一个为空，因此它创建了带有 25 的节点，然后 return 将其发送到调用 insert(20->right,25) 并将 25 设置为 20->right 这样您就有了一棵树看起来像这样

/* consider following BST with their addresses[]:

              20 [200]
               \
                25 [300]  
*/

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

/* 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)

现在让我们看看 returns

insert(null,25) return一个有25的节点，然后从栈中移除

 return 25;

insert(20,25) 获取它的 return 节点的 25。它将其右子节点设置为 25，如下所示

 20->right = 25;
 return 20;

现在我们回到最初的 insert(15,25) 调用。它获得了 returned 20。它确实如此

15->right = 20;
return 15;

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

How binary search tree insertion works using recursion?

c

c++

algorithm

recursion

data-structures