主页 / coding / 问题 / 79012349
Accepted
mike rodent
Asked: 2024-09-23 02:49:10 +0800 CST

在深度优先非递归树遍历器上产生深度？

  • 772

我正在尝试寻找一种非递归的“强大/多功能”树遍历算法，最终不仅可以产生节点，还可以产生节点的深度、其父节点和其兄弟索引，并且能够使用广度优先搜索（BFS）或深度优先搜索（DFS）。

可以像这样将深度优先和面包优先结合起来，只需产生节点（NB 假设节点可能有也可能没有键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：它不会引发异常，只是深度错误。我本能地觉得代码可能只需要进行最小的调整就可以depth在 DFS 上产生（正确），但到目前为止我还没有成功。

问题是，如果我能找到一种使用 DFS 得出深度的方法，我相信对于 BFS 和 DFS 来说，通过维护“深度到最后一个节点”映射，得出父节点将是一个相当容易的步骤。如果您可以获得父节点，那么您也可以获得兄弟节点索引，最简单的方法是使用list的index方法（尽管可能有更聪明的方法来同时获得父节点和兄弟节点索引……）。

python

2 个回答

  1. Best Answer

    这个想法是将深度也放在队列中：将具有深度的节点对放入队列中，这将很容易。

    无需对代码进行过多更改即可使其正常工作，我们得到以下结果：

    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

    请注意pop(0)和new_nodes + queue不是高效操作。请考虑使用双端队列。

    • 1

  2. 按照 trincot 的建议使用deque，产生节点、深度、父级和兄弟索引：

    def get_walker(walk_by_depth=True):
    def walk(root):
        queue = deque([(root, 0, None, 0)]) 
        while len(queue) > 0:
            node_to_yield, depth, parent, sib_index = queue.popleft()  
            yield node_to_yield, depth, parent, sib_index
            if CHILD_NODES in node_to_yield:
                for sib_index, child in enumerate(node_to_yield[CHILD_NODES]):
                    node_tuple = (child, depth+1, node_to_yield, sib_index)
                    if walk_by_depth:
                        queue.insert(sib_index, node_tuple)
                    else:
                        queue.append(node_tuple)
    return walk
    • 1

相关问题