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

1.1 樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由 n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

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

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

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

樹中的一些名詞解釋：

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

1.3 樹的表示

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

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

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

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

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

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

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

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

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

1.4 樹的應用

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

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

2.1 二叉樹的概念

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

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

觀察上圖，二叉樹的特點：

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

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

2.2 特殊的二叉樹

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

完全二叉樹：

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

2.3 二叉樹的性質(zhì)

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

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

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

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

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

• 若 i > 0，i 位置節(jié)點的雙親序號：(i - 1) / 2；i=0，i 為根節(jié)點編號，無雙親節(jié)點
• 若 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)，一種鏈式結(jié)構(gòu)。

順序存儲

順序存儲就是使用數(shù)組來存儲，而「數(shù)組」一般只適合表示「滿二叉樹」或「完全二叉樹」，因為不是完全二叉樹會有「空間的浪費」。在實際使用中，只有「堆」才會使用數(shù)組來存儲。二叉樹的順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

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

leftchild = parent * 2 + 1

rightchild = parent * 2 + 2

parent = (child - 1) / 2

鏈式存儲

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

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

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

最新評論