这个BFS实现正确吗?

Question

我目前正在学习数据结构，我写了一个实现BFS的程序，我想如果有人能帮我检查一下。

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

class BST:
def __init__(self):
self.root = None
# Left out the insert function here
def BFS(self):
data = []
queue = []
node = self.root
queue.append(node)
while len(queue) != 0:
queue.reverse()
node = queue.pop()
data.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return data
# Tree
#      10
#    6    15
#   3 8    20
tree = BST()
tree.insert(10)
tree.insert(6)
tree.insert(15)
tree.insert(3)
tree.insert(8)
tree.insert(20)

print(tree.BFS())

我期望的返回值是

[10, 6, 15, 3, 8, 20]

但是，我得到的返回值是

[10, 6, 15, 8, 20, 3]

这仍然正确吗?因为我理解这一点的方式是每个节点值应该在每个级别上从左到右返回，所以我不确定我的实现是否正确。

Answer 1

queue.reverse()
node = queue.pop()

反转列表并弹出最后一个元素使队列变得相当杂乱，你不觉得吗?你没有在之后重新反转它，这就是为什么你会得到意想不到的顺序变化。

您可以向pop传递一个索引以删除特定项:

node = queue.pop(0)

从列表的开头删除项是缓慢的，但是。每次你这样做的时候，其他每一项都要往左移一个空格。我建议升级到专用队列数据结构。