①二叉树的遍历方式及其概念

讯享网

前序遍历：按照 Head-Left-Right的方式遍历，先输出头，再输出左侧，最后输出右侧。

                按照上图，前序遍历应该为：1>2>4>5>3>6>7

                对于上图的数和子树的关系做好区分，那么理解前序、中序、后序就很轻松了。

                例如：245为大二叉树的左侧，367为大二叉树的右侧，而4为245这个小数的左侧...

中序遍历：按照 Left-Head-Right的方式遍历，先输出左侧，再输出头，最后输出右侧。

                按照上图，中序遍历应该为：4>2>5>1>6>3>7

后序遍历：按照 Left-Right-Head的方式遍历，先输出左侧，再输出右侧，最后输出头。

                按照上图，后序遍历应该为：4>5>2>6>7>3>1

②二叉树的迭代遍历

        迭代这种方式在Java以及其它语言中都是很常用的，迭代具有代码简洁易懂，最接近算法底层原理等优势。但是当样本数据过大时，迭代会产生令人吃惊的空间消耗，例如斐波那契迭代数列，当计算第100个数字时，计算机就需要耗费大量时间和空间去做运算，这是迭代巨大的缺点。因此应该视工程实际情况来灵活选用迭代这个工具。

        话不多说，放马过来。（Java实现）

前序遍历：

        第一个if判断防止极端情况，即head==null的发生。

        下面三行分别是输出头部、左侧继续迭代、右侧再迭代。沿用第一张图做分析：首先head.val为1时，打印出输出1，而又head.left即2开始了新一轮的迭代；2进入迭代后，head会等于2，会打印2，而后再将2的左侧即4进入第三轮迭代，打印4，并且4左、右均为null；因此会返回2处，开始右侧迭代，打印5，并且5左、右均为null；因此再回到最开始的1，进入1右侧即3进行迭代，打印3；进入3左侧迭代，打印6，6左右为null，返回3；进入3的右侧，打印7，7左右为null，完成迭代。

因此前序遍历为1>2>4>5>3>6>7

 //先序 头>左>右 public static void preOrderRecursive(Node head){ if(head == null){return;} System.out.print(head.val); preOrderRecursive(head.left); preOrderRecursive(head.right); }

中序遍历：

讯享网//中序 左>头>右 public static void inOrderRecursive(Node head){ if(head==null){return;} inOrderRecursive(head.left); System.out.print(head.val); inOrderRecursive(head.right); }

后序遍历：

//后序 左>右>头 public static void posOrderRecursive(Node head){ if(head==null){return;} posOrderRecursive(head.left); posOrderRecursive(head.right); System.out.print(head.val); }

③二叉树的非迭代遍历

        如前所述，迭代在数据巨大的时候会造成大量空间耗费和时间消耗。对于任何一个工程来说，都是致命的，因此我们做出改进，来用while实现“迭代”的逻辑。

前序遍历：

        我们利用栈，先进后出FILO的特征，为了实现前序的头-左-右（Head-Left-Right）。我们可以反其道行之，将头先弹出，反过来压入右侧再压入左侧（这个顺序很重要！）。因此栈弹出的时候会先弹出左侧再弹出右侧。这就与 Head-Left-Right的顺序一致。

讯享网 public static void preOrder(Node head){ Stack<Node> stack = new Stack<>(); stack.add(head); while(!stack.isEmpty()){ head = stack.pop();//头先出来 System.out.print(head.val); //利用栈先进后出的特征，让右边进再左边进 //这样出来的时候可以保证左先出，右再出。完成 头>左>右先序遍历 if(head.right!=null) stack.push(head.right); if(head.left!=null) stack.push(head.left); }//结束while循环时stack全部弹出，先序完成 }

中序遍历：

        中序遍历相比较而言会比较复杂，同样利用栈的先进后出原理。但是判定条件为head！=null ||  !stack.isEmpty。下面我来参考文章开头的二叉树，捋一下思路。

     宏观思路为：把左侧全部压入栈，指针一直跟随左侧元素，若指针为空，栈弹出，并指向右侧，进而循环压入右侧元素的左侧（相对）。如此一来把二叉树斜着分割，所以压出栈的时候顺序相反，则是 左-头-右，这正好与中序遍历契合。

        由于中序遍历是Left-Head-Right。我们先创建栈，若头不为空则压入头，并把head作为指针移至原位（即1）的左侧（即2），这个操作放在while下面即把左侧所有不为null的元素都压入栈，即1入栈、2入栈、4入栈，而4左侧为null，停止while-if，转而进入while-else把栈顶元素放出（此时栈顶为4），打印4（此时栈内为1（底）-2（顶）），把head指针指向被打印元素的右侧（4右侧为null）；再次while大循环，head为空，进入else，打印此时栈顶元素，打印2，（此时栈内仅有1），head指针指向了2的右侧5....

        一致循环直到head==null 且栈内弹出所有元素停止。

 //二叉树中序遍历 左>头>右 public static void inOrder(Node head){ Stack<Node> stack = new Stack<>(); while(head!=null || !stack.isEmpty()){ if(head!=null){ stack.push(head); head = head.left; } else{ head = stack.pop(); System.out.print(head.val); head = head.right; } } }

后序遍历：

        后序遍历 Left-Right-Head。用了两个栈，首栈首先压入头部，再圧左侧，再压右侧。

而后将首栈弹出，顺序为头-右-左（注意左右被首栈倒出时颠倒），被尾栈接收为头（在最底层）-右-左。最后将尾栈遍历倒出，最终顺序为左-右-头，即后序遍历。

讯享网//二叉树后序遍历 左>右>头 利用一个辅助栈，只需要反向造即可 public static void posOrder(Node head){ Stack<Node> stack = new Stack<>(); Stack<Node> helpStack = new Stack<>(); stack.add(head); while(!stack.isEmpty()){ head = stack.pop(); helpStack.push(head); if(head.left!=null) stack.push(head.left); if(head.right!=null) stack.push(head.right); } while(!helpStack.isEmpty()){//把辅助栈倒出来 System.out.print(helpStack.pop().val); } }

最后，对调用方法进行测试

 public static class Node{ int val; Node left; Node right; Node(int x){ this.val = x; left = null; right = null; } } public static void main(String[] args){ Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); head.right.right = new Node(7); System.out.print("前序遍历"); preOrder(head); System.out.println(); System.out.print("中序遍历"); inOrder(head); System.out.println(); System.out.print("后序遍历"); posOrder(head); System.out.println(); }

结果

讯享网 ================recursive======================== pre-order: in-Order: pos-Order: Process finished with exit code 0