C語(yǔ)言實(shí)現(xiàn)二叉樹(shù)層次遍歷介紹

更新時(shí)間：2022年01月20日 14:43:52 作者：愛(ài)學(xué)代碼的學(xué)生

大家好，本篇文章主要講的是C語(yǔ)言實(shí)現(xiàn)二叉樹(shù)層次遍歷介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下

什么是層次遍歷？

對(duì)于一顆二叉樹(shù)來(lái)說(shuō)，從根節(jié)點(diǎn)開(kāi)始，按從上到下、從左到右的順序訪問(wèn)每一個(gè)結(jié)點(diǎn)。

注：每一個(gè)結(jié)點(diǎn)有且訪問(wèn)一次。

那我們?nèi)绾蝸?lái)實(shí)現(xiàn)這個(gè)算法呢？

實(shí)現(xiàn)原理：

對(duì)于二叉樹(shù)來(lái)說(shuō)，它是一個(gè)遞歸的定義，我們要實(shí)現(xiàn)層次遍歷必然要滿(mǎn)足從上到下、從左到右這個(gè)要求，從根結(jié)點(diǎn)出發(fā)，我們可以將所有意義上的根結(jié)點(diǎn)都存儲(chǔ)在隊(duì)列之中，那我們可以使用隊(duì)列先進(jìn)先出的特點(diǎn)來(lái)實(shí)現(xiàn)要求的遍歷。

這里我們需要引用隊(duì)列來(lái)實(shí)現(xiàn)。

主體代碼：

 
BiTree InitTree()//二叉樹(shù)的創(chuàng)建
{
	BiTree T =(BiTree) malloc(sizeof(Tree));
	char data;
	scanf("%c", &data);
	getchar();
	if (data == '#')//如果data為#則該子樹(shù)為空值
		return NULL;
	else {
		T->data = data;
		printf("請(qǐng)輸入%c的左子樹(shù):\n", data);
		T->lchild = InitTree();
		printf("請(qǐng)輸入%c的右子樹(shù):\n", data);
		T->rchild = InitTree();
	}
	return T;
}
void ShowCengci(BiTree T)
{
	LinkQueue qu;
	InitQueue(&qu);//初始化隊(duì)列
	enQueue(&qu, T);//根結(jié)點(diǎn)入隊(duì)
	while (QueueEmpty(qu))//判斷隊(duì)列中是否為空
	{
		BiTree S = deQueue(&qu);//根節(jié)點(diǎn)出隊(duì)
		printf("%c ", S->data);
		if (S->lchild != NULL)//判斷左右子樹(shù)是否為空，不為空則入隊(duì)
		{
			enQueue(&qu, S->lchild);
		}
		if (S->rchild != NULL)
		{
			enQueue(&qu, S->rchild);
		}
	}

隊(duì)列的鏈?zhǔn)綄?shí)現(xiàn)：

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;
}

通關(guān)上述代碼可以實(shí)現(xiàn)對(duì)二叉樹(shù)的層次遍歷。