??紙上得來終覺淺， 絕知此事要躬行。
??主頁：June-Frost
??專欄：數(shù)據(jù)結(jié)構(gòu)

??該文章主要講述二叉樹的遞歸結(jié)構(gòu)及分治算法的思想。

??前言：

?為了實(shí)現(xiàn)二叉樹的基本操作以及更好的了解二叉樹的結(jié)構(gòu)，先手動(dòng)創(chuàng)造一個(gè)鏈?zhǔn)蕉鏄洹?/p>

#include<stdio.h>
#include<stdlib.h>

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	int val;
}BTNode;

BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->left = NULL;
	node->right = NULL;
	node->val = x;
	return node;
}
int main()
{
	//創(chuàng)建節(jié)點(diǎn)
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);
	//建立關(guān)系
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node3->left = node5;
	node3->right = node6;
	node4->right = node7;

	return 0;
}

?創(chuàng)建出來的結(jié)構(gòu)：

??創(chuàng)建出來的這棵二叉樹將為后續(xù)的遍歷和分治做準(zhǔn)備.

?? 二叉樹的遍歷

? 遍歷操作可以快速熟悉二叉樹的遞歸結(jié)構(gòu)，二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對(duì)二叉樹中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。

?如果二叉樹不為空樹，就需要看成三部分，即 根節(jié)點(diǎn)，根節(jié)點(diǎn)的左子樹、根節(jié)點(diǎn)的右子樹，這樣就滿足了遞歸結(jié)構(gòu)：

??由于二叉樹滿足遞歸結(jié)構(gòu)，所以按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：

• 前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。即順序?yàn)椋焊?、左子樹、右子樹。

• 中序遍歷(Inorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）。即順序?yàn)椋鹤笞訕洹⒂易訕?、根?/p>

• 后序遍歷(Postorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。即順序?yàn)椋鹤笞訕?、右子樹、根?/p>

??按照創(chuàng)建的二叉樹，遍歷的順序?yàn)椋?br>

?? 前序遍歷

代碼實(shí)現(xiàn)：

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}

動(dòng)圖展示：

前序遍歷遞歸圖解：

?? 中序遍歷

代碼實(shí)現(xiàn)：

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

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

動(dòng)圖展示：

? 注意：對(duì)于這個(gè)動(dòng)圖的白色箭頭為遞歸調(diào)用和結(jié)束，紅色箭頭是左子樹部分調(diào)用結(jié)束之后打印節(jié)點(diǎn)的時(shí)機(jī)。

?? 后續(xù)遍歷

代碼實(shí)現(xiàn)：

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

動(dòng)圖展示：

? 注意：對(duì)于這個(gè)動(dòng)圖的白色箭頭為遞歸調(diào)用和結(jié)束，紅色箭頭是右子樹部分調(diào)用結(jié)束之后打印節(jié)點(diǎn)的時(shí)機(jī)。

?? 分治

?分治思想是一種解決問題的方法，本質(zhì)是一種管理，它的核心思想是將一個(gè)復(fù)雜的問題分解成若干個(gè)較小的子問題，然后分別解決這些子問題，最后將子問題的解合并得到原問題的解。這種思想在計(jì)算機(jī)科學(xué)、數(shù)學(xué)和工程領(lǐng)域都有廣泛應(yīng)用。
?分治思想的優(yōu)點(diǎn)在于它可以有效地減少問題的復(fù)雜度，提高算法的效率。同時(shí)，它還可以提高代碼的可讀性和可維護(hù)性，因?yàn)榭梢詫栴}分解成更小的部分，更容易理解和修改。

?? 一些例子

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

節(jié)點(diǎn)情況：

• 如果是空節(jié)點(diǎn)，返回0。
• 如果不是空節(jié)點(diǎn)，則返回該節(jié)點(diǎn)的左子樹的節(jié)點(diǎn)數(shù)+右子樹的節(jié)點(diǎn)個(gè)數(shù)+1(自己這個(gè)節(jié)點(diǎn))。

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

?這個(gè)代碼的訪問順序其實(shí)就是后序遍歷。

② 二叉樹葉子節(jié)點(diǎn)個(gè)數(shù)

節(jié)點(diǎn)情況：

• 如果是空，返回0。
• 如果是葉子，返回1。
• 不是葉子也不是空，就返回該節(jié)點(diǎn)左子樹的葉子數(shù) + 右子樹的葉子數(shù)。

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

③ 二叉樹第k層節(jié)點(diǎn)個(gè)數(shù)

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right, k - 1);
}

?? 結(jié)語

?文章到這里就結(jié)束了，如果對(duì)你有幫助，你的點(diǎn)贊將會(huì)是我的最大動(dòng)力，如果大家有什么問題或者不同的見解，歡迎大家的留言~文章來源地址http://www.zghlxwxcb.cn/news/detail-717896.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】深入探討二叉樹的遍歷和分治思想(一)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！