本文共 3697 字，大约阅读时间需要 12 分钟。

1，问题分析

public void visitFirst(Node tree) {        if (tree != null) {            System.out.print(tree.value + " ");//访问语句            visitFirst(tree.left);            visitFirst(tree.right);        }    }

由于不论先序还是中序，后序，在程序运行流程上没有本质区别，区别仅仅是访问语句的执行时间点。所以，只要有了先序的程序流程，改变一下访问语句代码位置，就可以实现前三种遍历方式。

2，先序遍历(非递归)

public void visitFirst_N(Node tree) {        if (tree != null) {            Stack
   
     s = new Stack();            Node cur = tree;            s.push(cur);            while (cur != null){                System.out.print(cur.value + " ");//访问语句代码                cur = cur.left;                if (cur != null)                    s.push(cur);                else {                    while(!s.empty()){                       Node t=s.pop();                       cur=t.right;                       if(cur!=null) { s.push(cur);break;}                    }                }            }        }    }
   

3，中序遍历(非递归)

public void midTest(Node tree){        if(tree!=null){           Stack
   
     s=new Stack();           Node cur=tree;            s.push(cur);            while(cur!=null){                cur=cur.left;                if(cur!=null){                    s.push(cur);                }else{                    while(!s.empty()){                        Node t=s.pop();                        System.out.print(t.value+" ");//访问语句代码                        cur=t.right;                        if(cur!=null){                            s.push(cur);                            break;                        }                    }                }            }        }    }
   

4，后续遍历(非递归)

比较复杂，为保证程序流程，将左边pop出来的数据填回去！由于有内存大小限制，不能使用标记数组！

public void LastTest(Node tree) {        if (tree != null) {            Stack
   
     s = new Stack();            Node cur = tree;            s.push(cur);            while (cur != null) {                cur = cur.left;                if (cur != null) {                    s.push(cur);                } else {                    while (!s.empty()) {                        Node t = s.peek();                        cur = t.right;                        if (cur == null) {                            Node x = s.pop();                            System.out.print(x.value + " ");                            Node y = s.pop();                            if (y.left == x) {                                s.push(y);                                cur = y.right;                            } else {                                Node k=s.peek();                                  System.out.print(y.value + " ");                                    //清空栈                                if(k.right==y) {                                    while (!s.empty()) {                                        System.out.print(s.pop().value + " ");                                    }                                    return;//直接结束                                }                                cur = k.right;                                //调试                               // Scanner sc = new Scanner(System.in);                                //sc.nextInt();                            }                        }                        if (cur != null) {                            s.push(cur);                            break;                        }                    }                }            }        }    }
   

5，层次遍历(非递归)

private void visitLevel(Node x) {        Queue
   
     queue = new Queue<>();        while (x != null) {            System.out.print(x.value + " ");            if (x.left != null)                queue.enqueue(x.left);            if (x.right != null)                queue.push(x.right);            x = queue.deQueue();        }    }
   

转载地址：http://mpvi.baihongyu.com/