这个 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())

我期望的return值是

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

但是，我得到的 return 值是

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

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

Answer 1

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

反转列表并弹出最后一个元素会导致队列非常混乱，您不觉得吗？您之后没有重新反转它，这就是为什么您会收到意外的订购更改。

您可以传递 pop 索引以删除特定项目：

node = queue.pop(0)

不过，从列表开头删除项目很慢。每次你这样做时，其他所有项目都必须移到左边的项目 space。我建议升级到专用的 queue 数据结构。

这个 BFS 实现是否正确？

Is this BFS implementation correct?

python

breadth-first-search