阅读:0       作者:解学武

二叉树层次遍历(C语言实现)

我们知道,是有层次的,比如:

1 二叉树的层次

上面这棵树一共有 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