二叉树的先序、中序、后序以及层次遍历_先序遍历

二叉树的先序、中序、后序以及层次遍历

方法：在遍历二叉树的时候，一个节点的遍历我们把它看做要经过它三次(下图红色区域)。

当经过一次，被写出来的点，我们称它为先序遍历。

当经过两次，被写出来的点，我们称它为中序遍历。

当经过三次，被写出来的点，我们称它为后序遍历。

1、先序(根)遍历

先序遍历(D-L-R)，按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中，先根后左再右。巧记：根左右。

先序遍历(只结果该节点一次，就被记录下来)

2、中序(根)遍历

 中序遍历（LDR）,按照左根右的顺序沿一定路径经过路径上所有的结点，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树，巧记：左根右。

 3、后序(根)遍历

 后序遍历（LRD）,按照左右根的顺序沿一定路径经过路径上所有的结点，后序遍历首先遍历左子树，然后访问右子树，最后遍历根结点，巧记：左右根。

 4、层次遍历

按照二叉树的层数，一层层遍历。

要进行层次遍历，需要建立一个循环队列。先将二叉树头结点入队列，再将头结点的左、右节点入队列，此时头节点就可以出队列遍历，然后重复上面的操作直到队头和队尾为空，这就是层次遍历。

注：在二叉树遍历中先序和中序或者中序和后序可以确定唯一的一棵二叉树。

 例如：一棵二叉树的中序是：BDCAEHGKF    后序是：DCBHKGFEA

就可以得到该二叉树的结构如下：

 代码：

节点类

   public class Node {//节点类
	 public int data;//数据域
	 public Node lnode;//左节点
	 public Node rnode;//右节点
	 
	 public void addNode(Node n) {
		 if(n.data < this.data) {//左节点
			 if(lnode == null) {
				 lnode = n;
			 }else lnode.addNode(n);
		 }else {
			 if(rnode == null) {
				 rnode = n;
			 }else rnode.addNode(n);
		 }
	 }
	 
	 public void xianxu() {//先序遍历
        System.out.print(this.data);
		if(lnode != null) lnode.xianxu();
		if(rnode != null) rnode.xianxu();
	}
	public void zhongxu() {//中序遍历
		if(lnode != null) lnode.zhongxu();
		System.out.print(this.data);
		if(rnode != null) rnode.zhongxu();
	}
    public void houxu() {//后序遍历
		if(lnode != null) lnode.houxu();
		if(rnode != null) rnode.houxu();
        System.out.print(this.data);
	}
 
}

树类

public class MyTree {
	private Node root;//根节点
	
	public void add(int a) {
		Node n = new Node();
		n.data = a;
		if(root == null) {
			root = n;
		}else {
			root.addNode(n);
		}
	}
	
	public void sort() {
		if(root == null) return;
		else root.zhongxu();
	}
	
	public static void main(String[] args) {
		MyTree mt = new MyTree();
		mt.add(5);
		mt.add(4);
		mt.add(8);
		mt.add(6);
		mt.add(0);
		mt.sort();
		System.out.println();
		}
}