前言

學習二叉樹前，我們先來了解樹的基本概念，為學習二叉樹鋪墊

由于二叉樹是遞回實作的，所以不懂遞回的小伙伴先去看看遞回
先學好遞回，在學二叉樹

樹的基本概念

1、樹的定義

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，當 n = 0 時，T稱為空樹；否則，T是非空樹，記作

• 有一個特殊的結點r，稱為根結點，根節點沒有前驅結點
• 除根節點外，其余結點被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼，
• 因此，樹是遞回定義的，

2、樹的相關術語

• 結點的度：一個節點含有的子樹的個數稱為該節點的度（分支數）； 如上圖：A的為6
• 葉結點或終端結點：度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點
• 非終端節點或分支結點：度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點
• 雙親結點或父結點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點
• 孩子結點或子結點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點
• 兄弟結點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點
• 樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6
• 結點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
• 樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4
• 堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點
• 結點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先
• 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫
• 森林：由m（m>0）棵互不相交的樹的集合稱為森林

二叉樹的基本概念

1、二叉樹的定義

一棵二叉樹是結點的一個有限集合，該集合:

1. 或者為空
2. 或者由一個根節點加上兩棵別稱為左子樹和右子樹、互不相交的二叉樹組成

二叉樹的特點：

1. 二叉樹不存在度大于2的結點
2. 二叉樹的子樹有左、右之分，其子樹的次序不能顛倒，因此二叉樹是有序樹

所以二叉樹有下面幾種復合情況：

2、二叉樹的性質

二叉樹具有如下性質：

1. 若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個結點.
2. 若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是2^k-1.
3. 對任何一棵二叉樹， 如果度為0其葉結點個數為n0， 度為2的分支結點個數為n2，則有 n0＝n2＋1
4. 若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，h=log2(n+1). (ps：log2(n+1)是log以2為底，n+1為對數)
5. 對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的陣列順序對所有節點從0開始編號，則對于序號為i的結點有：
   1. 若i>0，i位置節點的雙親序號：(i-1)/2；i=0，i為根節點編號，無雙親節點
   2. 若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子
   3. 若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子

3、特殊的二叉樹

滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是2^k - 1，則它就是滿二叉樹，

完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 其特點是：從上面第 1 層到第 k - 1層的所有各層的結點數都是滿的，僅最下面第 k 層或是滿的，或從右向左連續缺失若干結點，要注意的是滿二叉樹是一種特殊的完全二叉樹，

二叉樹的實作方式

二叉樹一般有陣列存盤和鏈式存盤兩種方式：

1. 普通的二叉樹是不適合用陣列來存盤的，因為可能會存在大量的空間浪費，而完全二叉樹更適合使用順序結構存盤，現實中我們通常把堆(一種二叉樹)使用順序結構的陣列來存盤，需要注意的是這里的堆和作業系統虛擬行程地址空間中的堆是兩回事，一個是資料結構，一個是作業系統中管理記憶體的一塊區域分段，

2. 使用鏈表存盤克服了陣列存盤浪費空間的缺點，鏈式存盤二叉樹的結點至少包含三個域，資料域data，左子女結點指標leftChild 和右子女結點指標 rightChild，這種鏈表稱為二叉鏈表，

二叉樹的基本操作

頭檔案

#pragma once // 防止頭檔案重復包含
#include<stdio.h> 
#include<stdlib.h> // 動態記憶體函式頭檔案
#include<stdbool.h> // bool 頭檔案
typedef char DataType; // char重命名
typedef struct Node
{
	DataType data; // 資料域
	struct Node* leftChild; // 左子女
	struct Node* rightChild; // 右子女
}BinTree;
void CreateBinTree(BinTree** T);
//BinTree* CreateBinTree();// 先序建立二叉樹
void PreOrderTraverse(BinTree* T);// 先序遍歷
void InOrderTraverse(BinTree* T);// 中序遍歷
void PostOraderTraverse(BinTree* T);// 后序遍歷
void PrintBinTree(BinTree* T);// 廣義表列印
size_t BinTreeHeight(BinTree* T);// 樹的深度/高度
size_t BinTreeSize(BinTree* T);// 樹的結點個數
size_t BinTreeLeadCount(BinTree* T);// 葉子結點個數
bool BinTreeIsEmpty(BinTree* T); // 判斷二叉樹是否為空？
size_t BinTreeNode_1Size(BinTree* T);// 統計度為1的結點個數
size_t BinTreeNode_2Size(BinTree* T);// 度為2的結點個數
void PrintBinTreeNode_TPath(BinTree* T, char path[], int pathlen);//輸出二叉樹中從每個葉子結點到根結點的路徑
void ChangeBinTreeLRNode(BinTree* T);// 交換左右結點
void DoubleOradeTraverse(BinTree* T);
// 雙序遍歷是指對于二叉樹的每一個結點來說，先訪問這個結點，再按雙序遍歷它的左子樹，
// 然后再一次訪問這個結點，接下來按雙序遍歷它的右子樹
void Destory(BinTree* T); // 釋放樹結點

1、先序建立二叉樹

1. 形參采用二級指標的方式進行初始化，在里面進行創建數的結點，先創建根節點，在遞回創建左子樹和右子樹，

void CreateBinTree(BinTree** T)
{
	DataType ch;
	scanf("%c", &ch); // 輸入資料
	if (ch == '#') // #表示為空的結點
		*T = NULL;
	else
	{
		*T = (BinTree*)malloc(sizeof(BinTree));// 開辟記憶體
		if (*T == NULL)// 創建失敗
		{
			perror("MALLOC T");// 錯誤報警資訊
			exit(-1); // 退出
		}
		(*T)->data = ch; // 賦值
		CreateBinTree(&(*T)->leftChild); // 遞回創建左子樹
		CreateBinTree(&(*T)->rightChild); // 遞回創建右子樹
	}
}

2、先序遍歷

1. 先遍歷根節點，在遞回遍歷左子樹和右子樹

void PreOrderTraverse(BinTree *T)
{
	if (T!=NULL)
	{
		printf("%c ", T->data);
		PreOrderTraverse(T->leftChild);
		PreOrderTraverse(T->rightChild);
	}
}

3、中序遍歷

1. 先遞回遍歷左子樹，在遍歷根節點，最后遞回遍歷右子樹

void InOrderTraverse(BinTree* T)
{
	if (T != NULL)
	{
		InOrderTraverse(T->leftChild);
		printf("%c ", T->data);
		InOrderTraverse(T->rightChild);
	}
}

4、后序遍歷

1. 先遞回遍歷左子樹，再遞回遍歷右子樹，最后遍歷根節點，

void PostOraderTraverse(BinTree* T)
{
	if (T != NULL)
	{
		PostOraderTraverse(T->leftChild);
		PostOraderTraverse(T->rightChild);
		printf("%c ", T->data);
	}
}

5、先序遍歷（廣義表）

1. 在左子女不為慷訓者右子女不為空時，列印 ‘(’，在遞回遍歷左子樹，左遍歷完了，列印 ‘，’，在右子樹不為空的情況下，遞回遍歷右子樹，最后遍歷完，列印 ‘）’，

void PrintBinTree(BinTree* T)
{
	if (T != NULL)
	{
		printf("%c", T->data);
		if (T->leftChild != NULL || T->rightChild != NULL)// 檢查左子女或右子女是否為空
		{
			printf("("); // 有左子女或右子女列印 ( 進行閉合
			PrintBinTree(T->leftChild);// 遞回遍歷左子樹
			printf(","); // 左遍歷完了或者左子女為空，列印 ，
			if(T->rightChild != NULL) // 右子女不為空，在遞回遍歷右子樹
				PrintBinTree(T->rightChild);
			printf(")"); // 右子女遍歷完畢，列印 ）
		}
	}
}

6、二叉樹的深度（高度）

1. 遞回遍歷到左子樹或者右子樹的葉子結點，通過比較左子樹和右子樹的深度，取其最大值 + 1 即是樹的深度，

size_t BinTreeHeight(BinTree* T)
{
	if (T == NULL) // 為慷訓傳深度為0
		return 0;
	else
	{
		int m = BinTreeHeight(T->leftChild); // 遞回左子樹
		int n = BinTreeHeight(T->rightChild); // 遞回右子樹
		if (m > n)
			return m + 1; // 取其最大值 + 1 即上一層的深度
		else
			return n + 1;
	}
}

7、二叉樹的結點數

1. 分別遞回求出左子樹的結點個數和右子樹的結點個數，在加結點個數即是整個二叉樹的結點個數

size_t BinTreeSize(BinTree* T)
{
	if (T == NULL)
		return 0;
	else
		return BinTreeSize(T->leftChild) + BinTreeSize(T->rightChild) + 1;
}

8、二叉樹的葉結點個數

1. 葉結點是度為0的結點，所以判斷其左子女和右子女為空時，計算其個數即可

size_t BinTreeLeadCount(BinTree* T)
{
	if (T == NULL)
		return 0;
		// 葉結點才回傳 1
	if (T->leftChild == NULL && T->rightChild == NULL)
	{
		return 1;
	}
	else
		return BinTreeLeadCount(T->leftChild) + BinTreeLeadCount(T->rightChild);
		// 遞回遍歷左子樹和右子樹
}

9、度為1的結點個數

1. 度為1的結點是指左右子女其中一個為空的結點，所以這里遞回遍歷整個二叉樹，在度為1的條件下遍歷，左子樹 + 右子樹即度為 1 的結點個數

size_t BinTreeNode_1Size(BinTree* T)
{
	if (!T)
		return 0;
	// 度為1的結點，左右必定有一個為空
	if ((!T->leftChild  && T->rightChild) || (T->leftChild && !T->rightChild))
		return 1 + BinTreeNode_1Size(T->leftChild) + BinTreeNode_1Size(T->rightChild);
		// 度為1的結點數
	else
		return BinTreeNode_1Size(T->leftChild) + BinTreeNode_1Size(T->rightChild);
		// 此結點不是度為1的結點，繼續遍歷下一個左子女和右子女
}

10、度為2的結點個數

1. 跟求度為1的結點個數一樣，左右子女都不為空的條件下遍歷整個二叉樹，左子樹 + 右子樹即度為 2 的結點個數

size_t BinTreeNode_2Size(BinTree* T)
{
	if (!T)
		return 0;
		// 度為2的結點個數左右子女都不為空（兩條分支）
	if (T->leftChild && T->rightChild)
		return 1 + BinTreeNode_2Size(T->leftChild) + BinTreeNode_2Size(T->rightChild);
	else
		return BinTreeNode_2Size(T->leftChild) + BinTreeNode_2Size(T->rightChild);
		// 此結點不是度為2的結點，繼續遍歷下一個左子女和右子女
}

11、回傳每條葉結點到根結點的路徑

1. 這里要用一個陣列來保存路徑，遍歷到葉結點在回圈列印路徑

// 將路徑保存在陣列中
void PrintBinTreeNode_TPath(BinTree* T, char path[], int pathlen)
{
	if (T)
	{
		path[pathlen] = T->data; // 保存到陣列
		// 遍歷到葉結點，回圈列印路徑
		if (!T->leftChild && !T->rightChild)
		{
			for (int i = pathlen; i >= 0; i--)
				printf("%c ", path[i]);
			printf("\n");
		}
		else // 繼續遞回遍歷，直到葉結點
		{
			PrintBinTreeNode_TPath(T->leftChild, path, pathlen + 1);
			PrintBinTreeNode_TPath(T->rightChild, path, pathlen + 1);
		}
	}
}

12、交換左右結點

1. 在結點不為空的情況下，創建臨時數結點進行交換即可

void ChangeBinTreeLRNode(BinTree* T)
{
	BinTree* temp; // 臨時交換結點
	if (T)
	{
		temp = T->leftChild;
		T->leftChild = T->rightChild;
		T->rightChild = temp;
		ChangeBinTreeLRNode(T->leftChild);
		ChangeBinTreeLRNode(T->rightChild);
	}
}

13、雙序遍歷

1. 雙序遍歷是指對于二叉樹的每一個結點來說，先訪問這個結點，再按雙序遍歷它的左子樹，然后再一次訪問這個結點，接下來按雙序遍歷它的右子樹

void DoubleOradeTraverse(BinTree* T)
{
	if (T)
	{
		printf("%c", T->data); 
		DoubleOradeTraverse(T->leftChild);
		printf("%c", T->data);
		DoubleOradeTraverse(T->rightChild);
	}
}

14、銷毀樹

1. 先遞回銷毀左子樹和右子樹，最后在銷毀根結點即可

void Destory(BinTree* T)
{
	if (T)
	{
		Destory(T->leftChild);
		Destory(T->rightChild);
		free(T);
	}
}

二叉樹的注意事項

通過以上的學習，可以看出遞回的重要性和難度

1. 要注意先序，中序，后序，遍歷的先后順序，是先訪問根結點，還是遞回訪問左子樹，在遞回訪問右子樹，這些邏輯需要讀者自理清楚
2. 利用二叉樹的性質求解一些結點個數，要注意求解的條件，二叉樹夾著遞回，難免不讓人一頭霧水

原始碼：鏈接

制作不易，記得三連！！！