当前位置:   article > 正文

二叉树的层序遍历(C语言实现)_二叉树的层序遍历c语言

二叉树的层序遍历c语言

层序遍历代码思路

借助一个辅助队列。

  • 先将二叉树的根结点入队,
  • 然后出队,访问出队结点,
    • 若它有左子树,则将左子树根节点入队;
    • 若它有右子树,则将右子树根节点入队。
    • 然后出队,
    • 访问出队结点……如此反复,直到队列为空
void LevelOrder(BiTree T)
{
	InitQueue(&Q);	// 初始化辅助队列
	BiTree p;
	EnQueue(&Q, T);	// 将根节点入队
	while(!IsEmpty(Q))	// 队列不空则循环 
	{
		DeQueue(Q, p);	// 队头结点出队
		visit(p);
		if (p->lchild != NULL)
		{
			EnQueue(Q, p->lchild);	// 左子树不空,则左子树根节点入队 
		}
		if (p->rchild != NULL)
		{
			EnQueue(Q, p->rchild);	// 右子树不空,则右子树根节点入队 
		} 
	} 
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

实现过程

根据上面的代码思路,需要实现两个数据结构,一个二叉树,一个队列,需要实现的功能有

  • 二叉树、队列的数据结构定义
  • 二叉树的创建、队列的初始化
  • 二叉树的层序遍历、队列的出队、入队操作

代码实现

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>

using namespace std;

typedef char TElemType;

const int MAXSIZES = 50;

// 二叉树的存储结构 
typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

typedef BiTree QElemType;

// 队列的存储结构 
typedef struct {
	QElemType data[MAXSIZES];
	int front;
	int rear;
}SqQueue;

// 通过前序遍历创建二叉树 
void CreateBiTree(BiTree *T)
{
	TElemType ch;
	scanf("%c", &ch);
	if (ch == '#')
	{
		*T = NULL;
	}
	else
	{
		*T = (BiTree) malloc(sizeof(BiTNode));
		if (!T)
		{
			exit(0);
		}
		(*T)->data = ch;
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}

// 初始化队列 
void InitQueue(SqQueue *Q)
{
	Q->front = Q->rear = 0;
}

// 辅助队列的入队操作 
void EnQueue(SqQueue *Q, QElemType q)
{
	if ((Q->rear + 1) % MAXSIZES == Q->front)
		return;
	Q->data[Q->rear] = q;
	Q->rear = (Q->rear + 1) % MAXSIZES;
}

// 辅助队列的出队操作 
void DeQueue(SqQueue *Q, QElemType *q)
{
	if (Q->front == Q->rear)
		return;
	*q = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZES;
}

// 二叉树的中序遍历 
void InOrderTraverse(BiTree T)
{
	if (!T)
	{
		return;
	}
	
	InOrderTraverse(T->lchild);
	printf("%c", T->data);
	InOrderTraverse(T->rchild);
}

// 二叉树的层序遍历 
void LevelOrder(BiTree T)
{
	SqQueue Q;
	InitQueue(&Q);	// 初始化辅助队列
	BiTree p;
	EnQueue(&Q, T);	// 将根节点入队
	while(Q.front != Q.rear)	// 队列不空则循环 
	{
		DeQueue(&Q, &p);	// 队头结点出队
		printf("%c", p->data);
		if (p->lchild != NULL)
		{
			EnQueue(&Q, p->lchild);	// 左子树不空,则左子树根节点入队 
		}
		if (p->rchild != NULL)
		{
			EnQueue(&Q, p->rchild);	// 右子树不空,则右子树根节点入队 
		} 
	} 
}

int main()
{
	BiTree t;
	printf("请按照前序扩展二叉树进行输入:(#表示空结点)\n");
	CreateBiTree(&t);
	printf("中序遍历: "); 
	InOrderTraverse(t);
	printf("\n层序遍历: "); 
	LevelOrder(t);
	
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117

参考:
层序遍历思路来《王道数据结构》

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/846515
推荐阅读
相关标签
  

闽ICP备14008679号