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

?二叉樹的鏈式結(jié)構(gòu)

前一篇博客介紹了二叉樹的順序結(jié)構(gòu)，是通數(shù)組來存儲的，這里我們通過創(chuàng)建鏈式結(jié)構(gòu)來存儲，在堆上申請空間，結(jié)構(gòu)如下：

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

?二叉樹的簡單創(chuàng)建

這里我們用最粗暴的方法創(chuàng)建一棵樹，就是一個節(jié)點一個節(jié)點的創(chuàng)建，實現(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;}

如下圖：

?二叉樹的遍歷

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

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

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

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

下面我們來看一下代碼運行結(jié)果：

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

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

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

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

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

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

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

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

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

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

?層序遍歷

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

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

再看一下代碼實現(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);	}}

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

?二叉樹的節(jié)點個數(shù)和高度

?二叉樹的節(jié)點個數(shù)

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

代碼如下：

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

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

?二叉樹的葉子節(jié)點個數(shù)

??問題可以分解為求左子樹葉子節(jié)點個數(shù)+右子樹葉子節(jié)點個數(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);}

運行結(jié)果如下：

?二叉樹第k層節(jié)點個數(shù)

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

代碼實現(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);}

?二叉樹查找值為x的節(jié)點

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

代碼實現(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;}

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

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

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

代碼實現(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);}	

?二叉樹的銷毀

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

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é)

這篇博客就主要介紹了二叉樹的鏈式結(jié)構(gòu)及實現(xiàn)，還有一些相關的問題，二叉樹有關的問題遞歸會用到比較多，因為二叉樹本身就是由遞歸來創(chuàng)建的。今天就介紹到這，喜歡的話，歡迎點贊、支持和指正~