广度——第一次只遍历returns个节点

Question

我正在 python 学习广度优先遍历。我在编写这段代码时遇到了问题。 '''

from collections import deque
class Tree:
    def __init__(self,data):
        self.data = data
        self.right = None
        self.left = None
    def bft(root):
        list_nodes = []
        traversal_queue = deque([root])
        while len(traversal_queue)>0:
            node = traversal_queue.popleft()
            list_nodes.append(node.data)
            traversal_queue.append(node.left)
            traversal_queue.append(node.right)
            return list_nodes
n1 = Tree('A')
n2 = Tree('B')
n3 = Tree('C')
n4 = Tree('D')
n1.left = n2
n1.right = n3
n2.left = n4
print(Tree.bft(n1))

结果是

['A']

应该是['A','B','C','D']。我不知道为什么这段代码返回不正确的结果。你能帮帮我吗？

Answer 1

        while len(traversal_queue)>0:
            node = traversal_queue.popleft()
            list_nodes.append(node.data)
            traversal_queue.append(node.left)
            traversal_queue.append(node.right)
            return list_nodes

你在 while 循环中 returning list_nodes，这意味着它只会执行一次，因此 [=] 中只有一个值27=] list,to fix,move return list_nodes outside the while loop.

此外，您还没有检查是否将 None 插入队列（这将导致 AttributeError:'NoneType' Object has no Attribute 'data'）

最终 while 循环：

while len(traversal_queue)>0: 
     node = traversal_queue.popleft() 
     if node is None: 
         continue 
     list_nodes.append(node.data) 
     traversal_queue.append(node.left) 
     traversal_queue.append(node.right) 
return list_nodes

广度——第一次只遍历returns个节点

Breadth - first traversal only returns one node

python

breadth-first-search