一、樹的概念和結(jié)構(gòu)

1.1 樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由 n（n>=0）個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。

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

注意：樹形結(jié)構(gòu)中，子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)。

1.2 樹的結(jié)構(gòu) & 相關(guān)名詞解釋

樹中的一些名詞解釋：

• 節(jié)點(diǎn)的度：一個節(jié)點(diǎn)的子樹 (子節(jié)點(diǎn)) 個數(shù)稱為該節(jié)點(diǎn)的度； 如上圖：A的度為3
• 葉節(jié)點(diǎn) (終端節(jié)點(diǎn))：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)； 如上圖：J、F、K、L、H、I 節(jié)點(diǎn)為葉節(jié)點(diǎn)
• 非終端節(jié)點(diǎn) (分支節(jié)點(diǎn))：度不為0的節(jié)點(diǎn)； 如上圖：B、C、D、E、G 節(jié)點(diǎn)為分支節(jié)點(diǎn)
• 雙親節(jié)點(diǎn) (父節(jié)點(diǎn))：若一個節(jié)點(diǎn)有子節(jié)點(diǎn)，則這個節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)
• 孩子節(jié)點(diǎn) (子節(jié)點(diǎn))：一個節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)
• 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)； 如上圖：B、C、D是兄弟節(jié)點(diǎn)
• 樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度； 如上圖：樹的度為3
• 節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
• 樹的高度 (深度)：樹中節(jié)點(diǎn)的最大層次； 如上圖：樹的高度為4，空樹的高度是0，只有根節(jié)點(diǎn)的樹高度為1
• 堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：F、G互為堂兄弟節(jié)點(diǎn)
• 節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先，K的祖先是A、C、G
• 子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫
• 森林：由 m (m>0) 棵互不相交的樹的集合稱為森林（并查集就是一個森林）

1.3 樹的表示

樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了，既然保存值域，也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系。實(shí)際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法、孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法。

定義樹的結(jié)構(gòu)，首先需要說明樹的度是多少，否則很難去定義。

struct TreeNode
{
    int data; // 數(shù)據(jù)域
	struct TreeNode* subs[3]; // 此樹的度為3
};

如果沒有說明樹的度是多少，還可以用順序表去存儲。

struct TreeNode
{
    int data; // 數(shù)據(jù)域
    SeqList subs; // 順序表中存儲的是樹節(jié)點(diǎn)指針
    // C++可以這樣寫：vector<struct TreeNode*> subs;
};

再介紹一種雙親表示法，樹的結(jié)構(gòu)中，往下走，孩子節(jié)點(diǎn)可能有很多，但往上走，每個節(jié)點(diǎn)的雙親結(jié)點(diǎn)只有一個。

struct TreeNode
{
    int data; // 數(shù)據(jù)域
    struct TreeNode* parent; // 記錄該節(jié)點(diǎn)的雙親結(jié)點(diǎn)
};

上述方法都不是很實(shí)用，最實(shí)用的表示方法是孩子兄弟表示法。左孩子右兄弟。

typedef int DataType;
struct Node
{
    DataType _data;             // 結(jié)點(diǎn)中的數(shù)據(jù)域
	struct Node* _firstChild;   // 指向第一個孩子結(jié)點(diǎn)（即最左邊的孩子節(jié)點(diǎn)）
	struct Node* _pNextBrother; // 指向右邊的第一個兄弟結(jié)點(diǎn)
};

1.4 樹的應(yīng)用

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

二、二叉樹的概念 & 存儲結(jié)構(gòu)（重要）

2.1 二叉樹的概念

一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合：

由一個根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成，或者為空

觀察上圖，二叉樹的特點(diǎn)：

• 二叉樹不存在度大于2的結(jié)點(diǎn) (每個節(jié)點(diǎn)最多有兩個孩子)。
• 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。

注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：

2.2 特殊的二叉樹

滿二叉樹：一個二叉樹，如果每一個層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為 K，且結(jié)點(diǎn)總數(shù)是 2k - 1 ( 20 + 21 + 22 + … + 2k-1 )，則它就是滿二叉樹。

完全二叉樹：

• 完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)。
• 一個深度為 K 的有 n 個結(jié)點(diǎn)的二叉樹，對樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為 K 的滿二叉樹中編號從 1 至 n 的結(jié)點(diǎn)一一對應(yīng)時稱之為完全二叉樹。注：滿二叉樹是一種特殊的完全二叉樹。
• 前 k 層都是滿的，最后一層不一定滿，但最后一層從左到右必須是連續(xù)的。
• 深度為 k 的完全二叉樹的節(jié)點(diǎn)個數(shù)最多為 2k - 1，最少為 2k-1 - 1 + 1（前k層節(jié)點(diǎn)個數(shù)總和+1，因?yàn)榈趉層至少有一個），所以節(jié)點(diǎn)個數(shù)范圍是：[ 2k-1, 2k - 1 ]

2.3 二叉樹的性質(zhì)

1.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第 i 層上最多有 2i-1 個結(jié)點(diǎn)。

2.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則**高度(深度)為 h 的二叉樹的「最大結(jié)點(diǎn)數(shù)」**是 2h - 1。

3.對任何一棵二叉樹，如果度為 0 的葉結(jié)點(diǎn)個數(shù)為 n0，度為 2 的分支結(jié)點(diǎn)個數(shù)為 n2，則有 n0＝n2 ＋1（度為 0 的節(jié)點(diǎn) 比 度為 2 的節(jié)點(diǎn) 多一個）

4.若規(guī)定根節(jié)點(diǎn)的層數(shù)為 1，具有 n 個結(jié)點(diǎn)的「滿二叉樹」的高度(深度) h = log2(n+1)。 (log以2為底，n+1為對數(shù))

5.對于具有 n 個結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從 0 開始編號，則對于序號為 i 的結(jié)點(diǎn)有：

• 若 i > 0，i 位置節(jié)點(diǎn)的雙親序號：(i - 1) / 2；i=0，i 為根節(jié)點(diǎn)編號，無雙親節(jié)點(diǎn)
• 若 2i + 1 < n，左孩子序號：2i + 1，2i + 1 >= n否則無左孩子
• 若 2i + 2 < n，右孩子序號：2i + 2，2i + 2 >= n否則無右孩子

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

二叉樹一般可以使用兩種結(jié)構(gòu)來存儲，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

順序存儲

順序存儲就是使用數(shù)組來存儲，而「數(shù)組」一般只適合表示「滿二叉樹」或「完全二叉樹」，因?yàn)椴皇峭耆鏄鋾小缚臻g的浪費(fèi)」。在實(shí)際使用中，只有「堆」才會使用數(shù)組來存儲。二叉樹的順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

在數(shù)組中用下標(biāo)來表示樹中的父子關(guān)系，滿足以下關(guān)系：

leftchild = parent * 2 + 1

rightchild = parent * 2 + 2

parent = (child - 1) / 2

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

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素間的邏輯關(guān)系。通常的方法是鏈表中每個結(jié)點(diǎn)由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來記錄該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲地址。鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，目前我們學(xué)的一般都是二叉鏈（紅黑樹等才會用到三叉鏈）

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
	BTDataType data; // 數(shù)據(jù)域
	struct BinaryTreeNode* leftchild;  // 指向當(dāng)前節(jié)點(diǎn)的左孩子
	struct BinaryTreeNode* rightchild; // 指向當(dāng)前節(jié)點(diǎn)的右孩子
};
// 三叉鏈
struct BinaryTreeNode
{
	BTDataType data; // 數(shù)據(jù)域
	struct BinaryTreeNode* leftchild;  // 指向當(dāng)前節(jié)點(diǎn)的左孩子
	struct BinaryTreeNode* rightchild; // 指向當(dāng)前節(jié)點(diǎn)的右孩子
	struct BinaryTreeNode* parent;     // 指向當(dāng)前節(jié)點(diǎn)的雙親
};

到此這篇關(guān)于C語言樹與二叉樹基礎(chǔ)全刨析的文章就介紹到這了,更多相關(guān)C語言樹與二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論