Получить глубину на нерекурсивном обходчике по дереву в глубину? ⇐ Python

[Anonymous]

Я пытаюсь найти нерекурсивный «мощный/универсальный» алгоритм обхода дерева, который в конечном итоге дает не только узел, но и глубину узла, его родительский и родственный индексы, а также способен использовать метод «сначала в ширину». поиск (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_length=True: он не вызывает исключение, он просто неправильно определяет глубину. Инстинктивно у меня возникло ощущение, что код, вероятно, нуждается в минимальной настройке, чтобы обеспечить (правильную) глубину в DFS, но пока мне это не удалось.
Дело в том, что если я смогу найти способ получения глубины с помощью DFS, я считаю, что это будет довольно простой шаг для получения родительского узла как для BFS, так и для DFS, поддерживая «глубину до последнего». -узел» карта. Если вы можете получить родителя, вы также можете получить индекс родителя, самое простое, используя метод index списка (хотя могут быть гораздо более умные способы получить как родительский индекс, так и индекс родителя. ..).


Подробнее здесь: https://stackoverflow.com/questions/790 ... ree-walker