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

?二叉樹的鏈式結構

前一篇博客介紹了二叉樹的順序結構，是通數組來存儲的，這里我們通過創建鏈式結構來存儲，在堆上申請空間，結構如下：

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

?二叉樹的簡單創建

這里我們用最粗暴的方法創建一棵樹，就是一個節點一個節點的創建，實現代碼如下：

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

如下圖：

?二叉樹的遍歷

?前序遍歷（遞歸實現）

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

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

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

下面我們來看一下代碼運行結果：

?中序遍歷（遞歸實現）

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

代碼實現如下：

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

代碼運行結果如下：

?后序遍歷（遞歸實現）

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

代碼實現如下：

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

代碼運行結果如下：

?層序遍歷

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

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

再看一下代碼實現如下：

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

代碼運行結果如下：

?二叉樹的節點個數和高度

?二叉樹的節點個數

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

代碼如下：

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

代碼運行結果如下：

?二叉樹的葉子節點個數

??問題可以分解為求左子樹葉子節點個數+右子樹葉子節點個數，也是一個遞歸的問題，這里就直接實現了。

代碼如下：

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層節點個數

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

代碼實現如下：

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的節點

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

代碼實現如下：

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

?二叉樹的創建與銷毀

?二叉樹的創建

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

代碼實現如下：

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

?二叉樹的銷毀

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

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

?總結

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