帮我理解不使用递归的中序遍历

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

在编程中，有时候我们需要处理一些数据，比如从一个地方获取数据，然后在另一个地方使用这些数据。这个过程可能会涉及到很多步骤，比如读取文件、处理数据、再把结果保存到文件中。

有些时候，我们会遇到一些问题，比如数据格式不对、文件找不到等等。这些问题可能会导致程序出错，无法正常运行。因此，在编写程序时，我们需要考虑到这些潜在的问题，并做好相应的处理。

为了让程序更加健壮，我们可以使用一些技巧，比如在读取文件之前先检查文件是否存在，或者在处理数据时加一些错误处理的代码，这样即使出现问题，程序也能优雅地处理，而不是直接崩溃。

总之，编程不仅仅是写代码，更是要考虑到各种可能出现的情况，确保程序能够顺利运行。

def print_tree_in(root):
    stack = []
    current = root
    while True:
        while current is not None:
            stack.append(current)
            current = current.getLeft();
        if not stack:
            return
        current = stack.pop()
        print current.getValue()
        while current.getRight is None and stack:
            current = stack.pop()
            print current.getValue()
        current = current.getRight();

Answer 2

这里有一段简单的非递归中序遍历的C++代码……

void inorder (node *n)
{
    stack s;

    while(n){
        s.push(n);
        n=n->left;
    }

    while(!s.empty()){
        node *t=s.pop();
        cout<<t->data;
        t=t->right;

        while(t){
            s.push(t);
            t = t->left;
        }
    }
}

Answer 3

首先，从递归算法开始（伪代码）：

traverse(node):
  if node != None do:
    traverse(node.left)
    print node.value
    traverse(node.right)
  endif

这是一个明显的尾递归案例，所以你可以很容易地把它转换成一个while循环。

traverse(node):
  while node != None do:
    traverse(node.left)
    print node.value
    node = node.right
  endwhile

现在你面临一个递归调用。递归调用的作用是把一个新的上下文放到栈上，运行代码从头开始，然后再取回这个上下文，继续之前的操作。所以，你创建了一个栈来存储信息，还有一个循环来判断每次迭代时，我们是在“第一次运行”的情况（非空节点）还是在“返回”的情况（空节点，非空栈），然后执行相应的代码：

traverse(node):
  stack = []
  while !empty(stack) || node != None do:
    if node != None do: // this is a normal call, recurse
      push(stack,node)
      node = node.left
    else // we are now returning: pop and print the current node
      node = pop(stack)
      print node.value
      node = node.right
    endif
  endwhile

最难理解的部分是“返回”这一块：你需要在循环中判断你正在运行的代码是处于“进入函数”的状态，还是“从调用返回”的状态，这样你会有一个if/else链，根据你代码中非终止递归的数量来处理不同的情况。

在这个特定的情况下，我们使用节点来保存关于情况的信息。另一种方法是把这些信息存储在栈本身（就像计算机处理递归一样）。使用这种技术，代码虽然不那么优化，但更容易理解。

traverse(node):
  // entry:
  if node == NULL do return
  traverse(node.left)
  // after-left-traversal:
  print node.value
  traverse(node.right)

traverse(node):
   stack = [node,'entry']
   while !empty(stack) do:
     [node,state] = pop(stack)
     switch state: 
       case 'entry': 
         if node == None do: break; // return
         push(stack,[node,'after-left-traversal']) // store return address
         push(stack,[node.left,'entry']) // recursive call
         break;
       case 'after-left-traversal': 
         print node.value;
         // tail call : no return address
         push(stack,[node.right,'entry']) // recursive call
      end
    endwhile