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

一、樹

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

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

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

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

樹的相關概念

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

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

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

在樹的結(jié)構(gòu)中可以發(fā)現(xiàn)，樹是不易于用數(shù)組來存儲的，因此 采用鏈式的方式來存儲樹

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

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

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

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

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

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

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

二、二叉樹

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

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

二叉樹的遞歸定義為：

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

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

二叉樹的性質(zhì)

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

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

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

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

解得：n0 = n2 + 1

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

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

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

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

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

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

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

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

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

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

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

到此這篇關于C語言中關于樹和二叉樹的相關概念的文章就介紹到這了,更多相關C語言樹和二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論