二叉树的非递归遍历

二叉树最基础的插入，删除，生成以及递归遍历等内容不再赘述，这里只讨论二叉树的非递归遍历。

前序遍历

在二叉树的三种遍历中，前序遍历是最简单的，其次是中序遍历，最难的是后序遍历。前序遍历的原理是利用了栈。观察如下一颗二叉树：

要对其进行前序遍历，我们从根节点1开始，先输出根节点的值，同时一直向下遍历左子树，与此同时只要右子树不为空，就将右子树压入栈，并将指针移到它的左子树上，重复输出、将右子树压入栈、遍历左子树的操作。按照这个逻辑，我们一路遍历到节点4，此时栈中元素为【3、5】。此时打印节点4，节点4不再有左子树，停止向下遍历，弹出栈顶元素使指针指向它，由于每到一棵树都先将其右子树压入栈，所以栈顶元素一定为最近的待访问的右子树。对于这棵树，此时指针指向节点5，栈中元素为【3】。重复如上操作，完成前序遍历。

由于前序遍历需要先访问根节点，其次访问左节点，最后访问右节点，所以这个方法的思路是每到一个节点首先打印这个节点，与此同时一直访问左子树直到不能访问，最后访问右节点，如果右节点也不能访问或访问完毕，弹出栈顶元素作为新的根节点重复上述操作。下面是Java实现代码：

void preorderTraversedWithoutRecursive(BinaryTree tree) {
    Stack<BinaryTree> stack = new Stack<>();
    // 向栈底压入空元素作为遍历结束的标志
    stack.push(null);
    while (tree != null) {
        // 打印根节点信息
        System.out.print(tree.entry + " ");
        // 右子树不为空则压栈
        if (tree.rightSubTree != null) {
            stack.push(tree.rightSubTree);
        }
        // 左子树不为空则访问左子树，左子树为空则弹栈访问最近的右子树
        if (tree.leftSubTree != null) {
            tree = tree.leftSubTree;
        } else {
            tree = stack.pop();
        }
    }
}

中序遍历

中序遍历其实与前序遍历相似，还是以这棵树为例：

中序遍历还是一直往左遍历，只要节点左子树不为空，就将节点压入栈，然后继续向左遍历。当左子树为空时，输出根节点信息，在这题中，由节点1开始向左遍历到节点4，此时栈中元素为【1、2】。然后在右子树不为空的前提下跳转到右子树上循环进行遍历左子树、压根节点入栈的操作，如果右子树也为空，意味着此时已经完成这棵子树的中序遍历，此时输出栈顶元素的节点信息，也就是最近的根节点，在这题中，当指针指向节点4，左右子树均为空时，输出栈顶元素节点2的信息，同时弹出栈顶元素，将指针移到这个根节点的右子树上，也就是节点5，循环以上操作。下面是Java实现代码：

void inorderTraversedWithoutRecursive(BinaryTree tree) {
    Stack<BinaryTree> stack = new Stack<>();
    do {
        // 遍历结束的标志：栈空且当前树为空
        if (tree == null) {
            if (stack.empty()) {
                return;
            }
            System.out.print(stack.peek().entry + " ");
            tree = stack.pop().rightSubTree;
        }
        // 一直向左遍历并将根节点压入栈
        while(tree.leftSubTree != null) {
            stack.push(tree);
            tree = tree.leftSubTree;
        }
        // 输出节点信息
        System.out.print(tree.entry + " ");
        // 如果右子树为空，栈不空就输出栈顶元素信息并弹出它指向栈顶元素右子树，否则进入右子树开始循环
        if (tree.rightSubTree == null && !stack.empty()) {
            System.out.print(stack.peek().entry + " ");
            tree = stack.pop().rightSubTree;
        } else {
            tree = tree.rightSubTree;
        }
    } while (true);
}

后序遍历

后序遍历是三种遍历中最难的，还是以这棵树为例：

观察以2为根节点的子树，对其进行后序遍历结果为4、5、2，指针从2出发，先到达4，再经过2到达5，最后回到2，那么我们何时才能输出根节点？判断的依据就是看我们是从左子树回到它还是从右子树回到它，在后序遍历中，我们输出根节点一定是从右子树回到根节点时输出信息，所以我们需要用额外空间存储每个根节点的遍历方向。

我们首先从根节点开始一直向左遍历到达节点4，此时栈中元素为【1，2，4】遍历方向均为左。节点4由于没有左子树，更改遍历方向为2，对节点4的右子树进行遍历，而节点4同样没有右子树，此时观察栈顶元素的遍历方向，为1表示左子树已经遍历完成，而此时没有右子树或右子树也已遍历完成，对根节点也就是节点4进行弹栈输出操作，输出完毕后，只要栈不为空，就修改栈顶元素的遍历方向为1，这意味着，节点2的左子树已经遍历完成，接下来遍历节点2的右子树，节点5操作步骤与节点4相同，操作完成后弹栈输出节点2的信息，重复以上操作直到当前指向的树为空或栈为空。下面是Java实现代码：

void postorderTraversedWithoutRecursive(BinaryTree tree) {
    Stack<BinaryTree> stack = new Stack<>();
    Stack<Integer> orient = new Stack<>();
    // 遍历结束的标志，栈为空或树为空
    while (tree != null || !stack.empty()) {
        // 一直向左遍历并将根节点压入栈，同时标记当前根节点的遍历方向为0
        while (tree != null) {
            stack.push(tree);
            orient.push(0);
            tree = tree.leftSubTree;
        }
        // 如果栈不空且栈顶元素的遍历方向为1，就对栈顶元素进行弹栈输出
        while (!stack.empty() && orient.peek() == 1) {
            orient.pop();
            System.out.print(stack.pop().entry + " ");
        }
        // 如果栈不为空，开始遍历右子树并将遍历方向改为1
        if (!stack.empty()) {
            orient.pop();
            orient.push(1);
            tree = stack.peek().rightSubTree;
        }
    }
}