Помогите мне понять Inorder Traversal без использования рекурсии

Question

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

Это то, что я пробовал до сих пор:

def traverseInorder(node):
    lifo = Lifo()
    lifo.push(node)
    while True:
        if node is None:
            break
        if node.left is not None:
            lifo.push(node.left)
            node = node.left
            continue
        prev = node
        while True:
            if node is None:
                break
            print node.value
            prev = node
            node = lifo.pop()
        node = prev
        if node.right is not None:
            lifo.push(node.right)
            node = node.right
        else:
            break

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

Я не пробовал пост-порядок обхода, но я думаю, что это похоже, и там я тоже столкнусь с такой же концептуальной блокировкой.

Спасибо за ваше время!

П.С .: Определения Lifo и Node:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class Lifo:
    def __init__(self):
        self.lifo = ()
    def push(self, data):
        self.lifo = (data, self.lifo)
    def pop(self):
        if len(self.lifo) == 0:
            return None
        ret, self.lifo = self.lifo
        return ret

Answer 1

Маленькая оптимизация ответа от @ Emadpres

def in_order_search(node):
    stack = Stack()
    current = node

    while True:
        while current is not None:
            stack.push(current)
            current = current.l_child

        if stack.size() == 0:
            break

        current = stack.pop()
        print(current.data)
        current = current.r_child

Answer 2

@ Виктор, у меня есть предложение по вашей реализации, пытающееся поместить состояние в стек. Я не вижу в этом необходимости. Потому что каждый элемент, который вы берете из стека, уже пройден. поэтому вместо того, чтобы хранить информацию в стеке, все, что нам нужно, это флаг, указывающий, является ли следующий обрабатываемый узел из этого стека или нет. Ниже приведена моя реализация, которая прекрасно работает:

def intraverse(node):
    stack = []
    leftChecked = False
    while node != None:
        if not leftChecked and node.left != None:
            stack.append(node)
            node = node.left
        else:
            print node.data
            if node.right != None:
                node = node.right
                leftChecked = False
            elif len(stack)>0:
                node = stack.pop()
                leftChecked = True
            else:
                node = None

Answer 3

Состояние можно запомнить неявно,

traverse(node) {
   if(!node) return;
   push(stack, node);
   while (!empty(stack)) {
     /*Remember the left nodes in stack*/
     while (node->left) {
        push(stack, node->left);
        node = node->left;
      }

      /*Process the node*/
      printf("%d", node->data);

      /*Do the tail recursion*/
      if(node->right) {
         node = node->right
      } else {
         node = pop(stack); /*New Node will be from previous*/
      }
    }
 }

Answer 4

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

Из Википедии , алгоритм, к которому вы стремитесь:

1. Посетите корень.
2. Пройдите по левому поддереву
3. Пройдите по правому поддереву

В псевдокоде (отказ от ответственности, я не знаю Python, поэтому извиняюсь за код в стиле Python / C ++ ниже!) Ваш алгоритм будет выглядеть примерно так:

lifo = Lifo();
lifo.push(rootNode);

while(!lifo.empty())
{
    node = lifo.pop();
    if(node is not None)
    {
        print node.value;
        if(node.right is not None)
        {
            lifo.push(node.right);
        }
        if(node.left is not None)
        {
            lifo.push(node.left);
        }
    }
}

Для прохождения по порядку вы просто меняете порядок, в котором вы помещаете левое и правое поддеревья в стек.