BST-插入说明

Question

我正在尝试学习二叉搜索树，我对 BST 插入有一个疑问。这不是我的 code 我从 http://cslibrary.stanford.edu/110/BinaryTrees.html

struct node* insert(struct node* node, int data) { 
  // 1. If the tree is empty, return a new, single node 
  if (node == NULL) { 
    return(newNode(data)); 
  } 
  else { 
    // 2. Otherwise, recur down the tree 
    if (data <= node->data) node->left = insert(node->left, data); 
    else node->right = insert(node->right, data);

    return(node); // return the (unchanged) node pointer-->THIS LINE
  } 
}

我的疑问正如代码中提到的我不明白为什么root在插入时没有被改变（最后一行）.为什么每次都是同根？

Answer 1

如果你有一个 BST 并且想插入流 3, 2, 8, 5, 7 你会做如下：

如您所见，根永远不会改变。您插入的每个元素都会作为叶子添加到正确的位置。

Answer 2

此代码中的递归调用不会影响根节点，因为您发送了根节点第一次（此时root为NULL）会进入if条件否则不会影响 root 考虑以下树并调用

 2 --  (call insert and gave it root node, data -4)
   / \
  1   10
     /
    5

第一次调用将检查 root 是否 == NULL ---如果为假将测试大于或小于 2 的任何 -4，并将对左节点进行递归调用

    2 
   / \
  1-- 10  (call insert and gave it left child of root node, data -4)
     /
    5

并且此节点再次不为 NULL 将对根节点左侧的左侧进行花药递归调用此节点为 NULL

 2 
   / \
  1  10 
 /   /
NULL 5  (call insert and gave it left child of left child root node, data -4)

此处将创建新节点，并使用 returning 将此节点分配给根节点的左侧，并将其上的 return 指针指向第一次调用

刚刚... 我的建议是在学习 BST

之前阅读递归函数

BST-插入说明

BST-Insertion explaination

c++

recursion

binary-search-tree