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

1.1 樹(shù)的概念

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

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

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

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

樹(shù)中的一些名詞解釋：

• 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)的子樹(shù) (子節(jié)點(diǎn)) 個(gè)數(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))：若一個(gè)節(jié)點(diǎn)有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)； 如上圖：A是B的父節(jié)點(diǎn)
• 孩子節(jié)點(diǎn) (子節(jié)點(diǎn))：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的根節(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)
• 樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)的度稱為樹(shù)的度； 如上圖：樹(shù)的度為3
• 節(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；
• 樹(shù)的高度 (深度)：樹(shù)中節(jié)點(diǎn)的最大層次； 如上圖：樹(shù)的高度為4，空樹(shù)的高度是0，只有根節(jié)點(diǎn)的樹(shù)高度為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)為根的子樹(shù)中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫
• 森林：由 m (m>0) 棵互不相交的樹(shù)的集合稱為森林（并查集就是一個(gè)森林）

1.3 樹(shù)的表示

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

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

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

如果沒(méi)有說(shuō)明樹(shù)的度是多少，還可以用順序表去存儲(chǔ)。

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

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

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;   // 指向第一個(gè)孩子結(jié)點(diǎn)（即最左邊的孩子節(jié)點(diǎn)）
	struct Node* _pNextBrother; // 指向右邊的第一個(gè)兄弟結(jié)點(diǎn)
};

1.4 樹(shù)的應(yīng)用

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

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

2.1 二叉樹(shù)的概念

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

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

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

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

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

2.2 特殊的二叉樹(shù)

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

完全二叉樹(shù)：

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

2.3 二叉樹(shù)的性質(zhì)

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

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

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

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

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

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

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

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

順序存儲(chǔ)

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

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

leftchild = parent * 2 + 1

rightchild = parent * 2 + 2

parent = (child - 1) / 2

鏈?zhǔn)酱鎯?chǔ)

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

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語(yǔ)言樹(shù)與二叉樹(shù)基礎(chǔ)全刨析的文章就介紹到這了,更多相關(guān)C語(yǔ)言樹(shù)與二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論