二叉树的层序遍历
一、定义
所谓二叉树的层次遍历，是指从二叉树的第一层(根节点开始)自上而下逐层遍历，同层内按照从左至右的顺序逐个结点访问。
由二叉树层次遍历的要求可知，当一层访问完之后，按该层结点访问的次序，再对各结点的左、右孩子进行访问（即对下一层从左到右进行访问），这一访问的特点是：先访问的结点其孩子也将先访问，后访问的结点其孩子也将后访问，这与队列的操作控制特点吻合，因此在层次遍历的算法中，将应用队列进行结点访问次序的控制。
上述二叉树的层次遍历序列为:ABCDEFG
二、算法思想
- 首先根节点入队，当队列非空时，重复如下两步操作。
- 对头结点出队，并访问出对结点
- 出队结点的左、右孩子依次入队。
三、算法实现
//二叉树的层次遍历
void LevelOrder(BiTreeNode *root,LQueue *Q)
{
BiTreeNode *p;
QueueAppend(Q,root);
while (QueueNotEmpty(*Q)) {
QueueDelete(Q,&p);
Visit(p->data);
if (p->leftchild != NULL) QueueAppend(Q, p->leftchild);
if (p->rightchild != NULL)QueueAppend(Q, p->rightchild);
}
}
四、完整代码
BiTree.h头文件(包含了其他的算法，也可以看看)
#pragma once
#include<malloc.h>
//#include"Squeue.h"
typedef struct Node {
DataType data;//数据域
struct Node *leftchild;//左子树指针
struct Node *rightchild;//右子树指针
}BiTreeNode;
//typedef struct BiTreeNode * Element;
typedef struct qnode {
BiTreeNode* data;
struct qnode *next;
}LQNode;
typedef struct {
LQNode *front;//队头指针
LQNode *rear;//队尾指针
}LQueue;
//初始化
void Initiate(BiTreeNode **root) {
*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
(*root)->leftchild = NULL;
(*root)->rightchild = NULL;
}
//做插入结点
//若当前结点curr非空，则在curr的左子树插入元素值为x的新节点
//原curr所指结点的左子树成为新插入结点的左子树
//若插入成功，则返回新插入结点的指针，否则返回空指针
BiTreeNode* InsertLeftNode(BiTreeNode *curr, DataType x) {
BiTreeNode *s, *t;
if (curr == NULL) {
return NULL;
}
else {
t = curr->leftchild;//保存原来curr所指结点的左子树指针
s = (BiTreeNode*)malloc(sizeof(BiTreeNode));
s->data = x;
s->leftchild = t;//新插入结点的左子树成为为原来curr所指结点的左子树
s->rightchild = NULL;
curr->leftchild = s;//新结点成为curr的左子树
return curr->leftchild;//返回新插入结点的指针
}
}
//右插入结点
//若当前结点curr为空，则在curr的右子树插入元素值为x的新结点
//原curr所指结点的右子树成为新插入结点的右子树
//若插入成功，则返回新插入结点的指针，否则放回空指针
BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) {
BiTreeNode *s, *t;
if (curr == NULL) {
return NULL;
}
else {
t = curr->rightchild;//保存原curr所指结点的右子树指针
s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data = x;
s->rightchild = t;//新插入结点的右子树为原curr的右子树
s->leftchild = NULL;
curr->rightchild = s;//新结点成为curr的右子树
return curr->rightchild;//返回新插入结点的指针
}
}
//撤销二叉树操作设计
void Destroy(BiTreeNode **root) {
if ((*root) != NULL && (*root)->leftchild != NULL) {
Destroy(&(*root)->leftchild);
}
if ((*root) != NULL && (*root)->rightchild != NULL) {
Destroy(&(*root)->rightchild);
}
free(*root);
}
//左删除子树
//若左子树非空，则删除curr所指结点的左子树
//若删除成功，则返回删除结点的双亲结点指针，否则返回空指针
BiTreeNode *DeleteLeftTree(BiTreeNode *curr) {
if (curr == NULL || curr->leftchild == NULL) {
return NULL;
}
else {
Destroy(&curr->leftchild);
curr->leftchild = NULL;
return curr;
}
}
//右删除子树
//若curr非空，则删除curr所指结点的右子树
//若删除成功，则返回删除结点的双亲结点指针，否则返回空指针
BiTreeNode *DeleteRightTree(BiTreeNode *curr) {
if (curr == NULL || curr->rightchild == NULL) {
return NULL;
}
else {
Destroy(&curr->rightchild);
curr->rightchild = NULL;
return curr;
}
}
void Visit(DataType item) {
printf("%c ", item);
}
//前序遍历二叉树，访问操作为Visit()函数
void PreOrder(BiTreeNode *root, void Visit(DataType item)) {
if (root != NULL) {
Visit(root->data);
PreOrder(root->leftchild, Visit);
PreOrder(root->rightchild, Visit);
}
}
//中序遍历二叉树，访问操作为Visit()函数
void InOrder(BiTreeNode *root, void Visit(DataType item)) {
if (root != NULL) {
InOrder(root->leftchild, Visit);
Visit(root->data);
InOrder(root->rightchild, Visit);
}
}
//后续遍历二叉树，访问操作为Visit()函数
void PostOrder(BiTreeNode *root, void Visit(DataType item)) {
if (root != NULL) {
PostOrder(root->leftchild, Visit);
PostOrder(root->rightchild, Visit);
Visit(root->data);
}
}
//打印二叉树
void PrintBiTree(BiTreeNode *root, int n) {
//逆时针旋转90度打印二叉树root,n为缩进层数，初始值为0
int i;
if (root == NULL) {//递归出口
return;
}
PrintBiTree(root->rightchild, n + 1);//遍历打印右子树
//访问根节点
for (i = 0; i < n - 1; i++) {
printf(" ");
}
if (n > 0) {
printf("---");
printf("%c\n", root->data);
}
PrintBiTree(root->leftchild, n + 1);//遍历打印左子树
}
//查找数据元素
BiTreeNode *Search(BiTreeNode *root, DataType x) {
//查找数据元素x是否再二叉树root中
//查找到则返回该结点指针，未找到则返回空指针
BiTreeNode *find = NULL; //初始标记为查找失败
if (root != NULL) {
if (root->data == x) {
find = root;
}
else {
find = Search(root->leftchild, x);//在左子树中查找
if (find == NULL) {
find = Search(root->rightchild, x);//在右子树中找
}
}
}
return find;//返回查找标记
}
//统计二叉树结点总数
int Count(BiTreeNode *T)
{
if (T == NULL) {
return 0;
}
else {
return Count(T->leftchild) + Count(T->rightchild) + 1;
}
}
//输出二叉树中的叶子结点
void InOrder(BiTreeNode *T)//实际上是root->leftchild,root是头节点
{
if (T) {
InOrder(T->leftchild);
if (T->leftchild == NULL && T->rightchild == NULL) {
printf("%c ", T->data);
}
InOrder(T->rightchild);
}
}
//统计二叉树中的叶子节点数目
int Leaf(BiTreeNode *T)
{
int nl, nr;
if (T == NULL)
return 0;
if ((T->leftchild == NULL) && (T->rightchild == NULL)) {
return 1;
}
nl = Leaf(T->leftchild);//递归求左子树的叶子树
nr = Leaf(T->rightchild);//递归求右子树的叶子树
return (nl + nr);
}
//统计二叉树中度为2的结点数目
int leaf_2(BiTreeNode *T) {
if (T == NULL) {
return 0;
}
if ((T->leftchild != NULL) && (T->rightchild != NULL)) {
return (leaf_2(T->leftchild) + leaf_2(T->rightchild) + 1);
}
else {
return 0;
}
}
//计算二叉树中度为1的结点总数
int leaf_1(BiTreeNode *T) {
if (T==NULL) {
return 0;
}
if ((T->leftchild == NULL && T->rightchild != NULL) || (T->leftchild != NULL && T->rightchild == NULL))
{
return 1 + leaf_1(T->leftchild) + leaf_1(T->rightchild);
}
return leaf_1(T->leftchild) + leaf_1(T->rightchild);
}
//交换二叉树中各个节点的左右子树
void swap(BiTreeNode *T) {
BiTreeNode *temp;
if (T == NULL) {
return;
}
else {
temp = T->leftchild;
T->leftchild = T->rightchild;
T->rightchild = temp;
swap(T->leftchild);
swap(T->rightchild);
}
}
//初始化
void QueueInitiate(LQueue *Q)
{
Q->front = NULL;
Q->rear = NULL;
}
//非空否
int QueueNotEmpty(LQueue Q)
{
if (Q.front == NULL)
return 0;
else
return 1;
}
//入队列
void QueueAppend(LQueue *Q, BiTreeNode* x)
{
LQNode *p;
p = (LQNode *)malloc(sizeof(LQNode));
p->data = x;
p->next = NULL;
if (Q->rear != NULL)//队列原来非空时，队尾加新节点
Q->rear->next = p;
Q->rear = p; //修改队尾指针
if (Q->front == NULL) //队列原来为空时修改队头指针
Q->front = p;
}
//出队列
int QueueDelete(LQueue *Q, BiTreeNode* *d)
{
LQNode *p;
if (Q->front == NULL) {
printf("队列已空无数据元素出队列!\n");
return 0;
}
else {
*d = Q->front->data;
p = Q->front;
Q->front = Q->front->next;//出队列结点脱链
if (Q->front == NULL) Q->rear = NULL;//删除最后一个结点，要将尾指针置空
free(p);
return 1;
}
}
//二叉树的层次遍历
void LevelOrder(BiTreeNode *root,LQueue *Q)
{
BiTreeNode *p;
QueueAppend(Q,root);
while (QueueNotEmpty(*Q)) {
QueueDelete(Q,&p);
Visit(p->data);
if (p->leftchild != NULL) QueueAppend(Q, p->leftchild);
if (p->rightchild != NULL)QueueAppend(Q, p->rightchild);
}
}
.cpp文件
#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
#include"BiTree.h"
//#include"Squeue.h"
int main() {
BiTreeNode *root, *p, *find;
char x = 'E';
Initiate(&root);
p = InsertLeftNode(root, 'A');
p = InsertLeftNode(p, 'B');
p = InsertLeftNode(p, 'D');
p = InsertRightNode(p, 'G');
p = InsertRightNode(root->leftchild, 'C');
InsertLeftNode(p, 'E');
InsertRightNode(p, 'F');
printf("打印二叉树:\n");
PrintBiTree(root, 0);
printf("前序遍历: ");
PreOrder(root->leftchild, Visit);
printf("\n中序遍历: ");
InOrder(root->leftchild, Visit);
printf("\n后序遍历: ");
PostOrder(root->leftchild, Visit);
find = Search(root, x);
if (find != NULL) {
printf("\n数据元素%c在二叉树中", x);
}
else {
printf("\n数据元素%c不在二叉树中", x);
}
int count = Count(root->leftchild);
printf("\n二叉树中的结点总数为%d\n", count);
printf("二叉树的叶子结点为:");
InOrder(root->leftchild);
printf("\n");
int leaf = Leaf(root->leftchild);
printf("二叉树中的叶子节点数目为:%d\n", leaf);
int leaf2 = leaf_2(root->leftchild);
printf("二叉树中度为2的结点数目为:%d\n", leaf2);
int leaf1 = leaf_1(root->leftchild);
printf("二叉树中度为1的结点数目为:%d\n", leaf1);
/*交换二叉树各结的左右子树*/
/*swap(root->leftchild);
printf("前序遍历: ");
PreOrder(root->leftchild, Visit);
*/
printf("\n");
printf("层次遍历:\n");
LQueue Q;
QueueInitiate(&Q);
LevelOrder(root->leftchild,&Q);
Destroy(&root);
return 0;
system("pause");
}
