Início / coding / Perguntas / 79012349
Accepted
mike rodent
Asked: 2024-09-23 02:49:10 +0800 CST

Profundidade de rendimento em um tree walker não recursivo em profundidade?

  • 772

Estou tentando encontrar um algoritmo de tree walker "poderoso/versátil" não recursivo, que, em última análise, produza não apenas o nó, mas a profundidade do nó, seu índice pai e irmão, e seja capaz de usar uma busca em largura (BFS) ou busca em profundidade (DFS).

É possível combinar depth-first e bread-first assim, apenas produzindo o nó (NB assume um nó que pode ou não ter a chave CHILD_NODES). Exemplo usando Python - tag "Python" adicionada, mas obviamente não específica:

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

... e adicionar uma pequena quantidade de código permite que você obtenha uma profundidade somente para uma busca em largura :

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

O código acima não funciona de fato com walk_by_depth=True: ele não levanta uma Exception, ele apenas erra a profundidade. Instintivamente, tenho a sensação de que o código provavelmente só precisa de um ajuste mínimo para renderizar (corrigir) depthem um DFS, mas não tive sucesso até agora.

A questão é que, se eu puder encontrar uma maneira de produzir a profundidade com um DFS, acredito que será um passo bem fácil produzir, tanto para BFS quanto para DFS, o nó pai, mantendo um mapa "profundidade-para-último-nó". Se você puder obter o pai, também poderá obter o índice irmão, no máximo usando o método listde index(embora possa haver maneiras muito mais inteligentes de obter o índice pai e irmão...).

python

2 respostas

  1. Best Answer

    A ideia é colocar a profundidade na fila também: coloque pares de nós com suas profundidades na fila, e será fácil.

    Sem alterar mais do que o necessário no seu código para fazê-lo funcionar, obtemos isto:

    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

    Note que pop(0)e new_nodes + queuenão são operações eficientes. Considere usar um deque.

    • 1

  2. Implementação usando dequeconforme sugerido por trincot, produzindo nó, profundidade, índice pai e irmão:

    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

relate perguntas