二叉树的层次遍历

前言

对于二叉树来说，层次遍历可以说是很平常的，但由于其应用广泛，比如可以用来求二叉树的高度和宽度，因而非常重要。对于任何一个程序员来说掌握都是必须的。

思路

非常简单，利用队列来进行遍历。初始若根结点不为空则将其入队，在队列不为空下进行循环，出队一个元素并访问他，若其左孩子不空，将其左孩子入队。若其右孩子不空，将其右孩子入队。如此进行下去直到队列为空，遍历结束。

Codes

/**
 * 定义二叉树结构
 * @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);
    }
}