BST插入解释

Question

我试图学习二叉搜索树，我有一个与BST插入有关的疑问。 这不是我的鳕鱼Ë我采取这种从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

在此代码递归调用，不影响根节点，因为你在第一次发送根节点 （当时根是空的），并会进入if条件 否则不会影响根系考虑下面的树和呼叫

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

第一个电话将检查根== NULL ---这一点，如果假 将测试任何-4大于或小于2，将让左节点上递归调用

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

Answer 2

如果你有BST和要插入的流3，2，8，5，7，你会做如下：

3 

    3 
/
2 

    3 
/\ 
2 8 

    3 
/\ 
2 8 
/
    5 

    3 
/\ 
2 8 
/
    5 
    \ 
    7 

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