插入二叉树（非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

回答

相关问题