Глубина первого алгоритма итеративного углубления для печати ширины двоичного дерева первой

Question

Я не программист, но как часть моего личного проекта я стремлюсь понять, есть ли рекурсивное решение для возможности сначала распечатать двоичное дерево, порядок уровней?Я понимаю, что можно использовать первый итеративный алгоритм глубины?

#Helper method
def getChildren(node):
    children=[]
    hasLeft = node.left is not None
    hasRight = node.right is not None
    if not hasLeft and not hasRight:
        return []
    if hasLeft:
        children.append(node.left)
    if hasRight:
        children.append(node.right)
    return children

def DLS(node, depth):
    """Depth Limited Search"""
    if (depth == 0):
        return node
    elif (depth > 0):
        print node.value,
        children = getChildren(node)
        for child in children:
            DLS(child, depth-1)
    else:
        return False

Для следующего бинарного дерева:
(1)3<br> (2)2 (3)1<br> (4)1 (5)1 (6)1 (7)0<br> (8)1 (9)0

Я получаю этот вывод: (1)3 (2)2 (4)1 (8)1 (9)0 (5)1 (3)1 (6)1 (7)0 None

Что является не порядком уровня, а глубиной предварительного порядка.

Нужно ли повторять глубину для функции DLS?Как бы я реализовал распечатку порядка двоичного дерева?

Большое спасибо Alex

Answer 1

С точки зрения структур данных, разница между глубиной первой и шириной первой заключается в том, что глубина первой использует стек, а ширина первой использует очередь.

В глубине души идея заключается в том, чтобы "иметь дело с последствиями последней вещи, с которой вы столкнулись". Таким образом, со стеком вы всегда выталкиваете последний узел, который был нажат, и вы получаете правильное поведение.

Вначале идея заключается в том, чтобы «сначала разобраться со всеми последствиями выбранного узла, а затем двигаться дальше». Итак, вы сначала выясняете последствия (и сохраняете их), и только потом начинаете разбираться с ними в том порядке, в каком вы их нашли. Простейшая структура данных для поддержки этого - очередь.

Проблема в том, что рекурсия использует стек (стек вызовов). Таким образом, вы не видите структуру данных, но на самом деле она есть. Поскольку не существует (простого) способа организации очередей вызовов, вы не можете перевести поиск в ширину в код без использования явной очереди.

Если вам нужна информация о реализации в ширину с очередью, я предлагаю вам проверить Википедия .