c++ - BST-插入说明

Question

我正在尝试学习二叉搜索树，我有一个与 BST 插入相关的疑问。这不是我的代码e 我从 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
  } 
} 

我的疑问 正如代码中提到的我不明白为什么根在插入(最后一行)时没有改变。为什么它是同一个根每次？

Answer 1

此代码中的递归调用不会影响根节点，因为您发送根节点第一次(此时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)

此处将创建新节点，返回时会将此节点分配给根节点的左侧，并将其上的指针返回给第一次调用

    2 
   / \
  1  10 
 /   /
-4   5

只是...我的建议是在学习 BST 之前先阅读有关递归函数的内容