写给自己看之一：非递归遍历二叉搜索树（栈）

二叉搜索树的遍历是可以采用非递归方式的，其实所有的递归都可以写成循环的方式，就是简单和复杂，看得懂和看不懂之间的区别。
先看一段代码（本以为看了代码就能理解怎么写这么个循环遍历）：

Status InOrderTraverse(BiTree T, Status ( *Visit)(TElemType e)){
 InitStack(S); p = T;
 while(p || !StackEmpty(S)){
  if (p) { Push(S, p); p = p->lchild; }
  else {
   Pop(S, p);
   if(!Visit(p->data)) return ERROR;
   p = p->rchild;
  }
 }
 return OK
}

应该是一段很简洁高效的C/C++代码，但是看得我瞬间晕倒。我根本没看懂是怎么回事情。
再回头想一想什么才算利用栈写循环遍历呢？
首先，作为中序遍历，必然总要走所有的左子树。

    Stack< Node > stack = new Stack< Node >();

    Node n = this.root;

    while (n != null)
    {
        stack.Push(n);
        n = n.LChild;
    }

这一步必然是这样的。 其次，当栈找完所有的左子树的时候，就要打印出该节点的值（这个没问题）。这个时候其实相当于在访问中间节点，因为如果把空的左节点看成非空，那么其实就是打印一个空值，也就是说正真的打印其实是中节点。那么此时只需要遍历该节点的右子树就可以了。

    while (stack.Count != 0)
    {
        n = stack.Pop();
        _visit(n);
        stack.Push(n);
    }

但是，光这段代码不可能继续去遍历这颗右子树啊！怎么办？这个时候看看原来的C/C++代码，有点感觉了。只要把这两个循环结合在一起就可以解决这个问题。灵感来自最后那句stack.Push，只要重新复制n就解决了，不过这其实是一个揣测的操作，我是一点理论根据也没有，就算对了，我感觉依然没有完全搞懂的样子。

    while (n != null || stack.Count != 0)
    {
        if (n != null)
        {
            stack.Push(n);
            n = n.LChild;
        }
        else
        {
            n = stack.Pop();
            _visit(n);
            n = n.RChild;
        }
    }