樹插入

Question

interactivepython上的樹插入功能不正確嗎？

插入左：

def insertLeft(root,newBranch): 
    t = root.pop(1) 
    if len(t) > 1: 
     root.insert(1,[newBranch,t,[]]) 
    else: 
     root.insert(1,[newBranch, [], []]) 
    return root 

我發現邏輯是不正確的，插入導致破樹。

我嘗試了下面的代碼（你可以在同一頁面上運行代碼）並看到驗證。

r = BinaryTree(3) 
insertLeft(r,4) 
insertLeft(r,5) 
insertLeft(r, [10, [11, [],[]], []]) 
insertRight(r,6) 
insertRight(r,7) 
print(r) 

輸出：

[3, 
    [ 
     [10, [11, [], []], []], 
      [5, [4, [], []], []], 
      [] 
    ], 
    [ 
     7, 
      [], 
      [6, [], []] 
    ] 
] 

Answer 1

結果如預期由這些功能。以下內容：

insertLeft(r, [10, [11, [],[]], []]) 

...將值注入爲根的左子節點。將賦予該新節點的值是您作爲第二個參數提供的值。此函數始終創建一個一個新節點（三元組），並且您已將其賦予樹結構的值。

這在輸出中看起來很奇怪，看起來好像結構已損壞，但情況並非如此。值[10, [11, [],[]], []]就是這樣一個值 - 它並不參與構建主樹。

也許你想合併兩棵樹。但是在這種情況下，你應該決定在根節點的左邊的子樹上會發生什麼。舉例來說，你可以做這樣的事情：

insertLeft(r, 11) 
insertLeft(r, 10) 

...然後前面的子樹（[5, [4, [], []], []]）將成爲節點的孩子值11

總之，爲了合併子樹不能只傳遞一個子樹作爲參數insertLeft。該方法僅用於注入具有一個特定值的單個節點。