树的层次遍历
in 算法与数据结构 with 0 comment

树的层次遍历

in 算法与数据结构 with 0 comment

< 转自 -博客园- >

说到树的层次遍历,就应该提到广度优先搜索算法------广度优先搜索算法(Breadth-First-Search),又译作宽度优先搜索,或横向优先搜索,简称BFS,是一种图形搜索算法。

     可以说树层次遍历是广度优先遍历的一种直接应用吧,比较广度优先搜索是图形的一种搜索算法,图形是一种比较大的概念,但这个和深度优先齐名的算法,在树的层次遍历引用中,并没有那么复杂,或许是因为用在树的遍历,而非图吧。
   树的层次遍历,故名思议,在一棵树中,把节点从左往右,一层一层的,从上往下,遍历输出,这里要用到一种很重要的数据结构,队列,一提到队列,我们就要想到先进先进先,即为先进入队列元素,先接受处理,我们在日常生活中排队时,就是先到的人,先接受服务。

      理解好队列,可以很容易的解决树的层此遍历,步骤如下:
   1.首先将根节点放入队列中。  
   2.当队列为非空时,循环执行步骤3到步骤5,否则执行6;  
   3.出队列取得一个结点,访问该结点;  
   4.若该结点的左子树为非空,则将该结点的左子树入队列;  
   5.若该结点的右子树为非空,则将该结点的右子树入队列;  
   6.结束。

代码:

/***************************************  
* 时间:2013年12月2日  
* author:lm  
* 内容:二叉树的层次遍历  
***************************************/
import java.util.ArrayDeque;  
import java.util.Queue;
public class BinTree {
private char date;
private BinTree lchild; //左孩子
private BinTree rchild; //右孩子
private BinTree(char c ){
date = c;
}
public static void BFSOrder(BinTree t)
{
if(t==null) return ;
Queue<BinTree> queue = new ArrayDeque<BinTree>();
//队列小知识:使用offer和poll优于add和remove之处在于它们返回值可以判断成功与否,而不抛出异常
queue.offer(t); //进入队列
while(!queue.isEmpty())
{
t=queue.poll(); //当前节点出队列
System.out.print(t.date);
if(t.lchild!=null) //当前节点左孩子去排队,在前面哦
queue.offer(t.lchild);
if(t.rchild!=null) //右孩子排第二
queue.offer(t.rchild);
}
}
public static void main(String[] args) {
BinTree b1 = new BinTree('a');
BinTree b2 = new BinTree('b');
BinTree b3 = new BinTree('c');
BinTree b4 = new BinTree('d');
BinTree b5 = new BinTree('e');
BinTree b6 = new BinTree('f');
BinTree b7 = new BinTree('g');
/**
* a
* / \
* b c
* / \ / \
* d e f g
*/
b1.lchild = b2;
b1.rchild = b3;
b2.lchild = b4;
b2.rchild = b5;
b3.lchild = b6;
b3.rchild = b7;

BinTree.BFSOrder(b1);
System.out.println();
}
}

另外还写了树的三种深度优先遍历的递归与非递归算法:
http://www.cnblogs.com/LZYY/p/3454778.html

Responses