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

本文已收錄至《數(shù)據(jù)結(jié)構(gòu)(C/C++語(yǔ)言)》專(zhuān)欄！

作者：ARMCSKGT

你的閱讀和理解將是我極大的動(dòng)力！

目錄

前言?

正文

二叉樹(shù)操作的實(shí)現(xiàn)

二叉樹(shù)的前，中，后序遍歷(深度優(yōu)先遍歷)

求二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)

求葉子節(jié)點(diǎn)個(gè)數(shù)

求二叉樹(shù)的深度

二叉樹(shù)的層序遍歷(廣度優(yōu)先遍歷)

二叉樹(shù)的構(gòu)建函數(shù)

二叉樹(shù)的相關(guān)OJ題

判斷完全二叉樹(shù)

判斷平衡二叉樹(shù)

翻轉(zhuǎn)二叉樹(shù)

最后

我們前面了解過(guò)二叉樹(shù)的順序結(jié)構(gòu)那就是堆，但是二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)更重要，在以后的高級(jí)數(shù)據(jù)結(jié)構(gòu)中AVL樹(shù)，二叉搜索樹(shù)等都是基于鏈?zhǔn)蕉鏄?shù)構(gòu)建的，而且現(xiàn)在各大公司對(duì)于二叉樹(shù)知識(shí)的考察也很頻繁，所以掌握鏈?zhǔn)蕉鏄?shù)是必不可少的，學(xué)好了二叉樹(shù)也能極大的鍛煉我們對(duì)遞歸的理解！

二叉樹(shù)操作的實(shí)現(xiàn)

---

二叉樹(shù)的前，中，后序遍歷(深度優(yōu)先遍歷)

• 二叉樹(shù)的前序遍歷

口訣：根左右(先走根節(jié)點(diǎn) 再走左節(jié)點(diǎn) 最后走右節(jié)點(diǎn))。

前序遍歷是先訪(fǎng)問(wèn)根節(jié)點(diǎn)，再訪(fǎng)問(wèn)左子樹(shù)和右子樹(shù)。

// 二叉樹(shù)前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)//root為空則輸出#并停止遞歸
	{
		printf("# ");
		return;
	}
		
	printf("%c ", root->data);//先輸出根節(jié)點(diǎn)
	BinaryTreePrevOrder(root->left);//遞歸左子樹(shù)
	BinaryTreePrevOrder(root->right);//遞歸右子樹(shù)
}

• 二叉樹(shù)的中序遍歷

口訣：左根右(先走左節(jié)點(diǎn) 再走根節(jié)點(diǎn) 最后走右節(jié)點(diǎn))。

中序遍歷是先訪(fǎng)問(wèn)左子樹(shù)，再訪(fǎng)問(wèn)根節(jié)點(diǎn)和右子樹(shù)。

// 二叉樹(shù)中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)//節(jié)點(diǎn)為空停止遞歸并輸出#
	{
		printf("# ");
		return;
	}

	BinaryTreeInOrder(root->left);//先訪(fǎng)問(wèn)左子樹(shù)
	printf("%c ", root->data);//再輸出根節(jié)點(diǎn)
	BinaryTreeInOrder(root->right);//最后訪(fǎng)問(wèn)右子樹(shù)
}

• 二叉樹(shù)的后序遍歷

口訣：左右根(先走左節(jié)點(diǎn) 再走右節(jié)點(diǎn) 最后走根節(jié)點(diǎn))。

后序遍歷是先訪(fǎng)問(wèn)左子樹(shù)和右子樹(shù)，再訪(fǎng)問(wèn)根節(jié)點(diǎn)。

// 二叉樹(shù)后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)//節(jié)點(diǎn)為空輸出#并停止遞歸
	{
		printf("# ");
		return;
	}

	BinaryTreePostOrder(root->left);//先訪(fǎng)問(wèn)子樹(shù)
	BinaryTreePostOrder(root->right);//再訪(fǎng)問(wèn)右子樹(shù)
	printf("%c ", root->data);//最后訪(fǎng)問(wèn)根節(jié)點(diǎn)
}

---

通過(guò)中序序列與前序序列或者中序序列與后序序列就可以確定一棵唯一的二叉樹(shù)，而通過(guò)前序序列和后序序列則不一定！對(duì)于二叉樹(shù)的遍歷，我們采用遞歸去解決，一直到空節(jié)點(diǎn)則停止遞進(jìn)開(kāi)始回歸到主調(diào)函數(shù)！

---

求二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)

求二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)，我們?nèi)匀皇鞘褂眠f歸，將每個(gè)節(jié)點(diǎn)看作一棵樹(shù)，那么根節(jié)點(diǎn)在計(jì)算時(shí)就是左子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)加上右子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)然后加1(根節(jié)點(diǎn)自己)，如果是空節(jié)點(diǎn)則返回0。

// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)//如果為空返回0
	{
		return 0;
	}
	
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
    //返回左子樹(shù)和右子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)加上自己
}

---

求葉子節(jié)點(diǎn)個(gè)數(shù)

求葉子節(jié)點(diǎn)的個(gè)數(shù)，利用遞歸，在遞歸時(shí)當(dāng)碰到節(jié)點(diǎn)的左右子樹(shù)都為空時(shí)則返回1且不再遞歸，空節(jié)點(diǎn)返回0。最后根節(jié)點(diǎn)返回左右子樹(shù)的葉子節(jié)點(diǎn)之和！

// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)//如果左孩子存在右孩子不存在，右子樹(shù)返回0
	{
		return 0;
	}

    //如果左右子樹(shù)都為空則為葉子節(jié)點(diǎn)，返回1
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

    //返回根節(jié)點(diǎn)的左右子樹(shù)葉子節(jié)點(diǎn)之和
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

---

求二叉樹(shù)的深度

求二叉樹(shù)的深度主要是比較左右子樹(shù)那一棵樹(shù)最高，返回最高的那一棵樹(shù)的深度加1(根節(jié)點(diǎn)自己)，通過(guò)遞歸比較每一棵樹(shù)，如果相同則隨意返回左右子樹(shù)的高度即可。

這是一個(gè)典型的大事化小的過(guò)程，函數(shù)先遞歸到葉子節(jié)點(diǎn)，然后逐一返回開(kāi)始比較左右子樹(shù)的高度，最后返回大的高度即是深度！

//求二叉樹(shù)的深度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)//如果遍歷到底則返回0
	{
		return 0;
	}
	
	int leftBT = BinaryTreeDepth(root->left);//獲取左子樹(shù)的深度
	int rightBT = BinaryTreeDepth(root->right);//獲取右子樹(shù)的深度

    //判斷左右子樹(shù)誰(shuí)大返回大值加上自己
	return leftBT >rightBT ? leftBT + 1 : rightBT + 1;
}

---

二叉樹(shù)的層序遍歷(廣度優(yōu)先遍歷)

二叉樹(shù)的層序遍歷借助隊(duì)列來(lái)完成，所謂層序遍歷就是廣度優(yōu)先遍歷，邏輯思想中是一層一層的進(jìn)行遍歷，隊(duì)列的先進(jìn)先出性質(zhì)非常適合層序遍歷，因此層序遍歷不需要遞歸。

層序遍歷的代碼邏輯是根節(jié)點(diǎn)先入隊(duì)，然后節(jié)點(diǎn)出隊(duì)時(shí)讓子節(jié)點(diǎn)入隊(duì)，如果節(jié)點(diǎn)為空則不入隊(duì)，循環(huán)往復(fù)一直到隊(duì)列為空時(shí)層序遍歷結(jié)束。核心思想是父節(jié)點(diǎn)出隊(duì)時(shí)將自己的子節(jié)點(diǎn)帶入隊(duì)列！

// 層序遍歷-借助隊(duì)列
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	
	QueueInit(&q);// 初始化隊(duì)列 
	if (root)//判斷樹(shù)是否為空
	{
		QueuePush(&q, root);//根節(jié)點(diǎn)入隊(duì)
		while (!QueueEmpty(&q))//隊(duì)列不為空則繼續(xù)循環(huán)
		{
			QDataType BT = QueueFront(&q);//取隊(duì)頭元素
			printf("%c ", BT->data);//打印這個(gè)節(jié)點(diǎn)值
			QueuePop(&q);//隊(duì)頭出隊(duì)
			if (BT->left)//當(dāng)前節(jié)點(diǎn)的左孩子如果存在則入隊(duì)
			{
				QueuePush(&q, BT->left);
			}

			if (BT->right)//當(dāng)前節(jié)點(diǎn)的右孩子如果存在則入隊(duì)
			{
				QueuePush(&q, BT->right);
			}
		}
	}
    QueueDestroy(&q);//銷(xiāo)毀隊(duì)列
}

---

二叉樹(shù)的構(gòu)建函數(shù)

在二叉樹(shù)的操作中，樹(shù)的構(gòu)建是必不可少的，二叉樹(shù)的構(gòu)建對(duì)一個(gè)數(shù)組序列進(jìn)行解讀，通過(guò)每一次的解讀決定節(jié)點(diǎn)是否為空，而為空的標(biāo)準(zhǔn)為當(dāng)前數(shù)組元素是 # ，如果當(dāng)前數(shù)組元素是 # 則該節(jié)點(diǎn)為空，每創(chuàng)建完成一個(gè)節(jié)點(diǎn)就會(huì)遞歸去創(chuàng)建該節(jié)點(diǎn)的左右孩子節(jié)點(diǎn)，無(wú)論節(jié)點(diǎn)是否為空都會(huì)遞歸，每創(chuàng)建完一個(gè)節(jié)點(diǎn)后數(shù)組的地址也會(huì)加1走到下一個(gè)元素然后傳遞給遞歸函數(shù)，所以在遞歸時(shí)需要傳遞數(shù)組的指針。這里遞歸的思想類(lèi)似于前序遍歷的思想，所以數(shù)組中存入的是這棵二叉樹(shù)的前序序列！

具體過(guò)程： 1. 判斷數(shù)組當(dāng)前的元素是否為 # 如果為 # 則函數(shù)返回NULL表示該節(jié)點(diǎn)為空。 2. 數(shù)組的地址自加1走到下一個(gè)元素，方便后面遞歸。 3. 申請(qǐng)一個(gè)新節(jié)點(diǎn)，節(jié)點(diǎn)值為當(dāng)前的數(shù)組元素。 4. 傳入當(dāng)前樹(shù)的父節(jié)點(diǎn)和數(shù)組當(dāng)前元素進(jìn)度的地址，遞歸創(chuàng)建左孩子和右孩子。 5. 最后當(dāng)所有節(jié)點(diǎn)創(chuàng)建完成后返回根節(jié)點(diǎn)的地址。

//創(chuàng)建二叉樹(shù)
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	assert(a);
	if (a[*pi] == '#')//如果是#返回空
	{
		(*pi)++;//數(shù)組地址+1走到下一個(gè)元素
		return NULL;//返回空
	}

	//創(chuàng)建新節(jié)點(diǎn)
	BTNode* TreeNode = (BTNode*)malloc(sizeof(BTNode));
	if (!TreeNode)
	{
		perror("malloc Tree fail\n");
		exit(EOF);
	}
	TreeNode->data = a[(*pi)++];//給節(jié)點(diǎn)賦值且數(shù)組地址+1走到下一個(gè)元素
	TreeNode->left = BinaryTreeCreate(a, pi);//遞歸創(chuàng)建左右子樹(shù)
	TreeNode->right = BinaryTreeCreate(a, pi);
	return TreeNode;//返回根節(jié)點(diǎn)的地址
}

二叉樹(shù)的相關(guān)OJ題

---

判斷完全二叉樹(shù)

題目鏈接：958. 二叉樹(shù)的完全性檢驗(yàn) - 力扣（LeetCode）

對(duì)于完全二叉樹(shù)的判斷，我們需要了解完全二叉樹(shù)的特點(diǎn)：完全二叉樹(shù)可以是滿(mǎn)二叉樹(shù)也可以是不滿(mǎn)的二叉樹(shù)，但不滿(mǎn)的二叉樹(shù)的葉子節(jié)點(diǎn)必須是從左到右排列的中間不能間斷！

我們通過(guò)圖片可以發(fā)現(xiàn)，完全二叉樹(shù)的葉子節(jié)點(diǎn)是從左到右連續(xù)的，而非完全二叉樹(shù)的葉子節(jié)點(diǎn)中間則缺失了一個(gè)，這就是我們判斷完全二叉樹(shù)的重要條件！基于完全二叉樹(shù)的這種特性，我們使用層序遍歷，一層一層的檢驗(yàn)，如果二叉樹(shù)是完全二叉樹(shù)那么他的每一層節(jié)點(diǎn)都是連續(xù)的(非空的)，一旦有空節(jié)點(diǎn)則表示所有節(jié)點(diǎn)已經(jīng)都遍歷過(guò)了，后面都是空節(jié)點(diǎn)，所以當(dāng)有節(jié)點(diǎn)時(shí)我們進(jìn)行層序遍歷，一旦碰到空就退出開(kāi)始進(jìn)行檢驗(yàn)，檢驗(yàn)是通過(guò)循環(huán)進(jìn)行排查，如果后面的節(jié)點(diǎn)都為空則是完全二叉樹(shù)，如果在空節(jié)點(diǎn)之后排查到非空的節(jié)點(diǎn)，那么就不是完全二叉樹(shù)！

這里的核心思想就是層序遍歷和完全二叉樹(shù)的特點(diǎn)！

判斷完全二叉樹(shù)的代碼邏輯： 1. 根節(jié)點(diǎn)入隊(duì)，然后出隊(duì)帶入子節(jié)點(diǎn)入隊(duì)。 2. 出隊(duì)的節(jié)點(diǎn)判斷是否為空，如果不為空則將左右孩子入隊(duì)(無(wú)論孩子是否為空節(jié)點(diǎn))。 3. 一旦碰到隊(duì)列中的空節(jié)點(diǎn)則入隊(duì)結(jié)束，開(kāi)始判斷。 4. 利用迭代判斷隊(duì)列中剩余的節(jié)點(diǎn)是否都是空節(jié)點(diǎn)，如果中間有一個(gè)非空節(jié)點(diǎn)則返回false。 5. 如果檢驗(yàn)完成都是空節(jié)點(diǎn)，最后銷(xiāo)毀隊(duì)列返回true。

//完全二叉樹(shù)的判斷---代碼接口來(lái)自力扣第958題
bool isCompleteTree(struct TreeNode* root ) 
{
	Queue q;
	QueueInit(&q);// 初始化隊(duì)列 
    
	if (root)//判斷樹(shù)是否為空
	{
		QueuePush(&q, root);//根節(jié)點(diǎn)入隊(duì)
		while (!QueueEmpty(&q))//隊(duì)列不為空則繼續(xù)循環(huán)
		{
			QDataType BT = QueueFront(&q);//取節(jié)點(diǎn)
			QueuePop(&q);
			
			if (BT)//如果節(jié)點(diǎn)不為空則入隊(duì)--NULL也入隊(duì)
			{
                QueuePush(&q, BT->left);
                QueuePush(&q, BT->right);
			}
            else//如果為空則開(kāi)始判斷是否全部為空節(jié)點(diǎn)(葉子節(jié)點(diǎn)的孩子)
            {
                break;
            }
			
		}
        while(!QueueEmpty(&q))
        {
            QDataType BT = QueueFront(&q);//取節(jié)點(diǎn)
            QueuePop(&q);
            if(BT!=NULL)//如果后面的所有節(jié)點(diǎn)中有一個(gè)不為空則表示不是完全二叉樹(shù)
            {
                QueueDestroy(&q);
                return false;
            }
        }
	}
    QueueDestroy(&q);
	return true;
}

---

判斷平衡二叉樹(shù)

題目鏈接：110. 平衡二叉樹(shù) - 力扣（LeetCode）

平衡二叉樹(shù)是一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn)的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1 。

對(duì)于平衡二叉樹(shù)的判斷，我們采用求深度的辦法去解決，根據(jù)題目意思，那么該樹(shù)的每一層都應(yīng)該只相差1層，如果相差大于1層則不是平衡二叉樹(shù)，所以這里需要借助求二叉樹(shù)深度的函數(shù)來(lái)解決。

判斷平衡二叉樹(shù)代碼思想： 1. 判斷節(jié)點(diǎn)是否為空，為空則返回true停止遞歸！ 2. 求出當(dāng)前父節(jié)點(diǎn)的左右子樹(shù)的深度，如果兩數(shù)的深度只差大于1則不是平衡二叉樹(shù)。 3. 遞歸求每一個(gè)節(jié)點(diǎn)的左右子樹(shù)是否都滿(mǎn)足這個(gè)要求！

//代碼接口來(lái)自力扣題目第110題

//求二叉樹(shù)的深度
int BinaryTreeDepth(struct TreeNode* root)
{
	if (root == NULL)//如果遍歷到底則返回0
	{
		return 0;
	}
	
	int leftBT = BinaryTreeDepth(root->left);//獲取左子樹(shù)的深度
	int rightBT = BinaryTreeDepth(root->right);//獲取右子樹(shù)的深度

	return leftBT >rightBT ? leftBT + 1 : rightBT + 1;//判斷左右子樹(shù)誰(shuí)大返回大值加上自己
}

//一層一層的判斷是否滿(mǎn)足平衡二叉樹(shù)
bool isBalanced(struct TreeNode* root)
{
    if(!root)
        return true;

    int left = BinaryTreeDepth(root->left);
    int right = BinaryTreeDepth(root->right);

    if(abs(left-right)>1)//如果該層的高度差不超過(guò)1就進(jìn)入下一層
        return false;

    return isBalanced(root->left) && isBalanced(root->right);//返回所有層的結(jié)果
}

---

翻轉(zhuǎn)二叉樹(shù)

題目鏈接：226. 翻轉(zhuǎn)二叉樹(shù) - 力扣（LeetCode）

如圖為翻轉(zhuǎn)二叉樹(shù)：

對(duì)于二叉樹(shù)的翻轉(zhuǎn)，我們采用的思想是先遞歸到葉子節(jié)點(diǎn)開(kāi)始從最下面向上翻轉(zhuǎn)，這是一種后序遍歷的思想，當(dāng)遞歸到葉子節(jié)點(diǎn)時(shí)交換左右兩棵子樹(shù)的節(jié)點(diǎn)(無(wú)論是否為空)，然后逐一向上一層一層的遞歸交換。

翻轉(zhuǎn)二叉樹(shù)的代碼思想： 1. 判斷節(jié)點(diǎn)是否為空或是否為葉子節(jié)點(diǎn)，如果為葉子節(jié)點(diǎn)則停止遞歸，返回當(dāng)前的節(jié)點(diǎn)地址！ 2. 后序遍歷遞歸左右子樹(shù)。 3. 遞歸到葉子節(jié)點(diǎn)時(shí)開(kāi)始交換左右子樹(shù)，交換完成后回到父節(jié)點(diǎn)的遞歸函數(shù)再次交換父節(jié)點(diǎn)的左右子樹(shù)，依次遞歸直到回到根節(jié)點(diǎn)時(shí)進(jìn)行最后的交換完成后翻轉(zhuǎn)結(jié)束！

//代碼接口來(lái)自力扣226題

struct TreeNode* invertTree(struct TreeNode* root)
{
    if(!root||(root->left==NULL&&root->right==NULL))//如果樹(shù)為空或者樹(shù)只有一個(gè)節(jié)點(diǎn)則返回空
    {
        return root;
    }

    //后序遍歷思想

    root->left = invertTree(root->left);//左子樹(shù)繼續(xù)遍歷
    root->right = invertTree(root->right);//右子樹(shù)繼續(xù)遍歷

    //開(kāi)始調(diào)換節(jié)點(diǎn)--無(wú)論是否為空都換
    struct TreeNode* leftnode=root->left;
    root->left=root->right;
    root->right=leftnode;
    

    return root;
}

本篇我們介紹了二叉樹(shù)的鏈?zhǔn)綄?shí)現(xiàn)的相關(guān)操作，相對(duì)于前面的數(shù)據(jù)結(jié)構(gòu)，二叉樹(shù)的實(shí)現(xiàn)和理解明顯要難一點(diǎn)，但是其應(yīng)用也更多是我們必須掌握的，這是二叉樹(shù)的基礎(chǔ)知識(shí)，關(guān)于二叉樹(shù)的學(xué)習(xí)還不止于此，還有更多高階的二叉樹(shù)我們后期會(huì)進(jìn)行介紹！

本次二叉樹(shù)的基本知識(shí)就介紹到這里啦，希望能夠盡可能幫助到大家。

如果文章中有瑕疵，還請(qǐng)各位大佬細(xì)心點(diǎn)評(píng)和留言，我將立即修補(bǔ)錯(cuò)誤，謝謝！

博客中的所有代碼合集：二叉樹(shù)的博客代碼及材料 - Gitee.com

🌟其他文章閱讀推薦🌟

數(shù)據(jù)結(jié)構(gòu)初級(jí)＜樹(shù)和二叉樹(shù)的概念＞

">數(shù)據(jù)結(jié)構(gòu)初級(jí)＜隊(duì)列>

C語(yǔ)言初級(jí)＜函數(shù)＞

🌹歡迎讀者多多瀏覽多多支持!🌹

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