二叉树的非递归遍历

二叉树的遍历是数据结构这门课中一个很基础的要求，通常我们会使用递归的方式来遍历二叉树，递归也比较利于理解。

而对于二叉树的非递归遍历，通常我们采用栈的方式实现。下面就分别说一下如何使用栈来实现二叉树的先序、中序、后序遍历。

先贴一下数据结构：

/**
 * @author thomas
 * @version 1.0
 * @date 2020/12/20 23:30
 * TODO
 **/
public class TreeNode {

    private String value;

    private TreeNode leftChild;

    private TreeNode rightChild;

    public TreeNode() {}
    public TreeNode(String value) {
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public Boolean hasLeftChild() {
        return leftChild != null;
    }

    public Boolean hasRightChild() {
        return rightChild != null;
    }

    public void setLeftChild(TreeNode node) {
        this.leftChild = node;
    }

    public void setRightChild(TreeNode node) {
        this.rightChild = node;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }
}

先序遍历（先根遍历）

先序遍历的顺序是

• 先访问根节点
• 再访问左子树
• 再访问右子树

简记遍历顺序就是根左右。

我们可以使用一个栈来模拟这个访问过程：

• 先将根节点入栈
• 然后弹出栈顶元素并打印
• 然后将右孩子入栈，再将左孩子入栈（注意顺序），然后转到第二步，直到栈中元素为空。

转换成代码很简单

/**
 * @author thomas
 * @date 2020/12/20 23:34
 * 非递归先序遍历二叉树
 **/
public void preOrder(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        // 栈顶元素出栈并打印之
        TreeNode top = stack.pop();
        System.out.print(top.getValue());
        // 右孩子、左孩子入栈
        if (top.hasRightChild()) {
            stack.push(top.getRightChild());
        }
        if (top.hasLeftChild()) {
            stack.push(top.getLeftChild());
        }

    }

}

后序遍历（后根遍历）

后序遍历的顺序是：

• 先访问左孩子
• 再访问右孩子
• 再访问根节点

简记遍历顺序就是左右根。

回想一下先序遍历的顺序，根左右，如果我们把左右子树入栈的顺序变换一下，那么遍历的顺序就变成了根右左，然后我们在之前打印的时候不执行打印操作，而是改为将要打印的元素再压入一个新的栈里，然后再依次将元素出栈打印，那不就得到了我们想要的后序遍历的顺序左右根吗？

按照这个想法，我们将上面的代码可以修改为：

**
 * @author thomas
 * @date 2020/12/21 0:02
 * 非递归后序遍历二叉树
 **/
public void postOrder(TreeNode root) {
    Stack<TreeNode> preOrderStack = new Stack<>();
    Stack<TreeNode> postOrderStack = new Stack<>();
    preOrderStack.push(root);
    while (!preOrderStack.empty()) {
        // 栈顶元素出栈并打印之
        TreeNode top = preOrderStack.pop();
        // 将原本的打印操作改为压入新的栈中
        inOrderStack.push(top);
        if (top.hasLeftChild()) {
            preOrderStack.push(top.getLeftChild());
        }
        if (top.hasRightChild()) {
            preOrderStack.push(top.getRightChild());
        }

    }
    // 出栈依次打印
    while (!inOrderStack.empty()) {
        System.out.print(inOrderStack.pop().getValue());
    }

}

中序遍历（中根遍历）

中序遍历的顺序是：

• 先访问左孩子
• 再访问根节点
• 再访问右孩子

按照这个顺序，我们可以得出以下步骤：

• 访问根节点，压栈
• 访问根节点的左孩子，继续压栈，循环这个过程，直到栈顶元素没有左孩子
• 开始处理栈中的元素，栈不为空时循环。每次弹出栈顶元素并访问之。
• 将弹出的栈顶元素的右孩子作为根节点，跳到第一步执行，直到栈内元素为空

转换成代码如下：

/**
 * @author thomas
 * @date 2020/12/21 0:22
 * 非递归中序遍历
 **/
public void inOrder(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    // 先找到最左子节点
    TreeNode p = stack.peek().getLeftChild();
    while (p != null ) {
        stack.push(p);
        p = p.getLeftChild();
    }
    while (!stack.empty()) {
        // 栈顶元素出栈并访问之
        TreeNode peak = stack.pop();
        System.out.print(peak.getValue());
        // 如果有右孩子则压栈
        if (peak.hasRightChild()) {
            stack.push(peak.getRightChild());
            // 压栈之后寻找最左子节点
            p = stack.peek().getLeftChild();
            while (p != null ) {
                stack.push(p);
                p = p.getLeftChild();
            }
        }
    }
}

以上就是非递归遍历二叉树的方法了，虽然代码不复杂，但还是很值得深入理解其中的思想的。

Q.E.D.