樹是一種 非線性的 數(shù)據(jù)結(jié)構(gòu)，由 n(n >= 0) 個 有限節(jié)點(diǎn) 組成一種 具有層次關(guān)系 的集合

一、樹

樹的結(jié)構(gòu)可以遞歸定義為：

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

0 個結(jié)點(diǎn)的樹就稱為空樹

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

樹的相關(guān)概念

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

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

樹的存儲結(jié)構(gòu)

在樹的結(jié)構(gòu)中可以發(fā)現(xiàn)，樹是不易于用數(shù)組來存儲的，因此 采用鏈?zhǔn)降姆绞絹泶鎯?/p>

結(jié)構(gòu)1:

由于樹的結(jié)構(gòu)中 每個節(jié)點(diǎn)的孩子個數(shù)是不確定的，因此每個節(jié)點(diǎn)需要使用一個順序表存儲孩子的指針

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

結(jié)構(gòu)2：

孩子兄弟表示法：節(jié)點(diǎn)的第一個孩子用該節(jié)點(diǎn)中的孩子指針指向，第二個孩子用該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)的兄弟指針指向，第三個孩子用該節(jié)點(diǎn)的第二個孩子結(jié)點(diǎn)的兄弟指針指向…

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

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

二、二叉樹

樹中 所有結(jié)點(diǎn)的度都小于等于 2 的樹，即樹的度小于等于 2 的樹，稱為二叉樹

在二叉數(shù)中子樹有左右區(qū)分，次序不能顛倒，左邊的稱為左子樹，右邊的稱為右子樹

二叉樹的遞歸定義為：

• 根節(jié)點(diǎn)
• 左子樹和右子樹

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

二叉樹的性質(zhì)

假定根節(jié)點(diǎn)的層數(shù)為 1

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

假設(shè)一顆二叉樹有 n 個節(jié)點(diǎn)，度為 0 的節(jié)點(diǎn)數(shù)為 n0，度為 1 的節(jié)點(diǎn)數(shù)為 n1，度為 2 的節(jié)點(diǎn)數(shù)為 n2，根據(jù) n 個節(jié)點(diǎn)的二叉樹有 n - 1 條邊，可得到如下關(guān)系：

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

解得：n0 = n2 + 1

滿二叉樹：如果二叉樹中每一個層的節(jié)點(diǎn)數(shù)都達(dá)到最大值，則這棵二叉樹稱為滿二叉樹

假設(shè)一棵二叉樹的層數(shù)為 K，且節(jié)點(diǎn)總數(shù)是 2^K - 1，則它就是滿二叉樹

完全二叉樹：假設(shè)一顆二叉樹有 K 層，如果這顆二叉數(shù)的前 K - 1 層是滿二叉樹，并且第 K 層是從左往右還是連續(xù)的節(jié)點(diǎn)，則這棵二叉樹稱為完全二叉樹

假設(shè)一棵完全二叉樹的層數(shù)為 K ，則完全二叉樹節(jié)點(diǎn)數(shù)的范圍：2^(K - 1) ~ 2^K - 1

完全二叉樹中度為 1 的節(jié)點(diǎn)有 0 個或 1 個

滿二叉樹可以認(rèn)為是一種特殊的完全二叉樹

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

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

由于完全二叉樹中從第二層開始，每一層的結(jié)點(diǎn)都是偶數(shù)個，因此 左孩子的編號都均為奇數(shù)，右孩子的編號都均為偶數(shù)

在 n 個節(jié)點(diǎn)的 完全二叉樹 中，對于合法的編號為 i 的節(jié)點(diǎn)有：

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