插入到二叉搜索樹

所以我必須將一個節點插入二叉搜索樹。在我的入門級課程中，二叉搜索樹被表示爲鏈接列表，如下圖所示的這個二叉樹的 [4, [5, [0, [],[]], [2, [], []]], [1, [],[]]]：插入到二叉搜索樹

this binary tree 。

（這不是一個二叉搜索樹，只是一張二叉樹，我有一張照片）。

所以插入一個節點到一棵樹，我寫了下面的遞歸代碼：

def tree_node(key): 
    return [key, [],[]] 

def insert(bst,key): 
    if bst == []: 
     return tree_node(key) 
    if key < bst[0]: 
     return insert(bst[1],key) 
    else: 
     return insert(bst[2],key) 
    return bst

這只是返回雖然節點，而不是新的樹節點

例如：

>>> insert([2, [1, [], []], [3, [], []]], 6) 
[6, [], []]

當它應該是：

>>> insert([2, [1, [], []], [3, [], []]], 6) 
[2, [1, [], []], [3, [], [6, [], []]]]

謝謝！

來源

2016-02-29 Samrose Ahmed

你永遠不會將節點插入你的樹中。看看你的基本情況 - 而不是將節點插入它應該是的，你只是簡單地返回節點。 –

您需要更改基本情況。而不是返回新list，你需要修改你在獲得通過的空單切片賦值可能是最簡單的：

def insert(bst,key): 
    if bst == []: 
     bst[:] = tree_node(key) 
    elif key < bst[0]: 
     insert(bst[1],key) 
    else: 
     insert(bst[2],key)

因爲這個函數修改樹的地方，我不回來了。如果你想這樣做，只需在最後重新添加return bst（但不是在遞歸步驟中，我們希望忽略那些返回值）。

來源

2016-02-29 02:51:03 Blckknght

只是爲了向Samrose澄清，因爲他似乎是Python的新手 - 因爲值是通過引用傳遞的，所以'bst [：] = x'本質上是指在'bst'引用的列表中從頭到尾替換值，並且在x中找到的值。因此，在這種情況下，遞歸函數在bst中找到葉節點，並用'tree_node'生成的新tree_node替換找到的空葉節點。 –

我會糾正它將用新節點的內容替換列表的*內容*（它是空的，所以它實際上不會刪除任何內容）。它不會重新綁定任何變量名稱。 – Blckknght

是的，這正是我想要得到的，很好的澄清。 –

變化return insert(bst[1],key)與bst[1] = insert(bst[1],key)（和類似的bst[2]）;這樣你實際上插入了一些東西，並且會執行最後的return聲明。

來源

2016-02-29 02:52:02

插入到二叉搜索樹

回答

相關問題