🎉🎉想快速入門資料結構，推薦訂閱作者的初階資料結構專欄！此專欄預計更新：順序表，鏈表，堆疊，佇列，二叉樹，排序演算法等等

🎉🎉初階資料結構我們通過c語言實作，所以此專欄也可以幫助大家鞏固大家的c語言知識

🎉🎉源代碼已上傳至我的碼云

前言

我們在上篇文章中已經介紹了二叉樹的相關性質及其應用，點我直達上一篇文章

然而，在實際應用中，單純地講二叉樹的增刪查改是沒有意義的

因為存盤和訪問資料，將會變得特別的困難，因為二叉樹是一種層次結構，需要遞回來定義，在哪一點添加洗掉？這將變成一個最大的問題

二叉樹的增刪查改僅僅在搜索二叉樹和AVL樹中有應用，但由于它們的實作比較復雜，將在后續的專欄中進行講解

但我們實際在很多oj題中需要多二叉樹進行遍歷操作，所以我們在這篇文章中不講解增刪查改，只講解一些基礎的操作

分治思想
二叉樹的各種操作使用的分治的思想，就是將大事化小，小事化了

舉一個形象的例子：

你是某個學校的校長，需要統計你學校的總學生數

但如果你一個個的數的話，那作業量將會非常巨大

所以你可以這么分解問題：

將每個院的院長叫來，讓他們統計每個院的人數

院長同樣會將每個輔導員叫過來，安排任務

輔導員叫班主任，班主任叫班長

在這里班長已經不可拆分了，就可以依次往上上報了

最好，你只需要將每個院的結果加起來，就得到了學校的總人數

在解決二叉樹的問題中，我們也用到了一樣的思想：根就像我們的校長，要執行某個任務，可以安排給左子樹和右子樹進行，而左子樹和右子樹又可以把任務安排給它們的子樹，，，

二叉樹的定義

我們這里采用鏈式定義的方式，一個結構體來定義一個結點，分別存放資料，指向左孩子的指標和指向右孩子的指標

typedef int BTDataType;

typedef struct BinTreeNode
{
	struct BinTreeNode* left;
	struct BinTreeNode* right;
	BTDataType data;
}BTNode;

為了以下內容的講解，我們先寫一個函式來創建一棵簡單的樹

BTNode* createBinTree()
{
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;
	n7->data = 7;

	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;
	n3->left = n6;
	n3->right = NULL;
	n4->left = n7;
	n4->right = NULL;
	n5->left = NULL;
	n5->right = NULL;
	n6->left = NULL;
	n6->right = NULL;
	n7->left = NULL;
	n7->right = NULL;

	return n1;
}

創建出來就是這樣的一棵樹

遍歷操作

緒論

二叉樹我們采用遞回的方式來遍歷，基本思想就是訪問根，左子樹，右子樹，再訪問左子樹的根，左子樹的左子樹，左子樹的右子樹，，，依次往下

根據訪問順序的不一樣，將它們分為以下幾種遍歷順序

1. 前序遍歷：訪問根，左子樹，右子樹
2. 中序遍歷：訪問左子樹，根，右子樹
3. 后序遍歷：訪問左子樹，右子樹，根

以下將具體舉例

前序遍歷

記得要始終先訪問每棵樹不論是哪棵子樹的根，然后繼續往下操作
直接上圖解：

根據遞回的思想，我們可以直接寫出代碼

記住遞回的幾個要素：遞回終止條件和遞回繼續的條件

void PrevOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL");//終止條件，為空直接回傳
		return;
	}

	printf("%d ", root->data);//訪問根部

	PrevOrder(root->left);//訪問左子樹
	PrevOrder(root->right);//訪問右子樹
}

遞回展開圖

中序遍歷

中序遍歷就是總是先訪問完左子樹后再訪問根和右子樹

還是以前面那棵樹為例

代碼實作

void InOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);//與前序遍歷的區別僅僅是將根部的訪問放在中間
	InOrder(root->right);
}

后序遍歷

與前面的思想基本差不多，這里就不詳細闡述了

void PostOrder(BTNode* root)
{
	if (!root)
	{
		printf("NULL");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

二叉樹求結點個數

我們可以利用開始說到的思想，將問題分配給每個結點的下級，讓他們分配任務

首先，如果是空樹，或者走到葉子結點的下級了（葉子結點的下級為空）就回傳0

然后就轉換為左結點的個數+右結點的個數+1（跟結點自己）

int BinTreeSize(BTNode* root)
{
	return !root ? 0 : 1 + BinTreeSize(root->left) + BinTreeSize(root->right);
}

二叉樹求葉子結點的個數

葉子結點的特征是它的左右子樹為空

根據這個特征可以判斷，還是一樣，數出左右子樹的葉子結點個數加起來即可

int BinTreeLeafSize(BTNode* root)
{
	if (!root)
		return 0;
	return root->left == NULL && root->right == NULL ? 1 : BinTreeLeafSize(root->left) + BinTreeLeafSize(root->right);
}

二叉樹求第K層結點個數

這里同樣用到分治思想

如果是空樹或者到葉子結點的下一層，回傳0

如果只有一層的話，也就是只有一個根結點，就回傳1

問題轉化成求第左子樹第一層結點個數+右子樹第一層結點個數

不斷往下分解即可，直到求到需要的層數

int BinTreeLevelKSize(BTNode* root, int k)
{
	//回傳第K層結點個數
	assert(k >= 0);
	if (!root)
		return 0;
	if (k == 1)
		return 1;
	return BinTreeLevelKSize(root->left, k - 1) + BinTreeLevelKSize(root->right, k - 1);
	
}

二叉樹求最大深度

問題分解為求出左右子樹中的較大深度+1（根結點占1個深度）

為了防止函式呼叫過多，用變數保存左右子樹的深度

int BinTreeDepth(BTNode* root)
{
	if (!root)
		return 0;
	//函式呼叫頻繁
	//return BinTreeDepth(root->left) > BinTreeDepth(root->right) ? 1 + BinTreeDepth(root->left) : 1 + BinTreeDepth(root->right);

	//用變數保存

	int leftDepth = BinTreeDepth(root->left);
	int rightDepth = BinTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

二叉樹回傳某個指定結點

還是從左右子樹中找

BTNode* BinTreeFind(BTNode* root, BTDataType x)
{
	if (!root)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* Left = BinTreeFind(root->left, x);
	if (Left)
		return Left;
	BTNode* Right = BinTreeFind(root->right, x);
	if (Right)
		return Right;
	return NULL;
}