深度优先非递归树遍历器的产量深度？

Question

我正在尝试找到一种非递归的“强大/多功能”树步行者算法，最终不仅产生节点，而且产生节点的深度、其父节点和同级索引，并且能够使用广度优先搜索（ BFS）或深度优先搜索（DFS）。

可以像这样将深度优先和面包优先结合起来，只产生节点（注意假设一个节点可能有也可能没有密钥

CHILD_NODES

）。使用 Python 的示例 - 添加了“Python”标签，但显然不具体：

def get_walker(walk_by_depth=True):
    def walk(root):
        queue = [root]
        while len(queue) > 0:
            # the first item in the queue
            node_to_yield = queue.pop(0)

            yield node_to_yield

            if CHILD_NODES in node_to_yield:
                depth += 1    
                new_nodes = node_to_yield[CHILD_NODES]
                if walk_by_depth:
                    queue = new_nodes + queue
                else:
                    queue.extend(new_nodes)
    return walk

...并且添加少量代码可以让您仅产生广度优先搜索的深度：

def get_walker(walk_by_depth=True):
    def walk(root):
        queue = [root]
        depth = 0 
        depth_map_of_remaining_items = {0: 1}
        while len(queue) > 0:
            node_to_yield = queue.pop(0)
            if depth_map_of_remaining_items[depth] == 0:
                depth += 1
            depth_map_of_remaining_items[depth] -= 1

            yield node_to_yield, depth

            if CHILD_NODES in node_to_yield:
                depth += 1    
                new_nodes = node_to_yield[CHILD_NODES]
                if walk_by_depth:
                    queue = new_nodes + queue
                else:
                    queue.extend(new_nodes)
                    if depth not in depth_map_of_remaining_items:
                        depth_map_of_remaining_items[depth] = 0
                    depth_map_of_remaining_items[depth] += len(new_nodes)    
                depth -= 1
    return walk

上面的代码实际上不适用于

walk_by_depth=True

：它不会引发异常，它只是深度错误。本能地，我有一种感觉，代码可能只需要进行最小的调整即可在 DFS 上产生（正确）

depth

，但到目前为止我还没有成功。

问题是，如果我能找到一种使用 DFS 生成深度的方法，我相信对于 BFS 和 DFS（父节点）来说，通过维护“深度到最后的深度”，这将是一个相当容易生成的步骤。 -节点”地图。如果您可以获得父级，您也可以获得兄弟级索引，最简单的是使用

list

的

index

方法（尽管可能有更聪明的方法来获取父级和兄弟级索引......）。

Answer 1

这个想法是将深度也放入队列中：将节点对及其深度放入队列中，这会很容易。

无需对代码进行不必要的更改即可使其正常工作，我们得到：

def get_walker(walk_by_depth=True):
    def walk(root):
        queue = [(root, 0)]  # pair the root with its depth
        while len(queue) > 0:
            # the first item in the queue
            node_to_yield, depth = queue.pop(0)  # pop the pair

            yield node_to_yield, depth

            if CHILD_NODES in node_to_yield:
                # create pairs for all child nodes
                new_nodes = [(child, depth+1) for child in node_to_yield[CHILD_NODES]]
                if walk_by_depth:
                    queue = new_nodes + queue
                else:
                    queue.extend(new_nodes)
    return walk