二叉树的非递归遍历二（中序/JAVA）

思路

与先序非递归遍历非常类似，沿左子树向下搜索，将结点圧入栈中直到结点为空即到达最左端，出栈获得结点并访问，再沿右子树继续。可以看到与先序唯一的不同，先序是在压入栈之前访问，而中序则是在出栈之后访问。同样当栈为空时遍历完成。

代码

这里不贴完整代码了，其余与先序代码完全一致。关键函数代码如下：

    //非递归中序遍历
    public static void NotReCuInOrder(BiTree T) {
            //栈初始化
            Stack S = new Stack();
            S.top = -1;
            S.nodes = new BiTree[100];
            BiTree p = T;
            //遍历
            while(p != null || S.top != -1) {
                if(p != null) {
                    S.nodes[++S.top] = p;//入栈
                    p = p.lchild;//沿左子树向下
                } else {
                    p = S.nodes[S.top--];//出栈
                    System.out.print(p.data+" ");//访问
                    p = p.rchild;//沿右子树
                }
            }
    }