什么是层次遍历？
对于一颗二叉树来说，从根节点开始，按从上到下、从左到右的顺序访问每一个结点。
注：每一个结点有且访问一次。
那我们如何来实现这个算法呢？
实现原理：
对于二叉树来说，它是一个递归的定义，我们要实现层次遍历必然要满足从上到下、从左到右这个要求，从根结点出发，我们可以将所有意义上的根结点都存储在队列之中，那我们可以使用队列先进先出的特点来实现要求的遍历。
这里我们需要引用队列来实现。
主体代码：
BiTree InitTree()//二叉树的创建
{
BiTree T =(BiTree) malloc(sizeof(Tree));
char data;
scanf("%c", &data);
getchar();
if (data == '#')//如果data为#则该子树为空值
return NULL;
else {
T->data = data;
printf("请输入%c的左子树:\n", data);
T->lchild = InitTree();
printf("请输入%c的右子树:\n", data);
T->rchild = InitTree();
}
return T;
}
void ShowCengci(BiTree T)
{
LinkQueue qu;
InitQueue(&qu);//初始化队列
enQueue(&qu, T);//根结点入队
while (QueueEmpty(qu))//判断队列中是否为空
{
BiTree S = deQueue(&qu);//根节点出队
printf("%c ", S->data);
if (S->lchild != NULL)//判断左右子树是否为空，不为空则入队
{
enQueue(&qu, S->lchild);
}
if (S->rchild != NULL)
{
enQueue(&qu, S->rchild);
}
}队列的链式实现：
typedef struct BTree
{
char data;
struct BTree* lchild;
struct BTree* rchild;
}Tree,*BiTree;
typedef struct Queue
{
BiTree data;
struct Queue* next;
}Qnode,*Queueptr;
typedef struct point
{
Queueptr front;//头指针
Queueptr rear;//尾指针
}LinkQueue;
void InitQueue(LinkQueue* qu)
{
qu->front = qu->rear = (Queueptr)malloc(sizeof(Qnode));
if (qu->front == NULL)
return;
}
void enQueue(LinkQueue* qu, BiTree S)
{
Queueptr p = (Queueptr)malloc(sizeof(Qnode));
if (p == NULL) {
return;
}
if (S == NULL)
return;
p->data = S;
p->next = NULL;
qu->rear->next = p;
qu->rear = p;
}
int QueueEmpty(LinkQueue qu)
{
if (qu.front != qu.rear)
return 1;
else
return 0;
}
BiTree deQueue(LinkQueue* qu)
{
if (qu->front == qu->rear)
return;
Queueptr p = qu->front->next;
BiTree q = p->data;
qu->front->next = p->next;
if (qu->rear == p)
qu->rear = qu->front;
free(p);
return q;
}通关上述代码可以实现对二叉树的层次遍历。
总结
到此这篇关于C语言实现二叉树层次遍历介绍的文章就介绍到这了,更多相关C语言二叉树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
