大家好，又见面了，我是你们的朋友全栈君。
实现思路
我们来看看下图的二叉链表 如何实现层序遍历。
层序遍历顺序：ABECDG
A为B、E的双亲结点，遍历顺序是 根->左->右 是不是。
而且每个结点都是这样的遍历顺序 有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队，出队时将其左右孩子入队，循环队列进行出队，每次出队将其左右孩子入队。当队列为空时，整棵树层序遍历完毕。还没明白请看下面过程。
A->出队
队列：E、B
B->出队
队列：D、C、E
E->出队
队列：G、D、C
C->出队
队列：G、D
D->出队
队列：G
G->出队
队列为空，层序遍历完毕。
二叉树层序遍历算法代码
层序遍历函数
层序遍历核心代码，利用了一个自己底层封装的顺序队列。如果想知道怎么实现的呢，请看线性表：顺序队列算法实现。
//一排一排的遍历 利用队列的特性哟，将根结点入队列 然后然后出入队列，出队列后将其左右孩子结点入队列
//直到队列为空
void SeqTraverse(BiTree tree)
{
SeqQueue queue = Init_SeqQueue();
Push_SeqQueue(queue, tree);
while (!IsEmpty_SeqQueue(queue))
{
BiTree root = Pop_SeqQueue(queue);
printf("%c ", root->data);
if (root->lchild)
Push_SeqQueue(queue, root->lchild);
if(root->rchild)
Push_SeqQueue(queue, root->rchild);
}
printf("\n");
}完整代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include "SeqQueue.h"
typedef char ElemType;
typedef struct BiNode
{
ElemType data;
struct BiNode* lchild;
struct BiNode* rchild;
}BiNode, *BiTree;
//创建二叉链表
void CreateBiTree(BiTree* tree)
{
char c;
scanf("%c", &c);
if (c == ' ')
{
*tree = NULL;
return;
}
*tree = malloc(sizeof(BiNode));
(*tree)->data = c;
CreateBiTree(&(*tree)->lchild);
CreateBiTree(&(*tree)->rchild);
return;
}
//二叉链表 递归前序遍历
void PreTraverse(BiTree tree)
{
if (tree == NULL)
{
return;
}
printf("%c ", tree->data);
PreTraverse(tree->lchild);
PreTraverse(tree->rchild);
}
//一排一排的遍历 利用队列的特性哟，将根结点入队列 然后然后出入队列，出队列后将其左右孩子结点入队列
//直到队列为空
void SeqTraverse(BiTree tree)
{
SeqQueue queue = Init_SeqQueue();
Push_SeqQueue(queue, tree);
while (!IsEmpty_SeqQueue(queue))
{
BiTree root = Pop_SeqQueue(queue);
printf("%c ", root->data);
if (root->lchild)
Push_SeqQueue(queue, root->lchild);
if(root->rchild)
Push_SeqQueue(queue, root->rchild);
}
printf("\n");
}
int main(int argc, char *argv[])
{
BiTree tree = NULL;
printf("请前序遍历输入结点：");
CreateBiTree(&tree);
printf("前序遍历：");
PreTraverse(tree);
printf("\n层序遍历：");
SeqTraverse(tree);
return 0;
}
代码运行检测
我们构建如下图的二叉树，注意创建二叉树输入序列为：ABC__D__E_G__，_代表一个空格哟。
运行结果
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/143355.html原文链接：https://javaforall.net
