二叉搜索樹

這是關於BST在維基百科上發現了一些代碼：二叉搜索樹

# 'node' refers to the parent-node in this case 
def search_binary_tree(node, key): 
    if node is None: 
     return None # key not found 
    if key < node.key: 
     return search_binary_tree(node.leftChild, key) 
    elif key > node.key: 
     return search_binary_tree(node.rightChild, key) 
    else: # key is equal to node key 
     return node.value # found key

現在，這裏的二叉樹：

如果我在尋找11，我按照算法那裏，我從10開始，我右轉到12，然後從左到9，然後到達樹的盡頭，但沒有發現11. 但是11存在於我的樹中，它只存在於另一側。

你能解釋一下二叉樹中這個算法在我的樹上工作的限制嗎？

謝謝。

來源

2010-09-07 Martin

這只是因爲你的樹不是二叉搜索樹：沒有正確排序。 BST按照算法中的描述進行構建。例如在你的樹中：節點'9'不在正確的位置，因爲它應該在你的根節點'10'的左邊。 '14'和'11'應該在右側分支上。

例如一個BST可能某事像這樣：

來源

2010-09-07 05:37:39 PierrOz

非常感謝PerrOz。這解釋了我沒有得到關於BST的部分:) – Martin 2010-09-07 05:44:18

不要在二叉樹和二叉搜索樹之間混淆。二叉搜索樹（簡稱BST）是一種特殊類型的二叉樹，其中左側的所有節點都小於或等於父節點，所有節點的右側都大於父節點。

鑑於你給出的例子只是一個二叉樹，而不是二叉搜索樹。您可以看到值11和14留給父節點10，這違反了BST屬性。查看二叉搜索樹here。

來源

2010-09-07 05:34:26 bragboy

你叫什麼父節點？如果左邊的所有節點都小於或等於祖先，而不是父權，那麼這會有意義嗎？我的意思是4而不是14。我固定了樹。 – Martin 2010-09-07 05:37:04

請參閱此鏈接瞭解所有的行話。 http://www.technicalypto.com/2010/01/binary-trees-in-java.html – bragboy 2010-09-07 05:38:21

您已將節點14和11放在錯誤的地方。從the Wikipedia article on BSTs：

節點的左子樹只包含鍵小於節點的關鍵節點。

節點的右子樹只包含密鑰大於節點密鑰的節點。

左右子樹也必須是二叉搜索樹。

正如你所看到的，14和11是大於8

來源

2010-09-07 05:35:16

14,11和9是錯誤的。 – 2010-09-07 05:37:46

你不是一個BST呈現的樹。 11和14從未插入到10的左側，這就是爲什麼算法不在那裏搜索。 9也不合適。根據維基百科

插入：

插入開始作爲搜索將開始;如果根不等於這個值，我們像以前一樣搜索左邊或右邊的子樹。最終，我們將到達一個外部節點，並根據節點的值將值添加爲其右側或左側的子節點。換句話說，我們檢查根，如果新值小於根，則遞歸插入新節點到左側子樹，如果新值大於或等於根，則遞歸插入新子節點。

你可以告訴大家一個二叉樹是BST，如果它具有這些屬性（也來自維基百科）：

節點的左子樹只包含鍵節點小於節點鍵。

節點的右側子樹只包含密鑰大於節點密鑰的節點。

左右子樹也必須是二叉搜索樹。

來源

2010-09-07 05:35:22

你的樹不是二叉搜索樹

來源

2010-09-07 05:58:51 Hiber

回答

相關問題