C++

Question

我有一个看起来像这样的二叉树

struct Node 
{
  int key;
  double data;
  Node* right;
  Node* left;
};

我有这个 "insert" 函数用于插入新节点和构建树

void insert(Node*& p, int key, double to_be_inserted) 
{
  if (p == nullptr) 
  {
    p = new Node;
    p->key = key;
    p->data = to_be_inserted;
    p->left = nullptr;
    p->right = nullptr;
  }
  else 
  {
    if (p->key == key) 
    {
      p->data = to_be_inserted;
    }
    else 
    {
      Node*& newChild = (p->key > key) ? p->left : p->right;
      insert(newChild, key, to_be_inserted);
    }
  }
}

和一个看起来像这样的主函数

int main(int argc, char ** argv) 
{
  Node* root = nullptr;
  insert(root, 11, 11);
  insert(root, 6, 6);
  insert(root, 4, 4);
  insert(root, 5, 5);
  insert(root, 8, 8);
  insert(root, 10, 10);
  insert(root, 19, 19);
  insert(root, 17, 17);
  insert(root, 43, 43);
  insert(root, 31, 31);
  insert(root, 49, 49);

  printTree(root, 0);
  return 0;
}

最终的 "printed-out" 树看起来像这样

（这个 "print-out" 应该是从左到右而不是从上到下阅读）

我不明白的是...insert 函数什么时候决定回溯（回到树上）并构建右子树？

例如，如果我们查看 main 中的 insert(root, 5, 5) 和 insert(root, 8, 8)，为什么 8 最终成为 node 6 的子节点而不是 node 5。根据 insert 函数的逻辑，它应该继续沿着树向下移动，使 8 成为 node 5 的子节点......对吧？

我需要帮助才能正确理解插入功能。我确信我误解了它的逻辑。

谢谢（对不起post）！

Answer 1

当您插入 8 时，三个看起来像这样（X 表示 NULL）：

insert(root, 11, 11);
insert(root, 6, 6);
insert(root, 4, 4);
insert(root, 5, 5);

        11
    6         X
 4    X    X     X
   5

现在，当您尝试插入 8（在这一行 Node*& newChild = (p->key > key) ? p->left : p->right; 时，您首先检查 11 > 8 是否为真，因此这一行告诉您您现在尝试在 11 的 left 子节点插入 8，而 11 的根节点恰好位于 6.

此时insert函数又重复了一遍，不过这次三者的根不是11而是6。 8 大于 6，因此它位于 6 的右侧。

所以这是插入8前后的情况。


        11                             11                
    6         X                    6         X           
 4    X    X     X   =====>     4    8    X     X        
   5                             5

顺便说一句，这个函数有回溯。这是一个简单的递归函数。

C++ - 无法理解二叉树递归函数（插入）

C++ - Having trouble understanding binary tree recursive function (insertion)

tree

insert

binary-tree

recursive-backtracking