樹是一種 非線性的 數據結構，由 n(n >= 0) 個 有限節點 組成一種 具有層次關系 的集合

一、樹

樹的結構可以遞歸定義為：

根節點除根節點之外，其余節點被分成 M(M >= 0) 個互不相交的集合，每個集合分別是一棵子數

0 個結點的樹就稱為空樹

• 樹中除 根節點沒有前驅節點 之外，其余每個節點都 有且僅有一個前驅節點，因此 n 個節點的樹有 n - 1 條邊
• 樹中 每個節點 都可以 有 0 個或多個后繼節點

樹的相關概念

• 節點的度：節點含有的 子樹個數，如圖中 A 節點的度為 3
• 葉節點或終端節點：節點的 度為 0，如圖中 E、F、G、H、I
• 分支節點或非終端節點：節點的 度不為 0，如圖中 A、B、C、D
• 父節點或雙親節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點，如圖中 B 是 E 和 F 的父節點
• 子節點或孩子節點：若一個節點含有子樹，子樹的根節點 稱為該節點的子節點，如圖中 E 和 F 都是 B 的子節點
• 兄弟節點：父節點相同 的節點互為兄弟節點，如圖中 E 和 F 互為兄弟節點
• 樹的度：樹中所有節點的度中的最大值，如圖中 A 節點的度為 3，是樹中所有節點的度中的最大值，即樹的度為 3
• 節點的層次：如上圖，從根節點開始定義為第一層，根節點的子節點為第二層 …，(將根節點層次定義為 0 也是可以的)
• 樹的高度或深度：樹中節點的最大層次，圖中為樹的高度為 3
• 堂兄弟節點：父節點在同一層次的結點，如圖中 E、F、G、H、I 結點互為堂兄弟節點
• 節點的祖先：根節點到該節點路徑上的所有節點， A、B 結點是 E 的祖先
• 子孫：以某節點為根的子樹中任一節點 都稱為該節點的子孫，如上圖：所有節點都是 A 的子孫

森林：由 M(M > 0) 棵 互不相交的樹 構成的集合，將上圖中 A 節點去掉后，便構成由以 B、C、D 為根節點的三顆樹構成的森林

樹的存儲結構

在樹的結構中可以發現，樹是不易于用數組來存儲的，因此 采用鏈式的方式來存儲樹

結構1:

由于樹的結構中 每個節點的孩子個數是不確定的，因此每個節點需要使用一個順序表存儲孩子的指針

typedef int TreeDataType;
typedef struct TreeNode
{
	TreeDataType data;
	SeqList childs;	//順序表，并且每個元素的類型是 struct TreeNode*
}TreeNode;

結構2：

孩子兄弟表示法：節點的第一個孩子用該節點中的孩子指針指向，第二個孩子用該結點的第一個孩子結點的兄弟指針指向，第三個孩子用該節點的第二個孩子結點的兄弟指針指向…

typedef int TreeDataType;
typedef struct TreeNode
{
	TreeDataType data;
	struct TreeNode* child;
	struct TreeNode* brother;
}TreeNode;

存儲樹的方法還有雙親表示法，孩子表示法、孩子雙親表示法等，感興趣的讀者可以自行查閱

二、二叉樹

樹中 所有結點的度都小于等于 2 的樹，即樹的度小于等于 2 的樹，稱為二叉樹

在二叉數中子樹有左右區分，次序不能顛倒，左邊的稱為左子樹，右邊的稱為右子樹

二叉樹的遞歸定義為：

• 根節點
• 左子樹和右子樹

左子樹和右子樹可以為空樹，這里的子樹也是一顆二叉樹

二叉樹的性質

假定根節點的層數為 1

• 一棵非空二叉樹的第 i 層上最多有 2^(i - 1)個節點
• 深度為 h 的二叉樹的最大節點數是 2^h - 1
• 任何一棵二叉樹，如果度為 0 的葉節點個數為 n0，度為 2 的分支節點個數為 n2，則有 n0 ＝ n2 ＋1，即度為 0 的節點，比度為 2 的節點多 1

假設一顆二叉樹有 n 個節點，度為 0 的節點數為 n0，度為 1 的節點數為 n1，度為 2 的節點數為 n2，根據 n 個節點的二叉樹有 n - 1 條邊，可得到如下關系：

• n0 * 0 + n1 * 1 + n2 * 2 = n - 1
• n0 + n1 + n2 = n

解得：n0 = n2 + 1

滿二叉樹：如果二叉樹中每一個層的節點數都達到最大值，則這棵二叉樹稱為滿二叉樹

假設一棵二叉樹的層數為 K，且節點總數是 2^K - 1，則它就是滿二叉樹

完全二叉樹：假設一顆二叉樹有 K 層，如果這顆二叉數的前 K - 1 層是滿二叉樹，并且第 K 層是從左往右還是連續的節點，則這棵二叉樹稱為完全二叉樹

假設一棵完全二叉樹的層數為 K ，則完全二叉樹節點數的范圍：2^(K - 1) ~ 2^K - 1

完全二叉樹中度為 1 的節點有 0 個或 1 個

滿二叉樹可以認為是一種特殊的完全二叉樹

• 具有 n 個節點的 滿二叉樹 的深度 h = log2(n + 1)，n 個節點的 完全二叉樹 的深度 h = log2(n + 1)，h 向上取整(2.1 取 3)

• 對于具有 n 個節點的 完全二叉樹，按照 從上至下、從左至右 的順序，對所有節點從 0 開始依次編號

由于完全二叉樹中從第二層開始，每一層的結點都是偶數個，因此 左孩子的編號都均為奇數，右孩子的編號都均為偶數

在 n 個節點的 完全二叉樹 中，對于合法的編號為 i 的節點有：

• i 節點的 左孩子 的編號為 2 * i + 1，如果 2 * i + 1 < n，表示沒有左孩子
• i 節點的 右孩子 的編號為 2 * i + 2，如果 2 * i + 2 < n，表示沒有右孩子
• 根據 1 和 2 可知 i 節點的 父節點 的編號為 (i - 1) / 2，如果 i = 0，表示為根節點，沒有父節點