二叉樹的層次遍歷（C語言）-創(chuàng)新互聯(lián)

一、二叉樹的概念以及結(jié)構(gòu)

二叉樹是n(n>=0)個(gè)節(jié)點(diǎn)的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為根節(jié)點(diǎn)的左子樹和右子樹組。

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、微信平臺(tái)小程序開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了烏爾禾免費(fèi)建站歡迎大家使用！

二、二叉樹的遍歷圖解 先序遍歷

中序遍歷

后序遍歷

層次遍歷

三、代碼部分 一、頭文件 二、二叉樹的結(jié)構(gòu) 三、隊(duì)列的結(jié)構(gòu) 四、隊(duì)列的初始化 五、判斷隊(duì)列是否為空 六、添加元素 七、刪除元素 八、創(chuàng)建結(jié)點(diǎn) 九、創(chuàng)建二叉樹 十、層次遍歷 十一、主函數(shù) 十二、全部代碼 十三、測試結(jié)果

一、頭文件

#include#include#include#define MAXSIZE 5

二、二叉樹的結(jié)構(gòu)

//二叉樹的結(jié)構(gòu) 
typedef struct BTnode
{
	char element;
	struct BTnode *left;
	struct BTnode *right;	
}*BTnodePtr;

三、隊(duì)列的結(jié)構(gòu)

//隊(duì)列
typedef struct BTNodePtrQueue
{
	BTnodePtr *nodePtrs;
	int front;
	int rear;
}*QueuePtr;

四、隊(duì)列的初始化

//初始化隊(duì)列
QueuePtr initQueue()
{
	QueuePtr resultPtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultPtr->nodePtrs = (BTnodePtr*)malloc(MAXSIZE * (sizeof(BTnodePtr)));
	resultPtr->front = 0;
	resultPtr->rear = 1;
	return resultPtr;	
}

五、判斷隊(duì)列是否為空

int isQueueEmpty(QueuePtr paraQueuePtr)
{
	if ((paraQueuePtr->front + 1) % MAXSIZE == paraQueuePtr->rear) 
	{
		return 1;
	}

	return 0;
}

六、添加元素

//在隊(duì)列中添加元素
void enqueue(QueuePtr Queue,BTnodePtr newBTnodePtr)
{
	if((Queue->rear +1)%MAXSIZE == (Queue->front)%MAXSIZE )
	{
		printf("The queue is full.\n");
		return ; 
	}	
	Queue->nodePtrs [Queue->rear] = newBTnodePtr;
	Queue->rear = (Queue->rear+1)%MAXSIZE;
	printf("enqueue %c ends.\r\n", newBTnodePtr->element);
		
}

七、刪除元素

//刪除元素
BTnodePtr deQueue(QueuePtr Queue)
{
	if(isQueueEmpty(Queue))
	{
		printf("The queue is empty,can not delete.\n");
		return ;
	}
	Queue->front = (Queue->front +1)%MAXSIZE;
	printf("delete %c ends.\n",Queue->nodePtrs [Queue->front]->element);

	return  Queue->nodePtrs [Queue->front];
}

八、創(chuàng)建結(jié)點(diǎn)

//創(chuàng)建結(jié)點(diǎn) 
BTnodePtr constructBTnode(char newElement)
{
	BTnodePtr newPtr = (BTnodePtr)malloc(sizeof(struct BTnode));
	newPtr->element = newElement;
	newPtr->left = NULL;
	newPtr->right  = NULL;
	return newPtr;
}

九、創(chuàng)建二叉樹

//創(chuàng)建二叉樹
BTnodePtr stringToBTree(char *newString)
{
	int i;
	char ch;
	i = 0;
	QueuePtr Queue = initQueue();
	
	BTnodePtr resultHeader;
	BTnodePtr tempParent,tempLeftChlid,tempRightChild;
	
	ch = newString[i];
	resultHeader = constructBTnode(ch);
	enqueue(Queue,resultHeader);
	
	while(!isQueueEmpty(Queue))
	{
		tempParent = deQueue(Queue);
		//左 
		i++;
		if(newString[i] == '#')
		{
			tempParent->left = NULL;
		}
		else
		{
			tempLeftChlid = constructBTnode(newString[i]);
			enqueue(Queue,tempLeftChlid);
			tempParent->left = tempLeftChlid;
		}
		//右
		i++;
		if(newString[i] == '#')
		{
			tempParent->right = NULL;
		}
		else
		{
			tempRightChild = constructBTnode(newString[i]);
			enqueue(Queue,tempRightChild);
			tempParent->right = tempRightChild;
		}
		
	 } 
	return resultHeader;	
}

十、層次遍歷

//層次遍歷
void levelwise(BTnodePtr newTreePtr)
{
	char string[100];
	int i = 0;
	
	QueuePtr Queue = initQueue();
	BTnodePtr tempNodePtr;
	
	enqueue(Queue,newTreePtr);
	while(!isQueueEmpty(Queue))
	{
		tempNodePtr = deQueue(Queue);
		string[i] = tempNodePtr->element ;
		i++;
		if(tempNodePtr->left != NULL)
		{
			enqueue(Queue,tempNodePtr->left);
		}
		if(tempNodePtr->right  != NULL)
		{
			enqueue(Queue,tempNodePtr->right);
		}
	}
	string[i] = '\0';
	printf("levewise:%s",string);
}

十一、主函數(shù)

int main(){
	BTnodePtr tempHeader;
	char* tempString = "acde#bf######";

	tempHeader = stringToBTree(tempString);
	printf("Levelwise: ");
	levelwise(tempHeader);
	printf("\r\n");

	return 1;
}

十二、全部代碼

include#include#include#define MAXSIZE 5

//二叉樹的結(jié)構(gòu) 
typedef struct BTnode
{
	char element;
	struct BTnode *left;
	struct BTnode *right;	
}*BTnodePtr;
//隊(duì)列
typedef struct BTNodePtrQueue
{
	BTnodePtr *nodePtrs;
	int front;
	int rear;
}*QueuePtr;
//初始化隊(duì)列
QueuePtr initQueue()
{
	QueuePtr resultPtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultPtr->nodePtrs = (BTnodePtr*)malloc(MAXSIZE * (sizeof(BTnodePtr)));
	resultPtr->front = 0;
	resultPtr->rear = 1;
	return resultPtr;	
} 
int isQueueEmpty(QueuePtr paraQueuePtr)
{
	if ((paraQueuePtr->front + 1) % MAXSIZE == paraQueuePtr->rear) 
	{
		return 1;
	}

	return 0;
}
//在隊(duì)列中添加元素
void enqueue(QueuePtr Queue,BTnodePtr newBTnodePtr)
{
	if((Queue->rear +1)%MAXSIZE == (Queue->front)%MAXSIZE )
	{
		printf("The queue is full.\n");
		return ; 
	}	
	Queue->nodePtrs [Queue->rear] = newBTnodePtr;
	Queue->rear = (Queue->rear+1)%MAXSIZE;
	printf("enqueue %c ends.\r\n", newBTnodePtr->element);
		
} 
//刪除元素
BTnodePtr deQueue(QueuePtr Queue)
{
	if(isQueueEmpty(Queue))
	{
		printf("The queue is empty,can not delete.\n");
		return ;
	}
	Queue->front = (Queue->front +1)%MAXSIZE;
	printf("delete %c ends.\n",Queue->nodePtrs [Queue->front]->element);

	return  Queue->nodePtrs [Queue->front];
} 
//創(chuàng)建結(jié)點(diǎn) 
BTnodePtr constructBTnode(char newElement)
{
	BTnodePtr newPtr = (BTnodePtr)malloc(sizeof(struct BTnode));
	newPtr->element = newElement;
	newPtr->left = NULL;
	newPtr->right  = NULL;
	return newPtr;
}
//創(chuàng)建二叉樹
BTnodePtr stringToBTree(char *newString)
{
	int i;
	char ch;
	i = 0;
	QueuePtr Queue = initQueue();
	
	BTnodePtr resultHeader;
	BTnodePtr tempParent,tempLeftChlid,tempRightChild;
	
	ch = newString[i];
	resultHeader = constructBTnode(ch);
	enqueue(Queue,resultHeader);
	
	while(!isQueueEmpty(Queue))
	{
		tempParent = deQueue(Queue);
		//左 
		i++;
		if(newString[i] == '#')
		{
			tempParent->left = NULL;
		}
		else
		{
			tempLeftChlid = constructBTnode(newString[i]);
			enqueue(Queue,tempLeftChlid);
			tempParent->left = tempLeftChlid;
		}
		//右
		i++;
		if(newString[i] == '#')
		{
			tempParent->right = NULL;
		}
		else
		{
			tempRightChild = constructBTnode(newString[i]);
			enqueue(Queue,tempRightChild);
			tempParent->right = tempRightChild;
		}
		
	 } 
	return resultHeader;	
}
//層次遍歷
void levelwise(BTnodePtr newTreePtr)
{
	char string[100];
	int i = 0;
	
	QueuePtr Queue = initQueue();
	BTnodePtr tempNodePtr;
	
	enqueue(Queue,newTreePtr);
	while(!isQueueEmpty(Queue))
	{
		tempNodePtr = deQueue(Queue);
		string[i] = tempNodePtr->element ;
		i++;
		if(tempNodePtr->left != NULL)
		{
			enqueue(Queue,tempNodePtr->left);
		}
		if(tempNodePtr->right  != NULL)
		{
			enqueue(Queue,tempNodePtr->right);
		}
	}
	string[i] = '\0';
	printf("levewise:%s",string);
} 

int main(){
	BTnodePtr tempHeader;
	char* tempString = "acde#bf######";

	tempHeader = stringToBTree(tempString);
	printf("Levelwise: ");
	levelwise(tempHeader);
	printf("\r\n");

	return 1;
}

十三、測試結(jié)果

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱：二叉樹的層次遍歷（C語言）-創(chuàng)新互聯(lián)
文章分享：http://www.muchs.cn/article30/depcpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、電子商務(wù)、網(wǎng)站策劃、微信公眾號(hào)、面包屑導(dǎo)航、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

外貿(mào)網(wǎng)站建設(shè)