插入二叉树(非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。
好吧!所以,我希望这是你在找什么,但你的代码是非常好的,它只是需要一些变化:
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)。今后仍然有用!
感谢@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)
您可以先在您的问题中修复缩进吗?它有助于了解什么是实际错误,以及在SO上发布代码的工件。 – cosinepenguin
其实在代码中有很多错误......'n.left'和'n.right'在做什么?我不认为你曾经宣布过''''''。 – cosinepenguin
缩进是可以的我想。高清确实是在课外 –