二叉数（三）

下面使用Java实现中序非递归遍历二叉树，开始之前我们先梳理一下它的执行逻辑。

1. 申请一个桟记为stack.初始化一个指针cur指向头节点。
2. 以头节点为起始，将树的整个左边界压入到桟中。及不断的另cur=cur.left,重复步骤2
3. 如果cur.left为空，弹出stack桟顶元素，并打印桟顶元素的值，桟顶元素记为node,另cur=node.right重复步骤2
4. 直到cur指向的node为空并且stack为空时，结束该过程。

下面是Java代码实现：

public static void inOrder1(BiTree tree){
    Stack<BiTree> stack = new Stack<>();
    while(tree != null || !stack.empty()){
        if(tree!=null){
            stack.push(tree);
            tree = tree.lChild;
        }else{
            BiTree node = stack.pop();
            System.out.print(node.data);
            tree = node.rChild;
        }
    }
}