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

前序遍歷（根 左 右）

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

中序遍歷（左 根 右）

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

后序遍歷（左 右 根）

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

層級(jí)遍歷（從上到下 從左到右）

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

思路

非遞歸：

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

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

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

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

代碼

Node結(jié)點(diǎn)

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();}}