插入二叉樹（非BST）Python

我試圖在我的二叉樹中插入一個節點。但是，我不知道這樣做的正確方法。我明白我應該運行一個bfs並插入第一個空位置。我如何將它翻譯成代碼？插入二叉樹（非BST）Python

我試圖與DFS：樹看起來是這樣的：

class Node: 
    def __init__(self, val): 
     self.val = val 
     self.left, self.right = None, None 
def insert(node, val): 
    if not node: 
      return Node(val) 
    if not node.left: 
      node.left = Node(val) 
      return 
    if not node.right: 
      node.right = Node(val) 
      return 
    return insert(node.left, val) 
    return insert(node.right, val) 

n1, n2, n3, n4, n5, n6, n7, n8 = Node(1), Node(2), Node(3), Node(4), Node(5), Node(6), Node(7), Node(8) 
n1.left, n1.right, n2.left, n2.right, n3.left, n3.right, n4.left = n2, n3, n4, n5, n6, n7, n8

但是，這給了我一個無法訪問的代碼。這樣做的正確方法是什麼？我非常沮喪的人叫Binary Tree他們真的意味着BST。

來源

2017-07-06 Hasan Iqbal Anik

您可以先在您的問題中修復縮進嗎？它有助於瞭解什麼是實際錯誤，以及在SO上發佈代碼的工件。 – cosinepenguin

其實在代碼中有很多錯誤......'n.left'和'n.right'在做什麼？我不認爲你曾經宣佈過''''''。 – cosinepenguin

縮進是可以的我想。高清確實是在課外 –

好吧！所以，我希望這是你在找什麼，但你的代碼是非常好的，它只是需要一些變化：

class Node: 
    def __init__(self, val): 
     self.val = val 
     self.left, self.right = None, None 

    def __str__(self): #This allows you to print out the nodes for testing, other "magic" methods can be created here too! 
     return str(self.val) 

def insert(node, val=None): 
    if not val: 
     return Node(node) #This will create a new node if val is None 
    if not node.left: 
      node.left = val 
      return 
    if not node.right: 
      node.right = val 
      return 
    return insert(node.left, val) 
    return insert(node.right, val) 


def main(): 
    n1 = insert(1) 
    n2 = insert(2) 
    n3 = insert(3) 
    n4 = insert(4) 
    n5 = insert(5) 
    n6 = insert(6) 
    n7 = insert(7) 
    n8 = insert(8) 

    insert(n1, n2) 
    insert(n1, n3) 
    insert(n2, n4) 
    insert(n2, n5) 
    insert(n3, n6) 
    insert(n3, n7) 
    insert(n4, n8) 

    print(n1.left) 
    print(n3.left) 

main()

這個工作對我的測試！我改變了insert()背後的邏輯，以便允許該功能創建新的節點（儘管我知道這不一定是你想要它做的，你可以改變它！）。儘管如此，還有很多其他方法可以實現，但這是我能想到的最接近真實代碼的方式。

希望它有幫助！

PS 另一個很好的資源是Interactive Python（授予章節是關於BSTs）。今後仍然有用！

來源

2017-07-06 21:27:06 cosinepenguin

感謝@cosinepenguin。但是讓我們說我已經有了二叉樹。現在我想在這裏插入一個節點在第一個空位置。所以我會運行一個bfs，如果我找到任何左側或右側的孩子爲空，我會將其插入那裏。那是我的問題。 –

是的，你是100％正確的，如果你想要它是平衡的，不關心值的順序插入應該是寬度優先的，所以我修改了一些代碼，但你說我說了什麼原本仍然是：

要做一個bfs遍歷，你必須使用另一個數據結構，一個隊列。隊列是先進先出，這意味着你最終要在每個級別訪問每個節點，然後再進入下一個節點。有趣的是，爲了使這個深度從頭到尾流行，而不是從頭開始模擬堆棧。

def insert(node, val): 
    """ 
    Always returns the root of the tree 
    """ 
    if not node: 
     return Node(val) 
    queue = [node] 
    while len(queue) > 0: 
     # n is the current node in the tree 
     n = queue.pop(0) 

     # if it has no children insert node 
     # start from the left 
     if not n.left: 
      n.left = Node(val) 
      return node 
     if not n.right: 
      n.right = Node(val) 
      return node 

     queue.append(n.left) 
     queue.append(n.right)

來源

2017-07-06 21:29:57

插入二叉樹（非BST）Python

回答

相關問題