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 

正如你所看到的根永遠不會改變。插入的每個元素都會作爲葉子添加到正確的位置。