python 中的广度优先搜索遍历

Question

我知道已经有一些关于此的问题，我已经仔细阅读了它们并尝试使用这些答案作为解决方案，但我仍然遇到问题。出于某种原因，我的广度搜索要么陷入无限循环，要么它说它不能从空列表中 dequeue。

这是代码

def enqueue(self, data):
    self.queue_list.append(data

def dequeue(self):
    return self.queue_list.pop(0)

def breadth(self):
    string = ""
    queue = q.Queue()
    root = self.root
    queue.enqueue(root.data)
    string += str(queue.dequeue())

    while queue != None:
        if root.left != None:
            queue.enqueue(root.left.data)
            root = root.left
        if root.right != None:
            queue.enqueue(root.right.data)
            root = root.right
        data = queue.dequeue()
        string += str(data)

    return string

Answer 1

您在 while 循环中的检查不应该是 queue != None。

您应该检查队列何时为空。永远不会是 None.

按照编码，你对一些东西进行排队然后将其出队，所以队列是空的，然后你进入 while 循环，因为虽然队列是空的，但它不是 None.

然后您尝试在 while 循环快结束时执行双端队列，这导致了您的错误。

Answer 2

您需要将节点推入队列而不仅仅是数据。否则你只能走树的右边（第二个 if 语句覆盖根）。
我不确定你的数据结构，所以只使用 collections.deque

from collections import deque

def breadth(self):
    string = ""
    q = deque([self.root])
    while q:
        node = q.popleft()
        string += str(node.data)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.left)
    return string

Answer 3

使用上述提示的最终解决方案

 def breadth_first(self):

    string = ""
    queue = q.Queue()
    root = self.root
    queue.enqueue(root)

    while len(queue.queue_list) > 0:
        node = queue.dequeue()
        string += str(node.data) + " "
        if node.left != None:
            queue.enqueue(node.left)
        if node.right != None:
            queue.enqueue(node.right)
    return string

python 中的广度优先搜索遍历

breadth first search traversal in python

python

tree

data-structures

python-3.x