【數(shù)據(jù)結(jié)構(gòu)】二叉樹的基本操作與遍歷（C語言）-創(chuàng)新互聯(lián)

成都創(chuàng)新互聯(lián)主要從事成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)昆都侖,10年網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220

定義

滿二叉樹

完全二叉樹

性質(zhì)

應(yīng)用

計算二叉樹結(jié)點(diǎn)個數(shù)

計算葉子結(jié)點(diǎn)的個數(shù)

第?k 層結(jié)點(diǎn)的個數(shù)

查找值為x的節(jié)點(diǎn)

遍歷

前序遍歷

中序遍歷

后序遍歷

層序遍歷

判斷是否為完全二叉樹

定義

🦄二叉樹是由樹發(fā)展過來的，即度大為2的樹，且子樹有左右之分，可以這么理解，二叉樹是空結(jié)點(diǎn)跟左右子樹的結(jié)合體。

🦄下面這張圖可能更好理解一點(diǎn)，任何二叉樹都是下列幾種情況復(fù)合而成的。因此只要這個樹的度超過?2?，那么它就不是二叉樹。

滿二叉樹

🦄滿二叉樹是一種特殊的二叉樹，即每一層結(jié)點(diǎn)都到達(dá)大值。舉個簡單的例子，假設(shè)這個二叉樹根結(jié)點(diǎn)在?1?層且一共有?i?層，若結(jié)點(diǎn)總數(shù)為(2^i)?-1?個那么這個二叉樹就是滿二叉樹。

完全二叉樹

🦄可以說滿二叉樹也是一種特殊的完全二叉樹，完全二叉樹的底層的結(jié)點(diǎn)的排序從左到右都是連續(xù)的。若假設(shè)下面這張圖里的F結(jié)點(diǎn)還有一個左結(jié)點(diǎn)，那么這個二叉樹就不是完全二叉樹了。

性質(zhì)

1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有?2 ^ (i - 1)?個結(jié)點(diǎn)。
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的大結(jié)點(diǎn)數(shù)是(2 ^ h) - 1。
3. 對任何一棵二叉樹, 如果度為?0?其葉結(jié)點(diǎn)個數(shù)為?n0?, 度為?2?的分支結(jié)點(diǎn)個數(shù)為?n2?,則有??n0＝ n2＋1?。
4. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為?1?，具有?n?個結(jié)點(diǎn)的滿二叉樹的深度，h = log （n +?1）?。(ps：是?log?以2為底，n+1?為對數(shù))
5. 對于具有?n?個結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從?0?開始編號，則對于序號為?i?的結(jié)點(diǎn)有：
1. 若?i>0?，i?位置節(jié)點(diǎn)的雙親為：( i - 1 ) / 2?。
2. 若?2i + 1< n?，左孩子為：2i+1?，2i + 1 >= n否則無左孩子。
3. 若2i + 2< n，右孩子為：2i + 2，2i + 2 >= n否則無右孩子。

應(yīng)用

🦄與堆不同，二叉樹是多個結(jié)點(diǎn)鏈接起來的鏈?zhǔn)浇Y(jié)構(gòu)，因此對應(yīng)其特性，每一個根節(jié)點(diǎn)都指向左右兩個結(jié)點(diǎn)。

typedef int BTdatatype;
typedef struct BinaryTreeNode 
{
	BTdatatype data;                 //數(shù)據(jù)
	struct BinaryTreeNode* left;     //左結(jié)點(diǎn)
	struct BinaryTreeNode* right;    //右結(jié)點(diǎn)

}BTNode;

🦄而這里二叉樹的實現(xiàn)主要依靠的是遞歸，為的便是能夠在訪問完一個子樹后還能返回到它原來的根結(jié)點(diǎn)。

計算二叉樹結(jié)點(diǎn)個數(shù)

🦄這里開始遞歸就初見雛形，需要一次次遞歸遍歷整個二叉樹來計算結(jié)點(diǎn)個數(shù)，通過返回值的方式將數(shù)值統(tǒng)計起來。(若使用全局變量，在多次調(diào)用該函數(shù)的時候就會出現(xiàn)全局變量未初始化的情況而導(dǎo)致結(jié)果出錯)

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;         //遇到空結(jié)點(diǎn)就返回0（代表0個結(jié)點(diǎn)）
	}

	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;  //左右子樹結(jié)點(diǎn)加上自己的總個數(shù)
}

計算葉子結(jié)點(diǎn)的個數(shù)

🦄這題跟上一題類似，但還需要加上一個條件篩選葉子結(jié)點(diǎn)。

// 二叉樹葉子節(jié)點(diǎn)個數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)   //判斷是否為葉子結(jié)點(diǎn)
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); //兩邊葉子結(jié)點(diǎn)的個數(shù)
}

第?k 層結(jié)點(diǎn)的個數(shù)

🦄這題的關(guān)鍵在于對?k?層的檢索，既要找到?k?層的結(jié)點(diǎn)又要在?k?層前遇到空返回，則需要兩個判斷。舉個例子而言，根節(jié)點(diǎn)距離?k?層的長度為?k-1?，即第?2?層的結(jié)點(diǎn)距離?k?層的長度為?k-2?，因此每次進(jìn)一層的時候就把?k--?當(dāng)?k==1?的時候該結(jié)點(diǎn)就是?k?層的結(jié)點(diǎn)，因此只需要統(tǒng)計這些結(jié)點(diǎn)的個數(shù)就可以了。

// 二叉樹第k層節(jié)點(diǎn)個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)                  //空結(jié)點(diǎn)不計數(shù)
	{
		return 0;
	}
	if (k == 1 && root != NULL)        //到k層且結(jié)點(diǎn)不為空則計數(shù)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);  //統(tǒng)合數(shù)量
}

查找值為x的節(jié)點(diǎn)

🦄這題要注意的是對結(jié)點(diǎn)的值的返回，我們都知道一次的結(jié)果并不一定會影響到最終返回的結(jié)果，因此處理好一找到點(diǎn)就立刻返回的方法非常重要。這里就通過對返回值的判斷，只有找到目標(biāo)結(jié)點(diǎn)時才會直接層層返回。

// 二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTdatatype x)
{
	if (root == NULL)
	{
		return 0;                      
	}
	if (root->data == x)               //找到值為x的結(jié)點(diǎn)返回
	{
		return root;
	}
	BTNode* ret1 = BinaryTreeFind(root->left, x);    //往左找x
	if (ret1)                                        //有返回值則繼續(xù)返回
	{ 
		return ret1;
	}

	BTNode* ret2 = BinaryTreeFind(root->right, x);    //往右找x
	if(ret2)                                          //有返回值繼續(xù)返回
	{
		return ret2;
	}
}

遍歷

🦄遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。根據(jù)規(guī)則的不同，二叉樹的遍歷可以分作四種，分別是前序、中序、后序以及層序遍歷。

前序遍歷

傳送門：144.二叉樹的前序遍歷

🦄口訣：根左右，即先訪問根結(jié)點(diǎn)后再依次訪問左右結(jié)點(diǎn)，倒也像一個人從根結(jié)點(diǎn)繞著外圍跑遍了整個二叉樹。

// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)                //為空返回
	{
		printf("NULL ");
		return 0;
	}

	printf("%d ", root->data);         //先打印根節(jié)點(diǎn)的數(shù)據(jù)
	BinaryTreePrevOrder(root->left);   //訪問左子樹
	BinaryTreePrevOrder(root->right);  //訪問右子樹

}

中序遍歷

傳送門：94.二叉樹的中序遍歷

🦄口訣：左根右，中序遍歷則需要先訪問左子樹之后再訪問根結(jié)點(diǎn)，最后才是右子樹。簡單地看就是從左到右依次把結(jié)點(diǎn)拿下來并訪問。

// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)                   //為空返回
	{
		printf("NULL ");
		return 0;
	}

	BinaryTreeInOrder(root->left);   //先訪問左子樹
	printf("%d ", root->data);       //打印根結(jié)點(diǎn)
	BinaryTreeInOrder(root->right);  //再訪問右子樹
}

后序遍歷

傳送門：145.二叉樹的后序遍歷

🦄口訣：左右根?，后序遍歷則是先遍歷兩個子樹之后才是訪問根結(jié)點(diǎn)。即要訪問這個結(jié)點(diǎn)它的左右子樹都必須先遍歷一遍?？梢钥闯梢粋€結(jié)點(diǎn)必須是葉結(jié)點(diǎn)才能對其訪問，若非葉結(jié)點(diǎn)就先訪問并“刪除”左右結(jié)點(diǎn)后讓原結(jié)點(diǎn)變成葉結(jié)點(diǎn)之后再進(jìn)行訪問。

// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)                  //為空返回
	{
		printf("NULL ");
		return 0;
	}

	BinaryTreePostOrder(root->left);   //先遍歷左子樹
	BinaryTreePostOrder(root->right);  //再遍歷右子樹
	printf("%d ", root->data);         //最后打印根結(jié)點(diǎn)
}

層序遍歷

傳送門：102. 二叉樹的層序遍歷

🦄正如其名，層序遍歷就是以層為單位進(jìn)行遍歷。若要實現(xiàn)層序遍歷的話，所需的思想與上面的遍歷就完全不同。因為之前的遍歷是以深度優(yōu)先進(jìn)行的，而層序遍歷需要的是廣度優(yōu)先的遍歷。

🦄為了實現(xiàn)依層遍歷的功能，我們需要使用隊列來輔助實現(xiàn)。第一次傳入的是根結(jié)點(diǎn)，每次訪問完根結(jié)點(diǎn)之后把隊頭刪除，再把隊頭對應(yīng)的左右子樹對應(yīng)的指針傳入隊列之中，根據(jù)隊列先進(jìn)先出的性質(zhì)，所以后傳入的結(jié)點(diǎn)就會較后地被訪問。

typedef BTNode* Qdatatype;
typedef struct Qnode
{
	Qdatatype data;          //數(shù)據(jù)
	struct Queue* next;      //指向下個結(jié)點(diǎn)
}Qnode;

typedef struct Queue
{
	Qnode* head;             //隊列的頭
	Qnode* tail;             //隊列的尾
	int size;                //大小
}Queue;

void Queueinit(Queue* p)
{
	p->head = NULL;           //頭尾結(jié)點(diǎn)制空
	p->tail = NULL;
	p->size = 0;              //數(shù)據(jù)量為0
}

bool QueueEmpty(Queue* p)
{
	assert(p);
	return p->head == NULL || p->tail == NULL;    //二者一個為空則隊列為空
}

void Queuepush(Queue* p, Qdatatype x)
{
	assert(p);                //斷言

	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));   //開辟新結(jié)點(diǎn)
	if (newnode == NULL)              //開辟失敗返回
	{
		perror(malloc);
		exit(-1);
	}
	newnode->data = x;                //賦值
	newnode->next = NULL;
	if (p->head == NULL)              //隊列為空的情況
	{
		p->head = p->tail = newnode;
	}
	else
	{
		p->tail->next = newnode;      //鏈接
		p->tail = newnode;
	}
	p->size++;                        //對size進(jìn)行處理
}

void Queuepop(Queue* p)
{
	assert(p);                      //斷言p不為空
	assert(!QueueEmpty(p));         //斷言隊列不為空

	Qnode* next = p->head->next;    //存儲下一結(jié)點(diǎn)
	free(p->head);                  //釋放當(dāng)先頭結(jié)點(diǎn)
	p->head = next;                 //下一結(jié)點(diǎn)變成頭結(jié)點(diǎn)
	p->size--;                      //對size進(jìn)行處理
}

Qdatatype Queuefront(Queue* p)
{
	assert(p);
	assert(!QueueEmpty(p));         //斷言不為空

	return p->head->data;           //頭結(jié)點(diǎn)存儲的就是隊頭的數(shù)據(jù)
}

void QueueDestroy(Queue* p)
{
	assert(p);

	Qnode* cur = p->head;
	while (cur)
	{
		Qnode* next = cur->next;
		free(cur);
		cur = next;
	}
	p->head = p->tail = NULL;       //頭尾結(jié)點(diǎn)制空
	p->size = 0;                    //大小歸0
}

// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
	assert(root);

	Queue q;
	Queueinit(&q);                    //構(gòu)建隊列
	Queuepush(&q, root);              //根結(jié)點(diǎn)入隊

	while (!QueueEmpty(&q))           //隊列為空遍歷完成
	{
		BTNode* front = Queuefront(&q);  //取隊頭
		printf("%d ",front->data);
		Queuepop(&q);                    //刪隊頭
		if (front->left)
		{
			Queuepush(&q, front->left);  //插入隊頭的左結(jié)點(diǎn)
		}
		if (front->right)
		{
			Queuepush(&q, front->right); //插入隊頭的右結(jié)點(diǎn)
		}
	}
	printf("\n");
	QueueDestroy(&q);                    //銷毀隊列
}

判斷是否為完全二叉樹

🦄這個問題是在層序遍歷的基礎(chǔ)之上實現(xiàn)的，我們知道判斷是否為完全二叉樹的關(guān)鍵在于最后一層前都為滿，最后一層的結(jié)點(diǎn)必須連續(xù)。因此我們可以這樣想，只要層序遍歷直到遇到空指針就停止，之后判斷隊列里面還有沒有非空結(jié)點(diǎn)。若隊列里都是空指針則說明這棵樹為完全二叉樹。

// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root)
{
	assert(root);

	Queue q;
	Queueinit(&q);
	Queuepush(&q, root);

	while (!QueueEmpty(&q))          
	{
		BTNode* front = Queuefront(&q);     //取隊頭
		if (front == NULL)                  //隊頭不為空則繼續(xù)循環(huán)
		{
			break;
		}
		Queuepop(&q);
		Queuepush(&q, front->left);         //插入左右結(jié)點(diǎn)
		Queuepush(&q, front->right);
	}
	
	while (!QueueEmpty(&q))                 
	{
		BTNode* front = Queuefront(&q);      
		if (front != NULL)                  //只要判斷隊列之后還有沒有非空結(jié)點(diǎn)
		{
			QueueDestroy(&q);
			return -1;
		}
		Queuepop(&q);
	}
	QueueDestroy(&q);
	return 1;
}

🦙那么，今天二叉樹的基本操作與遍歷就告一段落，如果這篇文章對你有幫助的話，不妨留下三連支持以下博主，謝謝大家!!!

? ? ? ? ? ? ??

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

分享標(biāo)題：【數(shù)據(jù)結(jié)構(gòu)】二叉樹的基本操作與遍歷（C語言）-創(chuàng)新互聯(lián)
網(wǎng)頁URL：http://www.rwnh.cn/article40/pdieo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、全網(wǎng)營銷推廣、企業(yè)網(wǎng)站制作、移動網(wǎng)站建設(shè)、軟件開發(fā)、定制網(wǎng)站

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

猜你還喜歡下面的內(nèi)容

内射老阿姨1区2区3区4区_久久精品人人做人人爽电影蜜月_久久国产精品亚洲77777_99精品又大又爽又粗少妇毛片

【數(shù)據(jù)結(jié)構(gòu)】二叉樹的基本操作與遍歷（C語言）-創(chuàng)新互聯(lián)