二叉树（二）

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

1. 首先申请一个新的桟，记为stack。
2. 每次将头节点head压入stack中
3. 每次从stack中弹出桟顶节点，记为cur，然后打印cur节点的值。如果cur右孩子不为空的话，将cur的右孩子先压入stack中。最后如果cur的左孩子不为空的话，将cur的左孩子压入stack中。
4. 不断重复步骤3,直到stack为空，全部过程结束。

下面是Java代码实现：

/**
* 先序遍历
* 非递归
*/

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