二叉樹的遍歷（traversing binary tree）是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中所有的結(jié)點，使得每個結(jié)點被訪問依次且僅被訪問一次。

前序遍歷（根 左 右）

先訪問根結(jié)點，然后前序遍歷左子樹，再前序遍歷右子樹

中序遍歷（左 根 右）

中序遍歷根結(jié)點的左子樹，然后訪問根結(jié)點，最后遍歷右子樹

后序遍歷（左 右 根）

從左到右先葉子后結(jié)點的方式遍歷訪問左右子樹，最后訪問根結(jié)點

層級遍歷（從上到下 從左到右）

從根結(jié)點從上往下從左往右依次遍歷

思路

非遞歸：

前序遍歷：從根節(jié)點開始，首先將根節(jié)點壓入棧中，棧不為空進行出棧并打印結(jié)點的value數(shù)值，然后將該結(jié)點的不為空的右結(jié)點和左結(jié)點依次進行入棧操作重復直到棧為空。

后序遍歷：從根節(jié)點開始，首先將根節(jié)點壓入棧中，棧不為空進行出棧并入棧到另一個棧中，然后將該結(jié)點的不為空的左結(jié)點和右結(jié)點依次進行入棧操作重復直到棧為空。然后遍歷另一個棧進行出棧并打印結(jié)點的值。

中序遍歷：從根節(jié)點開始將該結(jié)點以及它的左邊界依次進行入棧，當該結(jié)點為null時，然后進行出棧操作，打印出棧結(jié)點的value數(shù)值，并入棧彈出結(jié)點的右結(jié)點，然后重復上述步驟，繼續(xù)入棧該結(jié)點的左邊界直到為空。。。。

層次遍歷：從根節(jié)點放入隊列，隊列不為空的時候進行出隊列并打印該結(jié)點的value數(shù)值，然后依次將該結(jié)點的左結(jié)點和右結(jié)點進行放入隊列，一直重復直到隊列為空。

代碼

Node結(jié)點

public class Node<V> {V value;public Node(V value) {this.value = value;}public Node left;public Node right;
}

遍歷代碼

public class Tree {//遞歸先序遍歷public static void preOrder1(Node head){if(head!=null){System.out.print(head.value+" ");preOrder1(head.left);preOrder1(head.right);}}//先序遍歷public static void preOrder(Node head){if(head!=null){Stack<Node> stack=new Stack<>();stack.add(head);//壓到棧尾while (!stack.empty()){head=stack.pop();System.out.print(head.value+" ");if(head.right!=null)stack.push(head.right);if(head.left!=null)stack.push(head.left);}}System.out.println();}//后序遍歷public static void postOrder(Node head){if(head!=null){Stack<Node> stack1=new Stack<>();Stack<Node> stack2=new Stack<>();stack1.push(head);while (!stack1.empty()){head = stack1.pop();stack2.push(head);if(head.left!=null)stack1.push(head.left);if(head.right!=null)stack1.push(head.right);}while (!stack2.empty()){Node pop = stack2.pop();System.out.print(pop.value+" ");}System.out.println();}}//中序遍歷public static void inOrder(Node head){Stack<Node> stack=new Stack<>();while (!stack.empty()||head!=null){if(head!=null){stack.push(head);head=head.left;}else {head=stack.pop();System.out.print(head.value+" ");head=head.right;}}System.out.println();}//層次遍歷public static void widthOrder(Node head){if(head!=null){Queue<Node> queue=new LinkedList<>();queue.add(head);while (!queue.isEmpty()){Node poll = queue.poll();System.out.print(poll.value+" ");if(poll.left!=null)queue.add(poll.left);if(poll.right!=null){queue.add(poll.right);}}}System.out.println();}}