??博客主頁： 小鎮(zhèn)敲碼人
??熱門專欄：數(shù)據(jù)結(jié)構(gòu)與算法
?? 歡迎關(guān)注：??點(diǎn)贊 ????留言 ??收藏
?? 任爾江湖滿血骨，我自踏雪尋梅香。 萬千浮云遮碧月，獨(dú)傲天下百堅(jiān)強(qiáng)。 男兒應(yīng)有龍騰志，蓋世一意轉(zhuǎn)洪荒。 莫使此生無痕度，終歸人間一捧黃。??????
?? 什么？你問我答案，少年你看，下一個十年又來了 ?? ?? ??

?? 樹

樹是一種數(shù)據(jù)結(jié)構(gòu)，和它的名字很像，樹這種數(shù)據(jù)結(jié)構(gòu)就像倒著的樹。

?? 樹的幾個基本概念

1. 節(jié)點(diǎn)： 像上圖一樣存儲一些值的圓圈就叫節(jié)點(diǎn)。
2. 根節(jié)點(diǎn)：根節(jié)點(diǎn)是一種比較特殊的節(jié)點(diǎn)，它位于樹的最頂部，就像樹的根一樣，所以叫根節(jié)點(diǎn)。
3. 節(jié)點(diǎn)的度：一個節(jié)點(diǎn)有幾個子樹，它的度就為幾，如上圖節(jié)點(diǎn)A的度為3。
4. 樹的度： 一棵樹中，最大的節(jié)點(diǎn)的度稱作樹的度，如上圖，樹的度為3.
5. 節(jié)點(diǎn)的層次：從根開始定義，根為第一層，以此類推。
6. 樹的深度：樹中節(jié)點(diǎn)的最大層次。如上圖節(jié)點(diǎn)的最大層次為4。
7. 孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱作這個節(jié)點(diǎn)的子節(jié)點(diǎn)。如上圖節(jié)點(diǎn)A的子節(jié)點(diǎn)為B、C、D。
8. 雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：如果一個節(jié)點(diǎn)含有子樹，那么這個節(jié)點(diǎn)就可以叫做這些子樹根節(jié)點(diǎn)的父節(jié)點(diǎn)，如上圖B、C、D的父節(jié)點(diǎn)為A.
9. 兄弟節(jié)點(diǎn)： 具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)，如上圖B、C、D互為兄弟節(jié)點(diǎn)。
10. 堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟節(jié)點(diǎn)，如上圖F、G互為堂兄弟節(jié)點(diǎn)。
11. 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)都可以成為該節(jié)點(diǎn)的祖先，如上圖的A是所有節(jié)點(diǎn)的祖先。
12. 子孫：以某節(jié)點(diǎn)為根節(jié)點(diǎn)，它的子樹上的所有節(jié)點(diǎn)都可以稱作它的子孫。如除A以外的所有節(jié)點(diǎn)都可以叫做A的子孫。
13. 森林：由m（m > 0）棵互不相交的樹組成的集合叫做森林。

?? 樹的結(jié)構(gòu)設(shè)計(jì)

樹的模擬實(shí)現(xiàn)比較復(fù)雜，我們的重點(diǎn)放在二叉樹的模擬實(shí)現(xiàn)上，實(shí)際中有雙親表示法、孩子雙親表示法以及孩子兄弟表示法，我們這里簡單的來了解一下，孩子兄弟表示法。

typedef int DataType;
struct Node
{
   Node* _firstchild;//保存第一個孩子節(jié)點(diǎn)
   Node* _pnextBrother;//保存下一個兄弟節(jié)點(diǎn)
   DataType _data;//節(jié)點(diǎn)中的數(shù)據(jù)域
}

?? 樹的應(yīng)用

文件系統(tǒng)的目錄樹結(jié)構(gòu)

?? 二叉樹

二叉樹就是每個節(jié)點(diǎn)至多有兩個孩子的樹。

從上圖可以知道：

• 它的每一個節(jié)點(diǎn)至多有兩個子節(jié)點(diǎn)，所以我們可以知道二叉樹的最大度為2。
• 二叉樹是有左右子樹之分的，不能顛倒，因此二叉樹是有序樹（有順序）。

?? 兩種特殊的二叉樹

• 滿二叉樹：：一個二叉樹，如果每一個層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是$2^k?1$ ，則它就是滿二叉樹。
  
• 完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為K的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
  
• 滿二叉樹是特殊的完全二叉樹

?? 二叉樹的一些基本性質(zhì)

這些性質(zhì)大家可以結(jié)合圖來理解，主要用來應(yīng)對選擇題。

?? 二叉樹的兩種結(jié)構(gòu)

?? 順序存儲

順序存儲就是使用數(shù)組去存儲，主要適用于完全二叉樹，因?yàn)槿绻悴皇峭耆鏄渚蜁嬖诳臻g的浪費(fèi)，我們來畫圖解釋一下為什么會存在空間的浪費(fèi)。

二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

堆是一種完全二叉樹，我們在實(shí)現(xiàn)堆時，會使用數(shù)組存儲，后序我們會重點(diǎn)介紹堆這種數(shù)據(jù)結(jié)構(gòu)，這篇博客我們先來重點(diǎn)看二叉樹。

?? 鏈?zhǔn)酱鎯?/h4>

鏈?zhǔn)酱鎯?shí)際上就是用鏈表去存儲節(jié)點(diǎn)，一個節(jié)點(diǎn)有三個數(shù)據(jù)域，左孩子的節(jié)點(diǎn)指針，右孩子的節(jié)點(diǎn)指針，節(jié)點(diǎn)的數(shù)據(jù)值。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，當(dāng)前我們二叉樹中用的一般都是二叉鏈，高階數(shù)據(jù)結(jié)構(gòu)如紅黑樹等會用到三叉鏈。

?? 鏈?zhǔn)蕉鏄涞哪M實(shí)現(xiàn)

?? 鏈?zhǔn)蕉鏄涞慕Y(jié)構(gòu)設(shè)計(jì)

前面已經(jīng)將鏈?zhǔn)蕉鏄涞倪壿嫿Y(jié)構(gòu)畫出，它用代碼來描述應(yīng)該是這樣的。

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

?? 鏈?zhǔn)蕉鏄涞暮瘮?shù)方法聲明

// 通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root);
// 二叉樹節(jié)點(diǎn)個數(shù)
int BinaryTreeSize(BTNode* root);
// 二叉樹葉子節(jié)點(diǎn)個數(shù)
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹第k層節(jié)點(diǎn)個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root);
// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root);
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root);
// 求某一個數(shù)的高度/深度
int BinaryTreeHeight(BTNode* root);

?? 鏈?zhǔn)蕉鏄涞暮瘮?shù)方法模擬實(shí)現(xiàn)

?? 創(chuàng)建二叉樹的兩種方法

?? 創(chuàng)建方法一

第一種創(chuàng)建二叉樹的方式是通過在測試文件里面直接創(chuàng)建節(jié)點(diǎn)，然后手動的把它們的關(guān)系給鏈接起來。

void Test1()
{
   BTNode* Node1 = (BTNode*)malloc(sizeof(BTNode));
	Node1->_data = 1;
	Node1->_left = NULL;
	Node1->_right = NULL;
	BTNode* Node2 = (BTNode*)malloc(sizeof(BTNode));
	Node2->_data = 2;
	Node2->_left = NULL;
	Node2->_right = NULL;
	BTNode* Node3 = (BTNode*)malloc(sizeof(BTNode));
	Node3->_data = 5;
	Node3->_left = NULL;
	Node3->_right = NULL;
	BTNode* Node4 = (BTNode*)malloc(sizeof(BTNode));
	Node4->_data = 8;
	Node4->_left = NULL;
	Node4->_right = NULL;
	BTNode* Node5 = (BTNode*)malloc(sizeof(BTNode));
	Node5->_data = 5;
	Node5->_left = NULL;
	Node5->_right = NULL;
	BTNode* Node6 = (BTNode*)malloc(sizeof(BTNode));
	Node6->_data = 7;
	Node6->_left = NULL;
	Node6->_right = NULL;
	BTNode* Node7 = (BTNode*)malloc(sizeof(BTNode));
	Node7->_data = 10;
	Node7->_left = NULL;
	Node7->_right = NULL;
	Node1->_left = Node2;
	Node1->_right = Node3;
	Node2->_left = Node4;
	Node2->_right = Node5;
	Node3->_left = Node6;
	Node4->_left = Node7;
	BinaryTreeLevelOrder(Node1);//層序遍歷
}

注意：以下函數(shù)都用方法一的數(shù)據(jù)來測試
上面的節(jié)點(diǎn)用二叉樹的圖來表示是這樣的：

我們打印走的是層序遍歷，這個要用到隊(duì)列，我們稍后再說，至于為什么要用層序遍歷打印，當(dāng)然是為了更快的檢查我們的二叉樹是否構(gòu)建正確，黑框是我們的打印結(jié)果，可以看到是符合預(yù)期的。

?? 創(chuàng)建方法二

上面的方法顯然是不太好的，因?yàn)樾枰覀兪謩尤ユ溄樱绻?jié)點(diǎn)的個數(shù)很龐大，10萬個，也要我們手動去鏈接嗎，這顯然是不太合適的，所以接下來我們方法二就來給小伙伴們介紹一下，二叉樹常見的構(gòu)建方法，給你傳一個數(shù)組，并告訴你這個數(shù)組是什么遍歷讓你來構(gòu)建二叉樹。

// 通過前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	assert((*pi) < n);
	if (a[(*pi)] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->_data = a[(*pi)++];
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);
	return root;
}

由于這個前序遍歷的數(shù)組給我們給出了空指針，也就是每一個節(jié)點(diǎn)都給出來了，空指針用’#'來表示，所以這個二叉樹是唯一的，另外這個數(shù)組應(yīng)該是一個字符數(shù)組，我們通過遞歸來寫就很簡單了，實(shí)際上就是一個前序遍歷還原的過程，過于簡單，我們不做過多的闡述。如果你對遞歸的過程不太理解，我們下面的前、中、后序遍歷會深入的去講解。

• 注意這里如果沒有給出代表空指針的’#‘，二叉樹就不唯一了，我們舉個例子來畫圖說明：
  假設(shè)此時二叉樹的前序遍歷是1 2 3 4 6 5 8

這里N代表空節(jié)點(diǎn)。

我們這里隨便寫都寫出了兩種。

注意：當(dāng)我們不給出空節(jié)點(diǎn)時，只有中序和前序給出或者中序和后序給出，這個二叉樹才確定，因?yàn)槲覀兛梢酝ㄟ^中序來劃分左子樹和右子樹，然后前序或者后序得到根，這樣就能確定這個二叉樹了，后序我們二叉樹OJ會有類似的題目，如果小伙伴不太會也請不要擔(dān)心。

?? 二叉樹的前序遍歷

?? 遞歸實(shí)現(xiàn)

二叉樹的前序遍歷就是先遍歷根節(jié)點(diǎn)，然后再去遍歷它的左子樹，最后遍歷它的右子樹。遞歸實(shí)現(xiàn)很簡單，代碼看著很短，關(guān)鍵是我們要理解代碼為什么是這樣，這里我們通過畫遞歸展開圖來解釋下面的程序：

// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
	  printf("NULL ");
	  return;
	}
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_left);
	BinaryTreeInOrder(root->_right);
}

這個函數(shù)的遞歸展開圖大致就是這樣注意我們只畫了一部分，希望能幫助你理解，當(dāng)你熟練之后就可以只畫一個草圖了，像這樣：

使用方法一創(chuàng)建二叉樹，打印結(jié)果如下：

?? 非遞歸實(shí)現(xiàn)

遞歸遍歷很簡單，遍歷完左子樹后又可以返回這個左子樹的根節(jié)點(diǎn)，然后繼續(xù)遍歷右子樹，但是我們非遞歸該如何控制呢？難道要用變量去一個個保存維護(hù)嗎，這太復(fù)雜了，我們很容易想到由于遞歸正是利用了隱式棧后入先出的特點(diǎn)，我們使用一個顯示棧來模擬這個過程就可以了。
我們先畫圖來分析：

我們繼續(xù)總結(jié)，簡化一下我們其實(shí)在一直重復(fù)做著相同的事情：

知道了原理是什么，再去寫程序就是信手拈來，C語言代碼實(shí)現(xiàn)如下，其中手搓棧的代碼請進(jìn)入博主的倉庫自?。?/p>

// 二叉樹前序遍歷非遞歸版本
void BinaryTreePrevOrderF(BTNode* root)
{
	Stack st1;//建立棧對象
	StackInit(&st1);//初始化棧對象

	BTNode* cur = root;
	//開始循環(huán)進(jìn)行前序遍歷
	while (!StackEmpty(&st1) || cur == root)
	{
		//開始遍歷左子樹
		while (cur != NULL)
		{
			printf("%d ", cur->_data);//先遍歷打印根節(jié)點(diǎn)
			StackPush(&st1,cur);//將當(dāng)前節(jié)點(diǎn)指針入棧
			cur = cur->_left;//繼續(xù)遍歷左樹
		}

		printf("NULL ");
		//遍歷完了某個根節(jié)點(diǎn)的左子樹，cur為空跳出循環(huán)
		while (!StackEmpty(&st1))
		{
			cur = StackTop(&st1);
			cur = cur->_right;
			if (cur != NULL)//此時表明我們找到了棧里面最近一次入棧的那個右子樹根節(jié)點(diǎn)不為空的節(jié)點(diǎn)
			{
				StackPop(&st1);//我們已經(jīng)拿到它的右子樹根節(jié)點(diǎn)，它已經(jīng)沒有用了，彈出去！
				break;
			}
			printf("NULL ");
			StackPop(&st1);//沒有找到這個節(jié)點(diǎn)沒有用了，彈出去
		}
	}
}

注意我們棧的數(shù)據(jù)類型是這個二叉樹的結(jié)構(gòu)體指針，這里可能是編譯器的問題，不能使用這個結(jié)構(gòu)體的別名，只能使用原來的那個來定義棧的數(shù)據(jù)類型，它們分屬于不同的文件。

這里我們使用二叉樹的創(chuàng)建方法一來驗(yàn)證一下，打印結(jié)果：

和我們的預(yù)期一致。

?? 二叉樹的中序遍歷

二叉樹的中序遍歷就是先遍歷左子樹，然后再遍歷它的根節(jié)點(diǎn)，最后遍歷它的右子樹，對于每個節(jié)點(diǎn)都是同樣的規(guī)則。

?? 遞歸實(shí)現(xiàn)

遞歸實(shí)現(xiàn)和前序遍歷類似，這里我們直接給出代碼：

// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_right);
}

打印結(jié)果：

遞歸遍歷過程理解，這里我們不再畫遞歸展開圖，直接畫出簡略圖：

這里我們也打印出了NULL，是為了便于大家理解。

?? 非遞歸實(shí)現(xiàn)

非遞歸和前序的非遞歸類似，我們依舊畫圖來分析

這里沒有具體的去畫棧的數(shù)據(jù)進(jìn)出分析，因?yàn)槲覀円呀?jīng)有了前序的基礎(chǔ)，中序和前序是很相似的，改一下打?。ù嫒霐?shù)組）的順序即可。

代碼實(shí)現(xiàn)：文章來源地址http://www.zghlxwxcb.cn/news/detail-841458.html

//二叉樹中序遍歷非遞歸版本
void BinaryTreeInOrderF(BTNode* root)
{
	Stack st1;//創(chuàng)建一個棧對象
	StackInit(&st1);//初始化棧對象
    
	BTNode* cur = root;//創(chuàng)建一個臨時遍歷cur用于遍歷二叉樹
	while (!StackEmpty(&st1) || cur != NULL)//棧不為空，或者cur不為空，我們就繼續(xù)執(zhí)行程序。
	{
		while (cur != NULL)
		{
			StackPush(&st1, cur);
			cur = cur->_left;
		}
		printf("NULL ");
		//某一個節(jié)點(diǎn)的左子樹遍歷完了，開始管它的右子樹
		while(!StackEmpty(&st1))
		{
			cur = StackTop(&st1);
			printf("%d ", cur->_data);//這個節(jié)點(diǎn)的左樹（可能為空）遍歷完了，可以遍歷根節(jié)點(diǎn)了
			cur = cur->_right;
			if(cur != NULL)
			{
				StackPop(&st1);//這個節(jié)點(diǎn)的根節(jié)點(diǎn)和左子樹已經(jīng)遍歷完嗎，右樹的根節(jié)點(diǎn)我們已經(jīng)保存，它已經(jīng)沒有用了，我們直接彈出去
				break;//出循環(huán)去遍歷當(dāng)前根節(jié)點(diǎn)的右樹，同樣的邏輯
			}
			StackPop(&st1);//這個節(jié)點(diǎn)的右樹為空，同樣沒有用，我們也彈出去。
			printf("NULL ");
		}
	}
}

遍歷結(jié)果：

符合預(yù)期。

?? 二叉樹的后序遍歷

二叉樹的后序遍歷就是先遍歷左子樹，然后再去遍歷它的右子樹，最后遍歷它的根節(jié)點(diǎn)。

?? 遞歸實(shí)現(xiàn)

遞歸實(shí)現(xiàn)還是一如既往的簡單，關(guān)鍵是理解

// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);//先遍歷它的左子樹
	BinaryTreeInOrder(root->_right);//再遍歷它的右子樹
	printf("%d ", root->_data);//最后打印它的根節(jié)點(diǎn)的值
}

打印結(jié)果：

?? 非遞歸實(shí)現(xiàn)

這里最難的應(yīng)該就是后序遍歷的非遞歸，也不能說難吧，就是后序遍歷的非遞歸和前面兩個不太一樣，前序遍歷和中序遍歷的非遞歸是比較相似的，這里我們畫出具體的數(shù)據(jù)出入棧的分析圖就很清晰了：

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

// 二叉樹后序遍歷非遞歸版本
void BinaryTreePostOrderF(BTNode* root)
{
	Stack st1;//定義棧對象
	StackInit(&st1);//初始化棧對象

	BTNode* cur = root;//創(chuàng)建臨時變量用來遍歷二叉樹
	while (!StackEmpty(&st1) || cur != NULL)//棧不為空，或者cur不為空進(jìn)入循環(huán)
	{
		while (cur != NULL)
		{
			StackPush(&st1, cur);//將左子樹的根節(jié)點(diǎn)的左節(jié)點(diǎn)依次入棧，這里也要把第一個根節(jié)點(diǎn)入棧（因?yàn)榈认乱ケ闅v它的右子樹）
			cur = cur->_left;
		}

		printf("NULL ");
		//某一個節(jié)點(diǎn)的左子樹為空跳出循環(huán)
		BTNode* prev = NULL;//定義遍歷prev用于保存上一個遍歷的右子樹根節(jié)點(diǎn)
		cur = StackTop(&st1);
		while(!StackEmpty(&st1) && (cur->_right == NULL || cur->_right == prev))//如果棧不為空，并且滿足打印和pop的條件，我們就繼續(xù)pop，直到不滿足條件
		{
			if (cur->_right == NULL)
				printf("NULL ");
			printf("%d ", cur->_data);
			StackPop(&st1);
			prev = cur;
			if (!StackEmpty(&st1))
			{
				cur = StackTop(&st1);
			}
		}
		//程序執(zhí)行到這里，只存在兩種情況，1.cur的右樹不為空，我們需要去遍歷它的右樹，2.棧為空，由于是后序，棧為空說明已經(jīng)遍歷完了，把cur置為空，讓循環(huán)結(jié)束
		if (!StackEmpty(&st1))
			cur = cur->_right;
		else
			cur = NULL;
	}
}

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

與預(yù)期一致。

?? 二叉樹的層序遍歷（非遞歸）

層序遍歷和它的名字一樣，是將二叉樹一層一層的遍歷，我們應(yīng)該如何實(shí)現(xiàn)呢？

這里我們不再賣關(guān)子了（dog，層序遍歷需要借助數(shù)據(jù)結(jié)構(gòu)隊(duì)列先進(jìn)先出的特性來實(shí)現(xiàn)，我們畫圖來分析，使用隊(duì)列來做的合理性：

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

// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;//建立隊(duì)列對象
	QueueInit(&q);//初始化隊(duì)列
	QueuePush(&q,root);//將根節(jié)點(diǎn)入隊(duì)列
	while (!QueueEmpty(&q))//隊(duì)列為空，層序遍歷結(jié)束
	{
		BTNode* cur = QueueFront(&q);//取隊(duì)頭
		QueuePop(&q);//pop隊(duì)頭
		if (cur == NULL)//如果隊(duì)頭為空，直接打印空
		{
			printf("NULL ");
		}
		else//否則打印隊(duì)頭數(shù)據(jù)
		{
			printf("%d ", cur->_data);
		}
		if (cur != NULL)//如果隊(duì)頭不為空，入隊(duì)頭的數(shù)據(jù)
		{
			QueuePush(&q, cur->_left);
			QueuePush(&q, cur->_right);
		}
	}
}

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

符合預(yù)期。

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

我們想計(jì)算二叉樹的節(jié)點(diǎn)的個數(shù)應(yīng)該怎么去做呢？用遞歸的思想就很簡單，當(dāng)一個節(jié)點(diǎn)作為根時，我們想計(jì)算以它為根的這棵二叉樹節(jié)點(diǎn)的數(shù)量，只需要求出它的左樹的節(jié)點(diǎn)總數(shù)量和右樹的節(jié)點(diǎn)總數(shù)量之和再加1就可以了，遞歸下去它的每個節(jié)點(diǎn)都面臨相同的問題，這樣我們就將一個大問題劃分為了一個個相同的子問題，可以用遞歸來解決。

?? 遞歸版本（前序遍歷）

// 二叉樹節(jié)點(diǎn)個數(shù)(遞歸版)
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
}

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

遞歸解法很簡單？根本沒有挑戰(zhàn)性？那不妨我們來嘗試一下非遞歸。

?? 非遞歸版本（前序遍歷）

分析：

其實(shí)就是二叉樹的前序遍歷，只不過從打印變成了Size++，想一想，前序遍歷打印的次數(shù)不就是節(jié)點(diǎn)的個數(shù)嗎，只不過我們不打印NULL了而已，使用任何一種遍歷都可以求出節(jié)點(diǎn)個數(shù)。

// 二叉樹節(jié)點(diǎn)個數(shù)非遞歸版
int BinaryTreeSizeF(BTNode* root)
{
	Stack st1;//定義棧的臨時變量
	StackInit(&st1);//初始化棧

	BTNode* cur = root;//定義臨時變量cur用于遍歷
	int Size = 0;
	while(!StackEmpty(&st1) || cur != NULL)
	{
		while (cur != NULL)
		{
			Size++;//根節(jié)點(diǎn)的位置Size++
			StackPush(&st1,cur);//節(jié)點(diǎn)指針入棧
			cur = cur->_left;//以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，遍歷它的左子樹
		}

		//有一個節(jié)點(diǎn)的左子樹走完了
		while (!StackEmpty(&st1))
		{
			cur = StackTop(&st1);
			cur = cur->_right;
			StackPop(&st1);
			if (cur != NULL)//有節(jié)點(diǎn)的右子樹不為空，我們跳出出棧循環(huán)，去遍歷它的右子樹
			{
				break;
			}
		}
	}
	return Size;
}

運(yùn)行結(jié)果:

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

此函數(shù)用來求葉子節(jié)點(diǎn)的個數(shù)我們的思路也很簡單，走一個前序遍歷，二叉樹的葉子節(jié)點(diǎn)的個數(shù) = 左子樹葉子節(jié)點(diǎn)的個數(shù)，和右子樹葉子節(jié)點(diǎn)的個數(shù)之和。

?? 遞歸版本

// 二叉樹葉子節(jié)點(diǎn)個數(shù)
int BinaryTreeLeafSize(BTNode* root) 
{
	if (root == NULL)//如果當(dāng)前節(jié)點(diǎn)為空，我們返回0
		return 0;
	if (root->_left == NULL && root->_right == NULL)//如果當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)我們直接返回1
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

實(shí)際我們要處理的就這兩種情況：

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

?? 非遞歸版本

非遞歸主要走的還是前序的非遞歸，在一些細(xì)節(jié)的地方處理即可。

我們?nèi)匀皇褂肧ize來記錄葉子節(jié)點(diǎn)的個數(shù)，當(dāng)一個節(jié)點(diǎn)的左孩子為空且右孩子也為空，我們保證右孩子為空很簡單，關(guān)鍵是如何保證左孩子為空，注意：只有循環(huán)剛結(jié)束的棧頂節(jié)點(diǎn)的左孩子才會空，其它的都有左孩子，你細(xì)思（dog。

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

// 二叉樹葉子節(jié)點(diǎn)個數(shù)非遞歸版
int BinaryTreeLeafSizeF(BTNode* root)
{
	Stack st1;//定義棧的臨時變量
	StackInit(&st1);//初始化棧

	BTNode* cur = root;//定義臨時變量cur用于遍歷
	int Size = 0;
	while (!StackEmpty(&st1) || cur != NULL)
	{
		while (cur != NULL)
		{
			StackPush(&st1, cur);//節(jié)點(diǎn)指針入棧
			cur = cur->_left;//以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，遍歷它的左子樹
		}

		//葉子節(jié)點(diǎn)只會在剛出循環(huán)的棧頂元素中出現(xiàn)
		cur = StackTop(&st1);
		if (cur->_right == NULL)//為空，葉子節(jié)點(diǎn)個數(shù)++，不為空繼續(xù)遍歷它的右子樹
		{
			Size++;
			StackPop(&st1);
			//找到下一個右子樹不為空的節(jié)點(diǎn)
			while (!StackEmpty(&st1))
			{
				cur = StackTop(&st1);
				cur = cur->_right;
				StackPop(&st1);
				if (cur != NULL)//有節(jié)點(diǎn)的右子樹不為空，我們跳出出棧循環(huán)，去遍歷它的右子樹
				{
					break;
				}
			}
		}

	}
	return Size;
}

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

?? 二叉樹第k層節(jié)點(diǎn)個數(shù)（假設(shè)二叉樹從第一層開始）

求第K層節(jié)點(diǎn)的個數(shù)也很簡單，遞歸的思想基本和前面的沒什么區(qū)別，二叉樹第k層節(jié)點(diǎn)的個數(shù) = 根節(jié)點(diǎn)左子樹第k層節(jié)點(diǎn)的個數(shù)+根節(jié)點(diǎn)右子樹第k層節(jié)點(diǎn)的個數(shù)。

?? 遞歸版本

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

// 二叉樹第k層節(jié)點(diǎn)個數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);//我們規(guī)定二叉樹層數(shù)從1開始，如果k小于1就要報(bào)錯，說明傳錯了。
	if (root == NULL)//如果此時root為空還沒返回說明找不到了，直接返回0
		return 0;
	if (k == 1)//找到了，返回1
		return 1;
	return BinaryTreeLevelKSize(root->_left,k-1) + BinaryTreeLevelKSize(root->_right,k-1);//根節(jié)點(diǎn)的第K層，相對于它的子樹來說就是k-1層
}

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

?? 非遞歸版本

?? 使用棧實(shí)現(xiàn)

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

// 二叉樹第k層節(jié)點(diǎn)個數(shù)非遞歸使用棧實(shí)現(xiàn)
int BinaryTreeLevelKSizeFS(BTNode* root, int k)
{
	Stack st1;//創(chuàng)建隊(duì)列
	StackInit(&st1);//初始化隊(duì)列

	BTNode* cur = root;//定義臨時變量cur來遍歷二叉樹
	int k1 = 1;
	int Size = 0;
	while (!StackEmpty(&st1) || cur != NULL)
	{
		while (cur != NULL)
		{
			if (k1 >= k)//滿足情況，我們break,同時Size++
			{
				Size++;
				cur = NULL;//把cur置為空，如果后面還存在右子樹滿足，cur就會被更新，否則就退出循環(huán)
				break;
			}
			else//還沒有滿足層數(shù)的要求，我們存入節(jié)點(diǎn)指針和層數(shù)，繼續(xù)遍歷
			{
				//統(tǒng)一先存值，再存節(jié)點(diǎn)
				StackPush(&st1, k1);
				StackPush(&st1, cur);
				k1++;
			}
			cur = cur->_left;//沒有滿足情況繼續(xù)遍歷
		}
		//找節(jié)點(diǎn)右子樹不為空的那個節(jié)點(diǎn)
		while (!StackEmpty(&st1))
		{
			cur = StackTop(&st1);
			StackPop(&st1);//pop節(jié)點(diǎn)指針
			if (cur->_right != NULL)//找到了
			{
				cur = cur->_right;
				k1 = StackTop(&st1)+1;
				StackPop(&st1);//pop這個節(jié)點(diǎn)對應(yīng)的層數(shù)
				break;
			}
			cur = NULL;//如果沒找到，程序就應(yīng)該結(jié)束，cur應(yīng)該被置空
			StackPop(&st1);//pop對應(yīng)的層數(shù)
		}

	}
	return Size;
}

細(xì)節(jié)有很多，比如對cur的置空處理就很關(guān)鍵，我們舉幾個例子來探討以下為什么要這樣做：

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

?? 使用隊(duì)列實(shí)現(xiàn)

剛剛這種方法在邏輯上理解可能有點(diǎn)困難，我們使用隊(duì)列會更容易理解：

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

// 二叉樹第k層節(jié)點(diǎn)個數(shù)非遞歸使用隊(duì)列實(shí)現(xiàn)
int BinaryTreeLevelKSizeFQ(BTNode* root, int k)
{
	assert(k > 0);//層數(shù)必須合法

	Queue q1;//創(chuàng)建隊(duì)列變量
	QueueInit(&q1);//初始化隊(duì)列變量

	QueuePush(&q1, root);//先將根節(jié)點(diǎn)入隊(duì)列
	BTNode* cur = NULL;//創(chuàng)建臨時變量用于輔助完成隊(duì)列的入隊(duì)操作

	while (!QueueEmpty(&q1))
	{
		int Size = QueueSize(&q1);//某一層的節(jié)點(diǎn)個數(shù)
		if (k == 1)
			return Size;
		while (Size--)
		{
			cur = QueueFront(&q1);
			QueuePop(&q1);
			if (cur->_left)
				QueuePush(&q1,cur->_left);
			if (cur->_right)
				QueuePush(&q1, cur->_right);
		}
		k--;
	}
	return 0;//沒有這層
}

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

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

注：這里我們默認(rèn)不會存相同的值。

遞歸思想：先去左樹找，如果左樹不能找到，再去右樹找。

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

// 二叉樹查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;
	BTNode* left = BinaryTreeFind(root->_left, x);
	if (left == NULL)
		return BinaryTreeFind(root->_right, x);
	else
		return left;
}

假設(shè)此時我們找節(jié)點(diǎn)值為10的節(jié)點(diǎn)，運(yùn)行結(jié)果為：

?? 求某一個樹的高度/深度

求一個樹的高度/深度，假設(shè)從1開始，遞歸思路也很簡單，一個樹的深度 = 它左右子樹的最大深度+1。

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

int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHight = BinaryTreeHeight(root->_left) + 1;//保存左樹的最大深度+1
	int rightHight = BinaryTreeHeight(root->_right) + 1;//右樹的最大深度+1
	return leftHight > rightHight ? leftHight : rightHight;//返回最大值
}

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

非遞歸我們不再給出，使用層序遍歷或者前中后序均可，有興趣的小伙伴可自行嘗試。

?? 判斷二叉樹是否是完全二叉樹

上面我們已經(jīng)談到，完全二叉樹是基于滿二叉樹的概念引申出來的，我們簡單點(diǎn)來說：完全二叉樹就是對應(yīng)深度的滿二叉樹按照順序減少一些節(jié)點(diǎn)，比如下面的圖：

那我們應(yīng)該如何判斷一棵樹是否是完全二叉樹呢？我們可以借助二叉樹的層序遍歷去完成這個判斷，并且我們需要存入NULL，因?yàn)閷有虮闅v都是一層一層按照順序來遍歷的，當(dāng)NULL后面都沒有為非空的節(jié)點(diǎn)時表面這個樹是完全二叉樹，否則就不是。空樹不是完全二叉樹。

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

// 判斷二叉樹是否是完全二叉樹
int BinaryTreeComplete(BTNode* root)
{
	assert(root);//如果為空不需要判斷直接強(qiáng)制報(bào)錯。

	Queue q;
	QueueInit(&q);//初始化隊(duì)列
	QueuePush(&q, root);//先存入根節(jié)點(diǎn)
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur == NULL)//找到空節(jié)點(diǎn)，退出循環(huán)
			break;
		QueuePush(&q, cur->_left);
		QueuePush(&q, cur->_right);
	}
    
	while (!QueueEmpty(&q))//繼續(xù)遍歷，如果能找到非空節(jié)點(diǎn)，則這個樹一定不是完全二叉樹返回false
	{
		BTNode* cur1 = QueueFront(&q);
		QueuePop(&q);
		if (cur1 != NULL)
			return false;
	}
	return true;//是完全二叉樹，返回true
}

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

?? 二叉樹銷毀

二叉樹的銷毀就是我們手動釋放空間的過程，因?yàn)橛行┕?jié)點(diǎn)是在堆上申請的，需要我們自己去釋放，走一個后序遍歷就可以完成，注意不能走前序或者中序，因?yàn)榍靶蚝椭行蚨际歉谟覙淝懊婢歪尫帕?，我們后面就找不到右樹了（非法訪問的問題）。

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

// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root)//傳二級指針，是為了讓其不用在外面置空
{
	if (*root == NULL)//如果已經(jīng)為空，返回
		return;
	BinaryTreeDestory(&(*root)->_left);//先去釋放左樹
	BinaryTreeDestory(&(*root)->_right);//再釋放右樹節(jié)點(diǎn)
	free(*root);//最后釋放根節(jié)點(diǎn)
	*root = NULL;//注意不要忘記置空
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)初階之基礎(chǔ)二叉樹（C語言實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！