前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
树的普通先序、中序、后序遍历

解决方案

方案一：
递归方法
1、先序先输出，后序后输出，中序中间输出，剩下的左右子树交给递归即可
2、将递归看成解决子问题的方式
方案二：
栈方法：
· 先序：
1、出根节点，依次将右、左放入
2、循环1步骤即可完成，栈为空结束
· 中序：
1、将根节点和根节点的所有左子节点放入栈
2、每弹出一个，将右子节点和右子节点的所有左子节点放入
3、循环步骤2即可
· 后序：
双栈法：
1、栈s1先序遍历微调一下将顺序先不输出，放入另一个栈s2中
2、s2依次弹出即可，类似先序遍历的逆过程
单栈法：
1 、栈s将将根节点和根节点的所有左子节点放入栈
2、每一次检测栈顶元素，先不弹出
3、判断栈顶元素是否满足弹出条件，满足时弹出，不满足则其将右子节点和右子节点的所有左子节点放入

代码编写

java语言版本

public class TreeUtils {

    /**
     * 递归先序遍历
     * @param root
     */
    public static void printPreOrder(MyTreeNode root){
        if (root == null){
            return;
        }
        System.out.println(root.getData());
        printPreOrder(root.getLeft());
        printPreOrder(root.getRight());
    }

    /**
     * 递归中序遍历
     * @param root
     */
    public static void printMidOrder(MyTreeNode root){
        if (root == null){
            return;
        }
        printMidOrder(root.getLeft());
        System.out.println(root.getData());
        printMidOrder(root.getRight());
    }

    /**
     * 递归后续遍历
     * @param root
     */
    public static void printPosOrder(MyTreeNode root){
        if (root == null){
            return;
        }
        printPosOrder(root.getLeft());
        printPosOrder(root.getRight());
        System.out.println(root.getData());
    }


    /**
     * 单栈先序遍历
     * @param root
     */
    public static void printByStackPre(MyTreeNode root){
        Stack<MyTreeNode> helperStack = new Stack<>();
        helperStack.push(root);
        while (!helperStack.isEmpty()){
            // 根出，右进、左进
            MyTreeNode pop = helperStack.pop();
            if (pop.getRight() != null){
                helperStack.push(pop.getRight());
            }
            if (pop.getLeft() != null){
                helperStack.push(pop.getLeft());
            }
            System.out.println(pop.getData());
        }
    }


    /**
     * 单栈中序遍历
     * @param root
     */
    public static void printByStackMid(MyTreeNode root){
        if (root == null){
            return;
        }
        Stack<MyTreeNode> helperStack = new Stack<>();
        MyTreeNode tem = root;
        while (tem != null){
            helperStack.push(tem);
            tem = tem.getLeft();
        }
        while (!helperStack.isEmpty()){
            MyTreeNode pop = helperStack.pop();
            // 右子树以及右子树的所有左子节点
            if (pop.getRight() != null){
                tem = pop.getRight();
                while (tem != null){
                    helperStack.push(tem);
                    tem = tem.getLeft();
                }
            }
            System.out.println(pop.getData());
        }
    }


    /**
     * 双栈后续遍历
     * @param root
     */
    public static void printByStackPos(MyTreeNode root){
        Stack<MyTreeNode> s1 = new Stack<>();
        Stack<MyTreeNode> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty()){
            MyTreeNode pop = s1.pop();
            // 先序遍历时先右后左，这里需要反过来
            if (pop.getLeft() != null){
                s1.push(pop.getLeft());
            }
            if (pop.getRight() != null){
                s1.push(pop.getRight());
            }
            s2.push(pop);
        }
        while (!s2.isEmpty()){
            MyTreeNode pop = s2.pop();
            System.out.println(pop.getData());
        }
    }

    /**
     * 单栈后续遍历
     * @param root
     */
    public static void printByOneStack(MyTreeNode root){
        Stack<MyTreeNode> stack = new Stack<>();
        // 上一次的打印节点
        MyTreeNode h = null;
        MyTreeNode tem = root;
        while (tem != null){
            stack.push(tem);
            tem = tem.getLeft();
        }
        while (!stack.isEmpty()){
            MyTreeNode peek = stack.peek();
            // 这只会走一次
            if (h == null){
                h = stack.pop();
                System.out.println(h.getData());
                continue;
            }
            if ((peek.getRight() == null && peek.getLeft() == null)
                    || h == peek.getRight()
                    || (h == peek.getLeft() && peek.getRight() == null)){
                // 三种情况直接输出
                h = stack.pop();
                System.out.println(h.getData());
            }else {
                // 左边打印完毕,并且右边有值,开始准备右边
                MyTreeNode right = peek.getRight();
                while (right != null){
                    stack.push(right);
                    right = right.getLeft();
                }
            }
        }
    }
    public static void main(String[] args) {

        MyTreeNode root = CommonUtils.getSearchMyTreeNode();

        printByOneStack(root);

    }
}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

递归方法就不聊了，聊一下栈方法如何替换递归方法
首先思考一下为什么树的遍历需要用到递归呢？
其实树的遍历的感觉很像单链表的感觉，是否有一种走着走着回不去的感觉？？对，这就是这类数据结构的特点：不能从后面的节点获取到前面的节点引用，那么这个时候该用什么方法能够完整的遍历他们呢？
第一种就是找个容器以空间O（n）的方法先保存，处理之后再还原回去，map或者其他空间
第二种就是通过递归，使用线程栈的方式存储前一个节点，使得当前栈结束后，还是能够通过线程栈访问到上一个节点
简单的树遍历就是利用了线程栈来进行每一个节点的保存，但是最大使用的栈空间跟树的高度有关，当一层结束后返回上一层时，上一层中的变量入参就是上一个节点，这时可以将该节点安排在遍历左子树前或者后都可以。
那么栈如何替换递归呢？
刚开始我想模拟线程栈的执行过程，操作数进入后，将下一层的操作数再压入，计算完成后弹出结果再访问栈顶即可，先序遍历确实可以模拟线程栈的方法遍历。精髓在于 入栈时需要考虑一下出栈的顺序，先序遍历为 中左右，那么入栈顺序为右左中才行 ，当然这里的右左中不能指子树，“右”其实是右子树的代表，也就是根节点，剩下的过程和方法栈基本是一样的
中序遍历需要初始化一下栈空间：其实不初始化也可以，可以将整个树看出某个右子树，操作一样，只不过也要保证顺序问题

后续遍历很麻烦，主要有几个方面：首先左右中时，当我们遍历到栈顶时，没有办法判断出是从左子树来还是右子树来的，其次 叶子节点、右子树为null的，从右子树遍历过来的，都需要打印当前栈顶，判断复杂，情况比较多。
那么这里我最后处理了就是如果栈顶符合了打印条件，那么就打印，如果不符合那么一定就是需要遍历右子树的情况！

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！