如何使用递归来实现二叉搜索树的插入？

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);
由于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]

- GorvGoyl

---

“root->right = root->right->right = tmp;” - 第一个“root->right =”从哪里来的？它似乎突然出现了... - user253751

它来自条件25>15。 - GorvGoyl

错误... insert(root->right, 25) 返回什么？ - user253751

这是一个递归函数，在达到基本情况后，它返回一个新节点，该节点设置为root->right->right，然后再次展开到root->right。 - GorvGoyl

我更新了我的回答，请看看底部是否有意义。 - Steve

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，所以我们调用（再次使用该节点处的值来表示我们传递的指针）
insert(15, 25)

然后在root->right上调用insert，它恰好是20。

insert(20, 25)

这句话的意思是在右侧节点20上再次执行插入操作，而该节点目前为空。

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; 

- Steve

---

然后它将返回此“TREE”给调用insert(15->right,25)，不是的，首先20-> right 存储了insert(25->right,25)的地址，然后root-> right 存储了20-> right的地址，即300。 - GorvGoyl

抱歉，应该是返回子树根节点的指针。 - Steve

哦，是的...没错...返回值是来自最后一个语句“return root;”，这就是为什么它返回root而不是root->right。我怎么可能没有注意到呢...终于明白了。 - GorvGoyl

没错，就是这样。我很高兴能以一种你能看懂的方式表达出来。 - Steve

Answer 2

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

   15
  /  \
     20
    /  \
       30

当您将25添加到此处时，结果如下：

   15
  /  \
     20
    /  \
        30
       /
      25

我会尝试逐步解释这段代码。在第一个函数调用中，将25添加到原始树上时，第一个节点不为NULL且25>15，因此

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

被称为。这会递归调用相同的插入函数，但现在使用20节点作为比较对象。再次不是空的且25> 20，因此像上面一样在右节点上调用插入。这会再次调用递归函数，但现在是在30上。25<30，因此它在左节点上调用该函数。此时，该函数已经传递了一个空指针，因为那里没有任何东西，并且创建了一个新节点并放置在这个位置。

- joeba

---

30 是一个打字错误..我已经更正了。"所有函数都将这个新创建的节点返回到原始函数调用。" 如何实现？你能举个例子吗？ - GorvGoyl

它不会直接返回到原始调用处。您必须在每次插入的迭代的堆栈中向下工作。它将指针返回到更大的子树，直到返回到原始调用处。 - Steve

当然。回想起来，我的措辞有点不清楚，经过进一步检查发现并不正确，我会编辑以删除它。实际上，返回值只是用于在正确位置创建节点时将其设置为正确的左侧或右侧。 - joeba

Answer 3

从某种意义上来说，你是正确的。你永远不可能有一个高度>2的子树（而不是树）。

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

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

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

- Imraaz Rally

Answer 4

请注意，insert()总是返回作为参数传递给它的root，除非root == NULL。因此，您无法让您插入的新节点“向上走树”。递归调用中发生的情况并不重要--在非NULL情况下，您始终返回相同的root。

尽管有些人教递归的方式不同，但我认为（至少对我来说）不要试图展开递归，而是考虑逻辑是否合理：

如果您传递了一个非NULL节点和data < root->data，如果您执行root->left = insert(root->left, data)并假设insert()神奇地“正常工作”（即将data插入到左侧树中并返回该树的根），那么您是否会得到正确的结果？

如果左右两种情况的逻辑都检查通过，则考虑基本情况：如果您传递了一个NULL节点，您是否会返回正确的单元素树？

如果基本情况的逻辑也检查通过，那么你就知道你的代码一定是正确的，因为递归步骤是有意义的，而且你知道你最终会到达一个也是有意义的基本情况（因为当你沿着树向下走时，最终会到达一个NULL节点）。

- Ulfalizer

---

在递归调用中发生的事情并不重要 - 您始终返回相同的根节点。但是，如果我使用insert（root->right，data）而不是root->right = insert（root->right，data），则函数无法正常工作。 - GorvGoyl

如果这有点模糊，可以考虑以下情况：如果基本情况是正确的，那么您就知道该算法将适用于高度为1的树。对于高度为2的树，您知道递归情况是正确的，因此它也必须有效（因为递归调用会使您进入基本情况）。对于高度为3的树，您知道高度为2的树是有效的。由于递归情况是正确的，这意味着高度为3的树也将有效。您可以一直这样下去，因此无论高度如何，该算法都必须适用于所有树。 - Ulfalizer

你的理论方法听起来不错，但我更关心实际实现和掌握真正的逻辑，而不是一些假设。 - GorvGoyl

@JerryGoyal：这就是递归背后的真正逻辑。一旦你达到了一千层递归，你就无法再在脑海中完全展开代码，所以你将不得不使用类似上面的推理。一旦你掌握了递归思维的要领，你也可以开始看到事物将如何执行。 - Ulfalizer

在编写算法时，这只是一种“假设”。一旦你组合好了递归情况（假设函数在此期间已经正确），以及基本情况，你就知道算法本身将是正确的（前提是在假设下没有任何错误），因此在那一点上它不再是一种假设。 - Ulfalizer