对于二叉树来说,层次遍历可以说是很平常的,但由于其应用广泛,比如可以用来求二叉树的高度和宽度,因而非常重要。对于任何一个程序员来说掌握都是必须的。
非常简单,利用队列来进行遍历。初始若根结点不为空则将其入队,在队列不为空下进行循环,出队一个元素并访问他,若其左孩子不空,将其左孩子入队。若其右孩子不空,将其右孩子入队。如此进行下去直到队列为空,遍历结束。
- /**
- * 定义二叉树结构
- * @author Fairy2016
- *
- */
- class BiTree {
- int data;
- BiTree lchild;
- BiTree rchild;
- }
- /**
- * 定义队列结构
- * @author Fairy2016
- *
- */
- class Queue {
- BiTree data[];
- int front;
- int rear;
- }
- /**
- * 二叉树层次遍历算法
- * @author Fairy2016
- *
- */
- public class LayerThrough {
- //根据给定序列,建立完全二叉树
- public static BiTree CreateCompleteBiTree(int a[], int n) {
- BiTree nodes[] = new BiTree[n];
- //初始化各结点
- for(int i = 0; i < n; i++) {
- nodes[i] = new BiTree();
- nodes[i].data = a[i];
- nodes[i].lchild = nodes[i].rchild = null;
- }
- //将各结点按照完全二叉树的关系连起来(其实就是奇左偶右)
- for(int i = 1; i <= n/2; i++) {
- nodes[i-1].lchild = nodes[2*i-1];
- if(2*i < n) {
- nodes[i-1].rchild = nodes[2*i];
- }
- }
- //返回根结点
- return nodes[0];
- }
- //层次遍历
- public static void LayerOrder(BiTree T) {
- if(T == null) {
- return;
- }
- //队列初始化
- Queue Q = new Queue();
- Q.front = Q.rear = -1;
- Q.data = new BiTree[100];
- Q.data[++Q.rear] = T;//根结点入队
- while(Q.rear != Q.front) {
- BiTree p = Q.data[++Q.front];//出队
- System.out.print(p.data+" ");//访问
- if(p.lchild != null) {
- Q.data[++Q.rear] = p.lchild;//左孩子入队
- }
- if(p.rchild != null) {
- Q.data[++Q.rear] = p.rchild;//右孩子入队
- }
- }
- }
- public static void main(String args[]) {
- int a[] = {1,2,3,4,5,6,7,8};
- int n = 8;
- BiTree T = CreateCompleteBiTree(a, n);
- LayerOrder(T);
- }
- }