??本篇博客我要來(lái)和大家一起聊一聊數(shù)據(jù)結(jié)構(gòu)中的二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)及相關(guān)的一些問(wèn)題的介紹
??博客代碼已上傳至gitee：https://gitee.com/byte-binxin/data-structure/commit/de7024a7498be71a78c18d22b7a7caee53f3ffb4

?二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)

前一篇博客介紹了二叉樹(shù)的順序結(jié)構(gòu)，是通數(shù)組來(lái)存儲(chǔ)的，這里我們通過(guò)創(chuàng)建鏈?zhǔn)浇Y(jié)構(gòu)來(lái)存儲(chǔ)，在堆上申請(qǐng)空間，結(jié)構(gòu)如下：

typedef char BTDataType;typedef struct BinaryTreeNode{	BTDataType data;	struct BinaryTreeNode* left;	struct BinaryTreeNode* right;}BTNode;

?二叉樹(shù)的簡(jiǎn)單創(chuàng)建

這里我們用最粗暴的方法創(chuàng)建一棵樹(shù)，就是一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的創(chuàng)建，實(shí)現(xiàn)代碼如下：

BTNode* CreatBinaryTree(){    BTNode* treeNode1 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode2 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode3 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode4 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode5 = (BTNode*)malloc(sizeof(BTNode));	BTNode* treeNode6 = (BTNode*)malloc(sizeof(BTNode));	treeNode1->data = "A";	treeNode2->data = "B";	treeNode3->data = "C";	treeNode4->data = "D";	treeNode5->data = "E";	treeNode6->data = "F";	treeNode1->left = treeNode2;	treeNode1->right = treeNode3;	treeNode2->left = treeNode4;	treeNode2->right = treeNode5;	treeNode3->left = treeNode6;	treeNode3->right = NULL;	treeNode4->left = treeNode4->right = NULL;	treeNode5->left = treeNode5->right = NULL;	treeNode6->left = treeNode6->right = NULL;}

如下圖：

?二叉樹(shù)的遍歷

?前序遍歷（遞歸實(shí)現(xiàn)）

?這里我先給大家介紹一下用遞歸實(shí)現(xiàn)，后面我會(huì)給大家介紹如何用棧模擬實(shí)現(xiàn)非遞歸。
?前序遍歷指的是先遍歷根，再遍歷左子樹(shù)，再遍歷右子樹(shù)。
?思想： 二叉樹(shù)本身就是一種遞歸結(jié)構(gòu)，所以通過(guò)遞歸來(lái)遍歷這棵樹(shù)，如何遞歸遍歷呢？
是這樣的，先遍歷根，再遍歷左子樹(shù)，左子樹(shù)又可以分解為，根、左子樹(shù)和右子樹(shù)，直到把所以左子樹(shù)的部分遍歷完，然后就遍歷右子樹(shù)，右子樹(shù)又可以分解為，根、左子樹(shù)和右子樹(shù)。
假如我們構(gòu)建了一個(gè)PrevOrder，這個(gè)函數(shù)是可以實(shí)現(xiàn)前序遍歷的，所以我們先遍歷根，剩下的左子樹(shù)和右子樹(shù)遍歷就交給這個(gè)函數(shù)去實(shí)現(xiàn)。
遞歸就是把一個(gè)大的問(wèn)題一直分解，直到分解為最后一個(gè)小問(wèn)題來(lái)解決，這就是所謂的大事化小。

了解了上面那些，我們就來(lái)看一下代碼是如何實(shí)現(xiàn)的，

void BinaryTreePrevOrder(BTNode* root){    // 遍歷到NULL就返回	if (root == NULL)	{		printf("NULL ");		return;	}  	// 先遍歷根	printf("%c ", root->data);	// 左子樹(shù)交給BinaryTreePrevOrder這個(gè)函數(shù)去遍歷	BinaryTreePrevOrder(root->left);	// 右子樹(shù)交給BinaryTreePrevOrder這個(gè)函數(shù)去遍歷	BinaryTreePrevOrder(root->right);}

下面我們來(lái)看一下代碼運(yùn)行結(jié)果：

?中序遍歷（遞歸實(shí)現(xiàn)）

?中序遍歷指的是先遍歷左子樹(shù)，再遍歷根，再遍歷右子樹(shù)。
?思想： 二叉樹(shù)本身就是一種遞歸結(jié)構(gòu)，所以通過(guò)遞歸來(lái)遍歷這棵樹(shù)，如何遞歸遍歷呢？
是這樣的，先遍歷左子樹(shù)，左子樹(shù)又可以分解為，左子樹(shù)、根和右子樹(shù)，直到把所以左子樹(shù)的部分遍歷完，然后就遍歷根，再遍歷右子樹(shù)，右子樹(shù)又可以分解為，左子樹(shù)、根和右子樹(shù)。
如下圖：

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

void BinaryTreeInOrder(BTNode* root){	// 遍歷到NULL就返回	if (root == NULL)	{		printf("NULL ");		return;	}	// 左子樹(shù)交給BinaryTreePrevOrder這個(gè)函數(shù)去遍歷	BinaryTreeInOrder(root->left);	// 遍歷根	printf("%c ", root->data);	// 右子樹(shù)交給BinaryTreePrevOrder這個(gè)函數(shù)去遍歷	BinaryTreeInOrder(root->right);}

代碼運(yùn)行結(jié)果如下：

?后序遍歷（遞歸實(shí)現(xiàn)）

?中序遍歷指的是先遍歷左子樹(shù)，再遍歷根，再遍歷右子樹(shù)。
?思想： 二叉樹(shù)本身就是一種遞歸結(jié)構(gòu)，所以通過(guò)遞歸來(lái)遍歷這棵樹(shù)，如何遞歸遍歷呢？
是這樣的，先遍歷左子樹(shù)，左子樹(shù)又可以分解為，左子樹(shù)、右子樹(shù)和根，直到把所以左子樹(shù)的部分遍歷完，然后遍歷右子樹(shù)，右子樹(shù)又可以分解為，左子樹(shù)、右子樹(shù)和根,最后遍歷根。
如下圖：

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

void BinaryTreePostOrder(BTNode* root){	if (root == NULL)	{		printf("NULL ");		return;	}	// 左子樹(shù)交給BinaryTreePrevOrder這個(gè)函數(shù)去遍歷	BinaryTreePostOrder(root->left);	// 右子樹(shù)交給BinaryTreePrevOrder這個(gè)函數(shù)去遍歷	BinaryTreePostOrder(root->right);	//遍歷根	printf("%c ", root->data);}

代碼運(yùn)行結(jié)果如下：

?層序遍歷

? 層序遍歷： 設(shè)二叉樹(shù)的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹(shù)的根節(jié)點(diǎn)出發(fā)，首先訪問(wèn)第一層的樹(shù)根節(jié)點(diǎn)，然后從左到右訪問(wèn)第2層上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問(wèn)樹(shù)的結(jié)點(diǎn)的過(guò)程就是層序遍歷。

層序遍歷用到的是隊(duì)列來(lái)解決，先將根入隊(duì)，然后把根取出，取出的同時(shí)分別再把不為空的左節(jié)點(diǎn)和右節(jié)點(diǎn)入隊(duì)，直到隊(duì)列為空時(shí)就說(shuō)明二叉樹(shù)已經(jīng)遍歷完了。為了方便大家理解我在這里做了個(gè)動(dòng)圖演示一下：

再看一下代碼實(shí)現(xiàn)如下：

void BinaryTreeLevelOrder(BTNode* root){	if (root == NULL)	{		printf("NULL");		return;	}	queue<BTNode*>q;	q.push(root);	while (!q.empty())	{		BTNode* front = q.front();		q.pop();		printf("%c ", front->data);		if (front->left)			q.push(front->left);		if (front->right)			q.push(front->right);	}}

代碼運(yùn)行結(jié)果如下：

?二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)和高度

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

?此問(wèn)題可以分解為求左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)節(jié)點(diǎn)個(gè)數(shù)+1，然后左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)又可以繼續(xù)分，所以這里可以用遞歸來(lái)求解這個(gè)問(wèn)題，下面我們就來(lái)實(shí)現(xiàn)一下這個(gè)接口

代碼如下：

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

代碼運(yùn)行結(jié)果如下：

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

??問(wèn)題可以分解為求左子樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)，也是一個(gè)遞歸的問(wèn)題，這里就直接實(shí)現(xiàn)了。

代碼如下：

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);}

運(yùn)行結(jié)果如下：

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

??求解第k層節(jié)點(diǎn)個(gè)數(shù)其實(shí)就是求解左子樹(shù)的第k-1層節(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)的第k-1層節(jié)點(diǎn)個(gè)數(shù)，當(dāng)k==1時(shí)，就可以直接返回1，節(jié)點(diǎn)為空就返回0。

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

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

?二叉樹(shù)查找值為x的節(jié)點(diǎn)

?這里我們只需要前序遍歷一遍二叉樹(shù)即可，直到找到x就返回。

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

BTNode* BinaryTreeFind(BTNode* root, BTDataType x){	if (root == NULL)		return NULL;	if (root->data == x)		return root;	BTNode* leftRet = BinaryTreeFind(root->left, x);	if (leftRet)		return leftRet;	BTNode* rightRet = BinaryTreeFind(root->right, x);	if (rightRet)		return rightRet;}

?二叉樹(shù)的創(chuàng)建與銷毀

?二叉樹(shù)的創(chuàng)建

?問(wèn)題： 通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"
給定一串字符串，#代表的是空樹(shù)，其他的都是節(jié)點(diǎn)。
這里我們只需要前序遍歷這串字符串來(lái)構(gòu)建這棵樹(shù)即可。
同樣是用遞歸來(lái)解決這個(gè)問(wèn)題
treeNode->left = BinaryTreeCreate(s, pi); 讓當(dāng)前這個(gè)節(jié)點(diǎn)的左指向給遞歸構(gòu)建左子樹(shù)
**treeNode->right = BinaryTreeCreate(s, pi);**讓當(dāng)前這個(gè)節(jié)點(diǎn)的右指向給遞歸構(gòu)建左子樹(shù)
如果當(dāng)前節(jié)點(diǎn)為空就直接返回NULL。

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

BTNode* BinaryTreeCreate(BTDataType* s, int* pi){	if (s[*pi] == "#")	{		(*pi)++;		return NULL;	}	BTNode* treeNode = (BTNode*)malloc(sizeof(BTNode));	treeNode->data = s[(*pi)++];	treeNode->left = BinaryTreeCreate(s, pi);	treeNode->right = BinaryTreeCreate(s, pi);}	

?二叉樹(shù)的銷毀

?二叉樹(shù)的銷毀我們可以通過(guò)層序遍歷來(lái)把節(jié)點(diǎn)逐個(gè)釋放掉，由于與上面的層序遍歷很相似，這里就不過(guò)多介紹了，直接上代碼

void BinaryTreeDestory(BTNode** root){	if (*root == NULL)		return;	queue<BTNode*>q;	q.push(*root);	while (!q.empty())	{		BTNode* front = q.front();		q.pop();				if (front->left)			q.push(front->left);		if (front->right)			q.push(front->right);		free(front);		front = NULL;	}}

?總結(jié)

這篇博客就主要介紹了二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)及實(shí)現(xiàn)，還有一些相關(guān)的問(wèn)題，二叉樹(shù)有關(guān)的問(wèn)題遞歸會(huì)用到比較多，因?yàn)槎鏄?shù)本身就是由遞歸來(lái)創(chuàng)建的。今天就介紹到這，喜歡的話，歡迎點(diǎn)贊、支持和指正~