作者：解学武

我们知道，树是有层次的，比如：

上面这棵树一共有 3 层，根结点位于第一层，以此类推。

所谓层次遍历二叉树，就是从树的根结点开始，一层一层按照从左往右的次序依次访问树中的结点。

二叉树的存储方式有两种，分别是顺序表和链表。对于顺序表存储的二叉树，层次遍历是很容易实现的，因为二叉树中的结点本就是一层一层存储到顺序表中的。唯一需要注意的是，顺序表存储的只能是完全二叉树，普通二叉树必须先转换成完全二叉树后才能存储到顺序表中，因此在实现层次遍历的时候，需要逐个对顺序表中存储的结点进行甄别。

层次遍历用链表存储的二叉树，可以借助队列存储结构实现，具体方案是：

1. 将根结点入队；
2. 从队列的头部提取一个结点并访问它，将该结点的左孩子和右孩子依次入队；
3. 重复执行第 2 步，直至队列为空；

假设将图 1 中的二叉树存储到链表中，那么层次遍历的过程是：

根结点 1 入队（1）；
根结点 1 出队并访问它，然后将 1 的左孩子 2 和右孩子 3 依次入队（3, 2）；
将结点 2 出队并访问它，然后将 2 的左孩子 4 和右孩子 5 依次入队（5,4,3）；
将结点 3 出队并访问它，然后将 3 的左孩子 6 和右孩子 7 依次入队（7,6,5,4）；
根结点 4 出队并访问它，然后将 4 的左孩子（无）和右孩子（无）依次入队（7,6,5）；
将结点 5 出队并访问它，然后将 5 的左孩子（无）和右孩子（无）依次入队（7,6）；
将结点 6 出队并访问它，然后将 6 的左孩子（无）和右孩子（无）依次入队（7）；  
将结点 7 出队并访问它，然后将 6 的左孩子（无）和右孩子（无）依次入队（）；
队列为空，层次遍历结束。 

层次遍历二叉树

对于顺序表存储的二叉树，层次遍历二叉树的 C 语言实现代码为：

#include <stdio.h>
#define NODENUM 7 //二叉树中结点的个数
#define ElemType int
//自定义 BiTree 类型，表示二叉树
typedef ElemType BiTree[NODENUM];
//顺序表存储二叉树
void InitBiTree(BiTree T) {
    ElemType node;
    int i = 0;
    printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");
    while (scanf("%d", &node))
    {
        T[i] = node;
        i++;
    }
}
//层次遍历二叉树
void LevelOrderTraverse(BiTree T) {
    int j;
    //从根结点起,层次遍历二叉树
    for (j = 0; j < NODENUM; j++) {
        //只访问非空结点
        if (T[j] != 0) {
            printf("%d ", T[j]);
        }
    }
}
int main() {
    int res;
    BiTree T = { 0 };
    InitBiTree(T);
    LevelOrderTraverse(T);
    return 0;
}

运行结果为：

按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7 #
1 2 3 4 5 6 7

对于链表存储的二叉树，层次遍历二叉树的 C 语言实现代码为：

#include <stdio.h>
#include <stdlib.h>
#define TElemType int
#define NODENUM 7
//初始化队头和队尾指针开始时都为0
int front = 0, rear = 0;
typedef struct BiTNode {
    TElemType data;//数据域
    struct BiTNode* lchild, * rchild;//左右孩子指针
}BiTNode, * BiTree;
//以先序遍历的方式存储二叉树到链表中
void CreateBiTree(BiTree* T) {
    int num;
    scanf("%d", &num);
    //如果输入的值为 0，表示无此结点
    if (num == 0) {
        *T = NULL;
    }
    else
    {
        //创建新结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = num;
        CreateBiTree(&((*T)->lchild));//创建该结点的左孩子
        CreateBiTree(&((*T)->rchild));//创建该结点的右孩子
    }
}
//入队函数
void EnQueue(BiTree* a, BiTree node) {
    if (rear == NODENUM) {
        printf("队列已满，入队失败\n");
        exit(0);
    }
    a[rear++] = node;
}
//出队函数
BiTNode* DeQueue(BiTNode** a) {
    if (front == rear) {
        printf("队列为空，出队失败\n");
        exit(0);
    }
    return a[front++];
}
//层次遍历二叉树
void LevelOrderTraverse(BiTree T) {
    //如果二叉树存在，才进行层次遍历
    if (T) {
        BiTree a[20] = { 0 };
        BiTree p = NULL;
        p = T;
        //根结点入队
        EnQueue(a, p);
        //重复执行，直至队列为空
        while (front < rear)
        {
            //从队列取出一个结点
            p = DeQueue(a);
            //访问当前结点
            printf("%d ", p->data);
            //将当前结点的左右孩子依次入队
            if (p->lchild) {
                EnQueue(a, p->lchild);
            }
            if (p->rchild) {
                EnQueue(a, p->rchild);
            }
        }
    } 
}
//后序遍历二叉树，释放树占用的内存
void DestroyBiTree(BiTree T) {
    if (T) {
        DestroyBiTree(T->lchild);//销毁左孩子
        DestroyBiTree(T->rchild);//销毁右孩子
        free(T);//释放结点占用的内存
    }
}
int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    LevelOrderTraverse(Tree);
    DestroyBiTree(Tree);
    return 0;
}

运行结果：

1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
1 2 3 4 5 6 7

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。