广度优先搜索没有 return 节点的正确排序

Question

我已经实现了一个看起来像这样的树：

               1

    2          3          4

 5     6               7      8

我想按广度打印。这是我的代码：

class Node:
    def __init__(self):
        self.data = None
        self.children = []


class Tree:
    def __init__(self):
        self.root = Node()

    def build(self):
        self.root.data = 1
        self.root.children.append(Node())
        self.root.children.append(Node())
        self.root.children.append(Node())
        self.root.children[0].data = 2
        self.root.children[1].data = 3
        self.root.children[2].data = 4

        self.root.children[0].children.append(Node())
        self.root.children[0].children.append(Node())

        self.root.children[2].children.append(Node())
        self.root.children[2].children.append(Node())

        self.root.children[0].children[0].data = 5
        self.root.children[0].children[1].data = 6

        self.root.children[2].children[0].data = 7
        self.root.children[2].children[1].data = 8
        return


    def traverseBF(self, node):
        li = []
        trav = []
        li.append(node)
        while len(li) != 0:
            for x in li:
                trav.append(x.data)
                for z in x.children:
                    li.append(z)
                # map(lambda z: li.append(z), x.children)
                li.remove(x)
        print(trav)



t = Tree()
t.build()
t.traverseBF(t.root)

输出为：[1, 3, 2, 5, 4, 7, 6, 8]

我的问题是：

为什么 3 在 2 之前插入 trav[]，即使在 root.children 中顺序是 [2,3,4]
为什么注释掉的 map 函数给出的结果与上面的 for 循环不一样？

Answer 1

问题在于您如何管理队列。使用单个 while 循环来检查列表的长度。在 while 内，弹出第一个节点，然后用弹出节点的子节点扩展队列。您的函数应如下所示：

def traverseBF(self, node):
    li = []
    trav = []
    li.append(node)
    while len(li) != 0:
        x = li.pop(0)          # pop the first item
        li.extend(x.children)  # extend the queue with children
        trav.append(x.data)
    print(trav)

这样，t.traverseBF(t.root) 打印出 [1, 2, 3, 4, 5, 6, 7, 8]。

这是您的代码的“更简洁”版本。我喜欢生成器，所以我把它变成了一个生成器，returns BFS 中的节点值一一排序：

def bfs(node):
    q = [node]
    while q:
        n = q.pop(0)
        q.extend(n.children)
        yield n.data

[*bfs(t.root)]
# [1, 2, 3, 4, 5, 6, 7, 8]

广度优先搜索没有 return 节点的正确排序

Breadth First Search does not return the correct ordering for nodes

python

list

tree

traversal