Java 二叉树的遍历

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。

前序遍历（根 左 右）

先访问根结点，然后前序遍历左子树，再前序遍历右子树

中序遍历（左 根 右）

中序遍历根结点的左子树，然后访问根结点，最后遍历右子树

后序遍历（左 右 根）

从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点

层级遍历（从上到下 从左到右）

从根结点从上往下从左往右依次遍历

思路

非递归：

前序遍历：从根节点开始，首先将根节点压入栈中，栈不为空进行出栈并打印结点的value数值，然后将该结点的不为空的右结点和左结点依次进行入栈操作重复直到栈为空。

后序遍历：从根节点开始，首先将根节点压入栈中，栈不为空进行出栈并入栈到另一个栈中，然后将该结点的不为空的左结点和右结点依次进行入栈操作重复直到栈为空。然后遍历另一个栈进行出栈并打印结点的值。

中序遍历：从根节点开始将该结点以及它的左边界依次进行入栈，当该结点为null时，然后进行出栈操作，打印出栈结点的value数值，并入栈弹出结点的右结点，然后重复上述步骤，继续入栈该结点的左边界直到为空。。。。

层次遍历：从根节点放入队列，队列不为空的时候进行出队列并打印该结点的value数值，然后依次将该结点的左结点和右结点进行放入队列，一直重复直到队列为空。

代码

Node结点

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