Итеративный обход двоичного дерева в обратном порядке с одним стеком, как подойти к проблеме?

Я изучал алгоритмы и структуры данных и написал обход двоичного дерева в обратном порядке без использования рекурсии и с использованием только одного стека.

Вот код:

def postorder_iterative(self):
    current = self
    s = []
    current1 = None
    done = 0
    def peek(s):
        return s[-1]

    while(not done):
        if current and (current != current1):
            s.append(current)
            current = current.leftChild
        elif(len(s) > 0):
            if peek(s).rightChild and peek(s).rightChild != current:
                current = peek(s).rightChild
            else:
                current = current1 = s.pop()
                print(current.key)
        else:
            done = 1

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

Может кто-нибудь объяснить, что такое интуитивный способ мышления об этой проблеме?

Я хотел бы иметь возможность воспроизвести это с помощью логики и не тратить на это столько времени, сколько я потратил.


python iteration binary-search-tree tree-traversal postorder
person d_darric    schedule 11.02.2019    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Обход в обратном порядке требует, чтобы вы печатали текущее значение узла только после обхода левого и правого поддеревьев. Вы используете стек для обхода только левого дерева и используете переменную current1 (последний напечатанный узел), чтобы знать, что теперь вы выходите из правого дерева, чтобы вы могли напечатать текущий узел.

Я бы переименовал current в node, current1 в last (для последней печати), удалил функцию peek(), чтобы просто ссылаться на stack[-1] непосредственно как tos (верхняя часть стека), и упростил ваш подход к:

def postorder_iterative(self):
    node, last = self, None
    stack = []

    while True:
        if node and node is not last:
            # build up the stack from the left tree
            stack.append(node)
            node = node.leftChild
        elif stack:
            # no more left-hand tree to process, is there a right-hand tree?
            tos = stack[-1]
            if tos.rightChild and tos.rightChild is not node:
                node = tos.rightChild
            else:
                # both left and right have been printed
                node = last = stack.pop()
                print(last.key)
        else:
            break

Однако все еще трудно понять, что происходит, поскольку связь между last и точкой, где были обработаны левое и правое поддеревья, не совсем ясна.

Я бы использовал один стек с флагом состояния, чтобы отслеживать, где вы находитесь в процессе:

def postorder_iterative(self):
    new, left_done, right_done = range(3)   # status of node
    stack = [[self, new]]  # node, status

    while stack:
        node, status = stack[-1]
        if status == right_done:
            stack.pop()
            print(node.key)
        else:
            stack[-1][1] += 1 # from new -> left_done and left_done -> right_done
            # new -> add left child, left_done -> add right child
            next_node = [node.leftChild, node.rightChild][status]
            if next_node is not None:
                stack.append((next_node, new))

Узлы проходят через три состояния, просто увеличивая флаг состояния. Они начинаются как новые узлы, затем продвигаются к левому, затем правому, и когда вершина стека находится в этом последнем состоянии, мы удаляем ее. из стека и вывести значение узла.

Находясь в состоянии new или left, мы добавляем левый или правый узел, если он есть, в стек как новый узел.

Другой подход помещает правое дерево в стек перед текущим узлом. Затем позже, когда вы вернетесь к текущему узлу, взяв его из стека, вы можете обнаружить случай, когда вам все еще нужно обработать правую часть, потому что вершина стека будет иметь правый узел. В этом случае вы заменяете вершину стека текущим узлом и продолжаете оттуда; позже вы вернетесь в то же место, и у вас больше не будет этого правого узла в верхней части стека, чтобы вы могли напечатать:

def postorder_iterative(self):
    stack = []
    node = self

    while node or stack:
        while node:
            # traverse to the left, but add the right to the stack first
            if node.rightChild is not None:
                stack.append(node.rightChild)
            stack.append(node)
            node = node.leftChild

        # left-hand tree traversed, time to process right or print
        node = stack.pop()

        if stack and node.rightChild is stack[-1]:
            # right-hand tree present and not yet done, swap tos and node
            node, stack[-1] = stack[-1], node
        else:
            print(node.key)
            node = None
person Martijn Pieters    schedule 11.02.2019