樹(shù)

樹(shù)的定義

Q：什么是樹(shù)

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

Q：樹(shù)有什么特點(diǎn)

有一個(gè)特殊的結(jié)點(diǎn)，稱(chēng)為根結(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ù)類(lèi)似的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼。

樹(shù)是遞歸定義的

對(duì)于樹(shù)的定義還需要強(qiáng)調(diào)兩點(diǎn)：

當(dāng)n>0時(shí)，根結(jié)點(diǎn)是唯一的，不可能存在多個(gè)根結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)中的樹(shù)是只能有一個(gè)根結(jié)點(diǎn)。

當(dāng)m>0時(shí)，子樹(shù)的個(gè)數(shù)沒(méi)有限制，但它們一定是互不相交的。像下圖中的結(jié)構(gòu)就不符合樹(shù)的定義，因?yàn)樗鼈兌加邢嘟坏淖訕?shù)。

樹(shù)的名詞解釋

節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的度； 如上圖：A的為3

葉節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn)； 如上圖：I,G,K,G,L,M節(jié)點(diǎn)為葉節(jié)點(diǎn)

非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)； 如上圖：B、D、C、E、F等節(jié)點(diǎn)為分支節(jié)點(diǎn)

雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個(gè)節(jié)點(diǎn)稱(chēng)為其子節(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)稱(chēng)為該節(jié)點(diǎn)的子節(jié)點(diǎn)； 如上圖：B是A的孩子節(jié)點(diǎn)

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱(chēng)為兄弟節(jié)點(diǎn)； 如上圖：B、C是兄弟節(jié)點(diǎn)

樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)的度稱(chēng)為樹(shù)的度； 如上圖：樹(shù)的度為3

節(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類(lèi)推

樹(shù)的高度或深度：樹(shù)中節(jié)點(diǎn)的最大層次； 如上圖：樹(shù)的高度為4

節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先

子孫：以某節(jié)點(diǎn)為根的子樹(shù)中任一節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫

森林：由m棵互不相交的樹(shù)的集合稱(chēng)為森林

樹(shù)的表示

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

說(shuō)到存儲(chǔ)結(jié)構(gòu)，自然就會(huì)想到我們前面講過(guò)的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種結(jié)構(gòu)。

順序存儲(chǔ)結(jié)構(gòu)：樹(shù)中某個(gè)結(jié)點(diǎn)的孩子可以有多個(gè)，若將樹(shù)中所有結(jié)點(diǎn)存儲(chǔ)到數(shù)組中，結(jié)點(diǎn)的存儲(chǔ)位置無(wú)法直接反應(yīng)其邏輯關(guān)系，因此：簡(jiǎn)單的順序存儲(chǔ)結(jié)構(gòu)是不能滿足樹(shù)的實(shí)現(xiàn)要求的

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，完全可以實(shí)現(xiàn)對(duì)樹(shù)的存儲(chǔ)結(jié)構(gòu)的表示。

表示方式：實(shí)際中樹(shù)有很多種表示方式， 如：雙親表示法，孩子表示法、孩子兄弟表示法等等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法。

代碼演示

typedef int DataType;
struct Node
{
    struct Node* _firstChild1;    // 第一個(gè)孩子結(jié)點(diǎn)
    struct Node* _pNextBrother;   // 指向其下一個(gè)兄弟結(jié)點(diǎn)
    DataType _data;               // 結(jié)點(diǎn)中的數(shù)據(jù)域
};

圖像演示

二叉樹(shù)的概念及結(jié)構(gòu)

二叉樹(shù)的概念

Q：什么是二叉樹(shù)

A：二叉樹(shù)是 n 個(gè)結(jié)點(diǎn)的有限集合。該集合或者為空集(空二叉樹(shù))或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的，分別稱(chēng)為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

Q：二叉樹(shù)有什么特點(diǎn)

每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，二叉樹(shù)不存在度大于2的結(jié)點(diǎn)。左子樹(shù)和右子樹(shù)是有順序的，次序不能任意顛倒。即使樹(shù)中某結(jié)點(diǎn)只有一棵子樹(shù)，也要區(qū)分左子樹(shù)還是右子樹(shù)。

Q：二叉樹(shù)有什么基本形式

空二叉樹(shù)只有一個(gè)根節(jié)點(diǎn)根節(jié)點(diǎn)只有左子樹(shù)根節(jié)點(diǎn)只有右子樹(shù)根節(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)

Q：特殊的二叉樹(shù)有哪些

（1）滿二叉樹(shù)：在一顆二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上，這樣的二叉樹(shù)稱(chēng)為滿二叉樹(shù)。如果一個(gè)二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿二叉樹(shù)。

（2）完全二叉樹(shù)：對(duì)于一顆具有 n 個(gè)結(jié)點(diǎn)的二叉樹(shù)按層序編號(hào)，如果編號(hào)為i（1<=i<=n）的結(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置完全相同，則稱(chēng)這棵二叉樹(shù)為完全二叉樹(shù)。滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。

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

性質(zhì)一：在二叉樹(shù)的第 i 層上至多有2^(i-1) 個(gè)結(jié)點(diǎn)。

性質(zhì)二：深度為 k 的二叉樹(shù)至多有2^(k)-1個(gè)結(jié)點(diǎn)。

性質(zhì)三：對(duì)任何一棵二叉樹(shù), 如果度為0，其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0＝n2 + 1。

性質(zhì)四：具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為

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

如果 i=1，則結(jié)點(diǎn) i 是二叉樹(shù)的根，無(wú)雙親；如果 i>1，則其雙親是結(jié)點(diǎn) 1/2

如果 2i>n，則結(jié)點(diǎn) i無(wú)左孩子；否則其左孩子是結(jié)點(diǎn)2i

如果 2i<n，則結(jié)點(diǎn) i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn)2i+1

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

順序存儲(chǔ)結(jié)構(gòu)

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

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹(shù)每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為它分配一個(gè)數(shù)據(jù)域和兩個(gè)指針域是比較自然的想法，我們稱(chēng)這樣的鏈表叫做二叉鏈表。結(jié)點(diǎn)結(jié)構(gòu)如圖：

代碼演示

typedef int BTDataType;
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft;       // 指向當(dāng)前節(jié)點(diǎn)左孩子
    struct BinTreeNode* _pRight;      // 指向當(dāng)前節(jié)點(diǎn)右孩子
    BTDataType _data;                 // 當(dāng)前節(jié)點(diǎn)值域
}

到此這篇關(guān)于C++超詳細(xì)講解樹(shù)與二叉樹(shù)的文章就介紹到這了,更多相關(guān)C++樹(shù)與二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論