宽度优先搜索不会返回节点的正确顺序

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]

我的问题是：

1. 为什么3在2之前被插入trav[]，即使在root.children中顺序是[2,3,4]
2. 为什么注释掉的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]

---

这是您的代码的“更干净”版本。我喜欢生成器，因此我将其转换为一个生成器，以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]