获取迭代器以使用深度优先遍历二叉树

Question

我想使用 for 循环对二叉树进行深度优先遍历，并在每一步执行计算。

假设你有一棵 4 层的树：

       root
       /  \
      /    \
     /      \
    xx       xx
   /  \     /  \
  /    \   /    \
xx    xx   xx    xx
/ \   / \  / \   / \
x  x x   x x  x  x  x

如果将“深度优先探索树的步骤”放在列表中，它将如下所示：

[
[1],
[1,1], 
[1,1,1],
[1,1,0],
[1,0],
[1,0,1],
[1,0,0],
[0], 
[0,1],
[0,1,0], 
[0,1,1],
[0,0],
[0,0,1]
[0,0,0] 
]

是否有给定二叉树级别的函数 returns 列表中的“树探索步骤”？

我的第一个想法是使用 itertools.permutation 库，但它没有给你正确的顺序。

我也试过使用：

l = [False, True]
list(itertools.product(l, repeat=3))

关闭，但它没有考虑到我在树的层级上下移动。

Answer 1

假设你的二叉树是一个完美二叉树，你可以使用这个函数：

def traverse(height, left=1, right=0):
    path = []
    while True:
        if len(path) < height:
            path.append(left)
        else:
            while path[-1] == right:
                path.pop()
                if not path:
                    return
            path[-1] = right
        yield path

然后对于高度为3的树，如下调用：

for path in traverse(3):
    print(path)

获取迭代器以使用深度优先遍历二叉树

Getting an iterator for traversing a binary tree using depth first

python

binary-tree

depth-first-search