目录
1.定义变量
2.创建一棵树
3.初始化队
4.入队操作
5.判断队列是否为空函数
6.出队操作
7.层次循环遍历，打印结果
7.先序遍历，对比结果
8.主函数调用
9.结果展示
首先，想如何层次的遍历一个二叉树呢？简单思路分为如下几步：
1.要先创建一个二叉树。（二叉树建立可参考上一篇博客）
2.采用队列思想，先进先出。也就是说先要创建一个队列。
3.首先根入队，然后出队，再入队它的左右孩子，然后左孩子出队，再入队左孩子的左右孩子，再出队右孩子，加入右孩子没有左右孩子为空，就什么就不用干，继续出队左孩子的左右孩子，直到所有元素都出完队时，遍历也就结束了。
代码：
1.定义变量
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct TreeNode
{
int data;
struct TreeNode* lchild;
struct TreeNode* rchild;
}TreeNode; //定义树
typedef struct QueueNode
{
TreeNode* node;
struct QueueNode* pre;
struct QueueNode* next;
}; // 定义队
2.创建一棵树
不再详细解释，如果不会看上一篇博客二叉树代码实现。
void creatTree(TreeNode** t,int* index,char* data)
{
char ch;
ch = data[*index];
(*index)++;
if (ch == '#')
*t = NULL;
else
{
*t = (TreeNode*)malloc(sizeof(TreeNode));
assert(*t);
(*t)->data = ch;
creatTree(&((*t)->lchild), index, data);
creatTree(&((*t)->rchild), index, data);
}
}
3.初始化队
QueueNode* initQueue()
{
QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));
assert(Q);
Q->node = NULL;
Q->next =Q;
Q->pre = Q;
return Q;
}
//采用循环双链表队列模式，其它链表也可
4.入队操作
void enQueue(QueueNode* Q,TreeNode* data)
{
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
assert(newnode);
newnode->node = data;
newnode->pre= Q;
newnode->next = Q;
Q->pre->next = newnode;
Q->pre = newnode;
}
5.判断队列是否为空函数
int is_emepty(QueueNode* Q)
{
if (Q->next == NULL)
return 0;
else
return 1;
}
6.出队操作
QueueNode* deQueue(QueueNode* Q)
{
if (is_emepty(Q) == 0)
return NULL;
else
{
QueueNode* node = Q->next;
Q->next->next->pre = Q;
Q->next = Q->next->next;
return node;
}
}
7.层次循环遍历，打印结果
void levelTraverse(QueueNode* Q, TreeNode* T)
{
enQueue(Q, T);
while (is_emepty(Q))
{
QueueNode* node = deQueue(Q);
printf("%c ", node->node->data);
if (node->node->lchild)
enQueue(Q, node->node->lchild);
if (node->node->rchild)
enQueue(Q, node->node->rchild);
}
}
7.先序遍历，对比结果
void preOrder(TreeNode* t)
{
if (t == NULL)
return;
else
{
printf("%c", t->data);
preOrder(t->lchild);
preOrder(t->rchild);
}
}
8.主函数调用
int main()
{
TreeNode* t;
char data[100];
int index = 0;
gets_s(data);
creatTree(&t, &index, data);
preOrder(t);
printf("\n");
QueueNode* q = initQueue();
levelTraverse(q, t);
return 0;
}
9.结果展示
ab##c##
abc
a b c
D:\VS\test.2\树\Debug\树.exe (进程 7660)已退出，代码为 -1073741819。
按任意键关闭此窗口. . .
adc#d####
adcd
a d c d
D:\VS\test.2\树\Debug\树.exe (进程 12196)已退出，代码为 -1073741819。
按任意键关闭此窗口. . .
