数据结构之二叉树的遍历3(java)

一：概述

绝大多数的可以用递归解决问题，也可以使用另一种数据结构来解决，这种数据结构就是栈。因为递归和栈都有回溯的特性。

二：具体说明

如何借助栈来实现二叉树的遍历，下面以二叉树的前序遍历为例，来阐述具体过程。

<1>首先遍历二叉树的根节点1，放入栈中。

<2>遍历根节点1的左孩子节点2，放入栈中。

<3>遍历节点2的左孩子节点4，放入栈中。

<4>节点4既没有左孩子，也没有右孩子，我们需要回溯到上一个节点2.如果不是做递归操作，怎么回溯呢？

栈可以存储刚才遍历的路径。让旧的栈顶元素4出栈，就可以重新访问节点2，得到节点2的右孩子5.

此时节点2已经没有了利用价值(已经访问过左孩子和右孩子)，节点2出栈，节点5入栈。

<5>节点5既没有左孩子，也没有右孩子，我i们需要再次回溯，一直回溯到节点1.所以让节点5出栈。根节点1的右孩子是节点3，节点1出栈，节点3入栈。

<6>节点的右孩子是节点6，节点3出栈，节点6入栈。

<7>节点6既没有左孩子，也没有右孩子，所以节点6出栈。此时栈为空，遍历结束。

具体前序遍历代码：

 /**
     * 二叉树非递归前序遍历
     * @param root
     */
    public static void preOrderTraveralWithStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = root;
        while(treeNode != null || !stack.isEmpty()) {
            //迭代访问节点的左孩子，并入栈
            while (treeNode != null) {
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            // 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
            if(!stack.isEmpty()) {
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }
        }
    }

二叉树的中序遍历和后序遍历的非递归实现，思路和前序遍历差不多，都是利用栈的回溯。