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

Question

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

Вот код:

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

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

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

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

Answer 1

Постпорядок обхода требует, чтобы вы печатали текущее значение узла только после обхода как левого, так и правого поддеревьев.Вы используете стек для обхода левого дерева only и используете переменную 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 = stack.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