1.什么是层序遍历？

就是将一颗树按照每一层每一层的方式进行遍历

例如这棵树，进行层序遍历的结果应该是

那么我们该怎样去实现呢？

2.实现思路

利用队列先进先出的思想去实现

重要思想：一层带一层

我们先把书的根节点入进去，然后每出一次都把它的子节点入队，出子节点时也一样

3.代码实现

因为我们用的是c来实现，所以在实现前请准备好一个队列

队列头文件

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>struct rootnode;
typedef struct rootnode* datatype;typedef struct Queen
{struct Queen* next;datatype data;
}Queen;typedef struct Q
{Queen* head;Queen* tail;
}Q;void QueenInit(Q* ps);void Queenpush(Q* ps, datatype x);
void Queenpop(Q* ps);bool Queenempty(Q* ps);datatype Queenfront(Q* ps);

队列的实现

#include "Queen.h"void QueenInit(Q* ps)
{ps->head = ps->tail = NULL;
}void Queenpush(Q* ps, datatype x)
{Queen* newnode = (Queen*)malloc(sizeof(Queen));newnode->data = x;newnode->next = NULL;if (ps->head == NULL){ps->head = newnode;ps->tail = newnode;}else{ps->tail->next = newnode;ps->tail = newnode;}
}void Queenpop(Q* ps)
{assert(ps);assert(ps->head);if (ps->head->next == NULL){free(ps->head);ps->head = NULL;}else{Queen* next = ps->head->next;free(ps->head);ps->head = next;}
}bool Queenempty(Q* ps)
{assert(ps);return ps->head == NULL;
}datatype Queenfront(Q* ps)
{assert(ps);return ps->head->data;
}

有了队列之后我们来实现层序遍历

void Level_order(root* p)
{Q q;//创建队列QueenInit(&q);//实现队列的初始化if (p)//如果根不为空，先入根Queenpush(&q, p);while (!Queenempty(&q))//如果此时队列不为空，进行循环{root* front = Queenfront(&q);//取出队列的头Queenpop(&q);printf("%c", front->data);//打印if (front->left)//如果此时结点的左子数不为空则入{Queenpush(&q, front->left);}if (front->right)//如果此时结点的右子数不为空则入{Queenpush(&q, front->right);}}
}