C语言实现二叉树层次遍历介绍

来自:网络
时间:2022-08-07
阅读:
目录

什么是层次遍历?

对于一颗二叉树来说,从根节点开始,按从上到下、从左到右的顺序访问每一个结点。

注:每一个结点有且访问一次。

那我们如何来实现这个算法呢?

实现原理:

对于二叉树来说,它是一个递归的定义,我们要实现层次遍历必然要满足从上到下、从左到右这个要求,从根结点出发,我们可以将所有意义上的根结点都存储在队列之中,那我们可以使用队列先进先出的特点来实现要求的遍历。

这里我们需要引用队列来实现。

主体代码:

 
BiTree InitTree()//二叉树的创建
{
	BiTree T =(BiTree) malloc(sizeof(Tree));
	char data;
	scanf("%c", &data);
	getchar();
	if (data == '#')//如果data为#则该子树为空值
		return NULL;
	else {
		T->data = data;
		printf("请输入%c的左子树:\n", data);
		T->lchild = InitTree();
		printf("请输入%c的右子树:\n", data);
		T->rchild = InitTree();
	}
	return T;
}
void ShowCengci(BiTree T)
{
	LinkQueue qu;
	InitQueue(&qu);//初始化队列
	enQueue(&qu, T);//根结点入队
	while (QueueEmpty(qu))//判断队列中是否为空
	{
		BiTree S = deQueue(&qu);//根节点出队
		printf("%c ", S->data);
		if (S->lchild != NULL)//判断左右子树是否为空,不为空则入队
		{
			enQueue(&qu, S->lchild);
		}
		if (S->rchild != NULL)
		{
			enQueue(&qu, S->rchild);
		}
	}

队列的链式实现:

typedef struct BTree
{
	char data;
	struct BTree* lchild;
	struct BTree* rchild;
}Tree,*BiTree;
typedef struct Queue
{
	BiTree data;
	struct Queue* next;
}Qnode,*Queueptr;
typedef struct point
{
	Queueptr front;//头指针
	Queueptr rear;//尾指针
}LinkQueue;
 
void InitQueue(LinkQueue* qu)
{
	qu->front = qu->rear = (Queueptr)malloc(sizeof(Qnode));
	if (qu->front == NULL)
		return;
}
void enQueue(LinkQueue* qu, BiTree S)
{
	Queueptr p = (Queueptr)malloc(sizeof(Qnode));
	if (p == NULL) {
		return;
	}
	if (S == NULL)
		return;
	p->data = S;
	p->next = NULL;
	qu->rear->next = p;
	qu->rear = p;
}
int QueueEmpty(LinkQueue qu)
{
	if (qu.front != qu.rear)
		return 1;
	else
		return 0;
}
BiTree deQueue(LinkQueue* qu)
{
	if (qu->front == qu->rear)
		return;
	Queueptr p = qu->front->next;
	BiTree q = p->data;
	qu->front->next = p->next;
	if (qu->rear == p)
		qu->rear = qu->front;
	free(p);
	return q;
}

通关上述代码可以实现对二叉树的层次遍历。

总结

返回顶部
顶部