數(shù)據(jù)結(jié)構(gòu)之樹和二叉樹概念篇
前言：
前篇學(xué)習(xí)了 數(shù)據(jù)結(jié)構(gòu)的棧和隊(duì)列，那么這篇繼續(xù)學(xué)習(xí)樹及其相關(guān)內(nèi)容基礎(chǔ)內(nèi)容。
/知識(shí)點(diǎn)匯總/
1、樹的概念和結(jié)構(gòu)
概念：樹是一種非線性結(jié)構(gòu)，是由有限個(gè)節(jié)點(diǎn)組成的具有層次關(guān)系的集合。倒立的樹模樣。
有一個(gè)特殊的結(jié)點(diǎn)，稱為根節(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有前驅(qū)。
另外的子樹有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼。
因此樹是遞歸定義的。根在上，葉在下。
1.1、樹的相關(guān)概念
結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的度就是結(jié)點(diǎn)含有的子樹個(gè)數(shù)，稱為該結(jié)點(diǎn)的度。
葉子節(jié)點(diǎn)或稱為終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)就是葉子節(jié)點(diǎn)，也就是沒(méi)有孩子的結(jié)點(diǎn)。
非終端結(jié)點(diǎn)或稱為分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。
雙親結(jié)點(diǎn)或父節(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子節(jié)點(diǎn)，則該節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)。
孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個(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)的度稱為樹的度。
結(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)的祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先
子孫：以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。
森林：由若干棵互不相交的樹的集合稱為森林?？捎袠淙サ舾Y(jié)點(diǎn)轉(zhuǎn)化。
那么樹的實(shí)現(xiàn)，該如何表示呢？用數(shù)組？用鏈表？
1.2、樹的存儲(chǔ)結(jié)構(gòu)
三種方法，假設(shè)樹的度為6
方法一：
#define N 6
struct TreeNode
{
int val;
struct TreeNode* childArr[N];//指針數(shù)組
};
方法二：
struct TreeNode
{
int val;
SeqList childSL;//順序表
//SeqList，C++的庫(kù)可調(diào)用
};
方法三，最優(yōu)方法：左孩子右兄弟表示法
struct TreeNode
{
int val;
struct TreeNode* leftChild;
struct TreeNode* rightBother;
};
2、二叉樹概念及結(jié)構(gòu)
2.1、二叉樹概念
一顆二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合：
1.或者為空
2.或由一個(gè)根結(jié)點(diǎn)加上兩棵，別稱為，左子樹和右子樹的二叉樹組成。
3.二叉樹不存在度大于2的結(jié)點(diǎn)
4.二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹。
注意：對(duì)于任意的二叉樹都是由一下幾種情況復(fù)合而成的。
1.空樹
2.只有根節(jié)點(diǎn)
3.只有左子樹
4.只有右子樹
5.左右子樹均存在
二叉樹的度不一定為2，但度為2一定是二叉樹。
因?yàn)槎鏄涞亩茸畲鬄?，即0~2
2.2、滿二叉樹
一顆二叉樹，如果每一層的結(jié)點(diǎn)樹達(dá)到最大值，那么這個(gè)二叉樹就是滿二叉樹。
層數(shù)為：k,那么結(jié)點(diǎn)總數(shù)就是：2^k-1個(gè)結(jié)點(diǎn)
每一層都是滿的，即除了葉子結(jié)點(diǎn)，其余所有結(jié)點(diǎn)的度都是2，因?yàn)橹挥卸葹?或度為2的結(jié)點(diǎn)。
2.3、完全二叉樹
完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，對(duì)于深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，被稱為完全二叉樹，滿二叉樹是一種特殊的完全二叉樹。
完全二叉樹葉子節(jié)點(diǎn)只可能出現(xiàn)在最下層或次下層，并且最下層的葉子節(jié)點(diǎn)都位于左孩子（因?yàn)橐３诌B續(xù)性，不能顛倒）。
前n-1層是滿的，最后一層不一定滿（因?yàn)闈M二叉樹是完全二叉樹的特殊情況），但是從左到右必須是連續(xù)的。
高度為h的完全二叉樹第h層的結(jié)點(diǎn)數(shù)：
最多就是：2^h - 1
最少為：2^(h-1)-1+1
即：[2^(h-1), 2^h-1]
2.4、滿二叉樹或完全二叉樹的存儲(chǔ)形式
1.數(shù)組 — 一層一層的存儲(chǔ)
父子結(jié)點(diǎn)的關(guān)系：
左孩子 = 父結(jié)點(diǎn)2 +1 //奇數(shù)
右孩子 = 父結(jié)點(diǎn)2+2 //偶數(shù)
或者由孩子結(jié)點(diǎn)推父結(jié)點(diǎn)：
父結(jié)點(diǎn) = (孩子結(jié)點(diǎn)-1)/2
所以非完全二叉樹不適合數(shù)組結(jié)構(gòu)的存儲(chǔ)，知識(shí)和鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)
3、堆的概念及結(jié)構(gòu)
一般是把數(shù)組數(shù)據(jù)看作一顆完全二叉樹，并有以下要求：
小堆：任意一個(gè)父親 <= 孩子
大堆：任意一個(gè)父親 >= 孩子
3.1、堆的性質(zhì)
1.堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值
2.堆總是一顆完全二叉樹
練習(xí)題1：
下列關(guān)鍵字序列為堆的是：
A 100 60 70 50 32 65
B 60 70 65 50 32 100
C 65 100 70 32 50 60
D 70 65 100 32 50 60
舉例：
A滿足：
100
60 70
50 32 65
小結(jié)：
所以有序數(shù)組是堆，但堆不一定有序；并且這里的堆和內(nèi)存空間的堆不是同一個(gè)意義。
3.2、堆的意義
- 堆的排序 O(N*log^N) – 根結(jié)點(diǎn)是該數(shù)的最大值
- top k問(wèn)題 – 便于求頂點(diǎn)問(wèn)題的解決
- 搜索
4、二叉樹的存儲(chǔ)形式
4.1、二叉樹的數(shù)組存儲(chǔ)形式
一般使用數(shù)組只適合表示完全二叉樹，因?yàn)椴皇峭耆鏄鋾?huì)有空間的浪費(fèi)等問(wèn)題。
并且實(shí)際應(yīng)用中，也只有堆會(huì)用數(shù)組的形式存儲(chǔ)。
即二叉樹順序存儲(chǔ)在物理上是一個(gè)數(shù)組，在邏輯上是一顆二叉樹。
4.2、二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
用鏈表來(lái)指示元素的邏輯關(guān)系。
通常，以鏈表中的每一個(gè)結(jié)點(diǎn)，三個(gè)域組成，分別是數(shù)據(jù)域、左指針域和右指針域，左指針指向左孩子，右指針指向右孩子。
鏈?zhǔn)浇Y(jié)構(gòu)也分為二叉鏈和三叉鏈，一般是二叉鏈。高階數(shù)據(jù)結(jié)構(gòu)涉及三叉鏈。
補(bǔ)充知識(shí)點(diǎn)（備注：后面抽空單獨(dú)寫篇學(xué)習(xí)該部分知識(shí)點(diǎn)）：
1.搜素二叉樹：對(duì)于根節(jié)點(diǎn)來(lái)說(shuō)，根節(jié)點(diǎn)的左子樹都小于根結(jié)點(diǎn)，根節(jié)點(diǎn)的右子樹都大于根節(jié)點(diǎn)。 最多查找高度次。
2.森林：是m(m≥0)棵互不相交的樹的集合，其次森林是由樹構(gòu)成的。
3.最優(yōu)二叉樹（哈夫曼樹）：帶權(quán)路徑最小的二叉樹稱為最優(yōu)二叉樹，也稱為哈夫曼樹。
3.1.帶權(quán)路徑長(zhǎng)度：設(shè)二叉樹具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和，稱為帶權(quán)路徑長(zhǎng)度。
3.2.哈夫曼樹的定義：一棵二叉樹要使其帶權(quán)路徑長(zhǎng)度最小，必須使權(quán)值越大的葉子節(jié)點(diǎn)越靠近根節(jié)點(diǎn)，權(quán)值越小的葉子節(jié)點(diǎn)越遠(yuǎn)離根節(jié)點(diǎn)，并且不存在度為1的結(jié)點(diǎn)。
4.線索二叉樹：加上線索的二叉樹稱為線索鏈表，也稱為線索二叉樹。
4.1.線索：考慮到具有n個(gè)結(jié)點(diǎn)的二叉鏈表，在2n個(gè)指針域中只有n-1個(gè)指針域用來(lái)存儲(chǔ)孩子節(jié)點(diǎn)的地址，存在n+1個(gè)空指針域，可以利用這些空指針指向該節(jié)點(diǎn)在某種遍歷序列中的前驅(qū)或后繼結(jié)點(diǎn)，這些指向前驅(qū)和后繼結(jié)點(diǎn)的指針?lè)Q為線索，加上線索的二叉鏈表就是線索鏈表或線索二叉樹。
4.3、樹、森林與二叉樹之間的相互轉(zhuǎn)換
4.3.1、樹轉(zhuǎn)換為二叉樹
一般步驟：
1.加線：樹中所有相鄰兄弟結(jié)點(diǎn)之間加一條線；
2.去線：對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線；
3.層次調(diào)整：按照二叉樹結(jié)點(diǎn)之間的關(guān)系進(jìn)行層次調(diào)整。
樣例流程圖，如下所示：
4.3.2、森林轉(zhuǎn)換為二叉樹
一般步驟：
1.將森林中的每根樹轉(zhuǎn)換為二叉樹；
2.將每棵樹的根結(jié)點(diǎn)視為兄弟，在所有根節(jié)點(diǎn)之間加上連線；
3.按照二叉樹結(jié)點(diǎn)之間的關(guān)系進(jìn)行層次調(diào)整。
樣例流程圖，如下所示：
4.3.3、二叉樹轉(zhuǎn)換為樹或森林
一般步驟：
1.加線：若某結(jié)點(diǎn)x是其雙親y的左孩子，則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子…都與結(jié)點(diǎn)y用線連接；
2.去線：刪去原來(lái)二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線；
3.層次調(diào)整：整理1和2步驟，使之層次分明，得到樹或森林。
樣例流程圖，如下所示：
5、二叉樹的基本性質(zhì)
二叉樹的5個(gè)基本性質(zhì)：
1.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個(gè)結(jié)點(diǎn)。
2.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大節(jié)點(diǎn)數(shù)為2^h - 1個(gè)（等比數(shù)列推導(dǎo)）
3.對(duì)任何一棵二叉樹，如果度為0其葉子節(jié)點(diǎn)個(gè)數(shù)為n0，度為2的分支節(jié)點(diǎn)個(gè)數(shù)為n2，則有n0 = n2 + 1;
4.若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h = log2^n+1。
5.對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下，從左至右的數(shù)組順序?qū)λ薪Y(jié)點(diǎn)從0開始編導(dǎo)，則對(duì)于序號(hào)為i的節(jié)點(diǎn)有：
1)若i>0,i位置節(jié)點(diǎn)的雙親序號(hào)為：（i-1）/2 , i = 0時(shí)i為根節(jié)點(diǎn)編號(hào)，無(wú)雙親節(jié)點(diǎn)；
2)若2i+1<n，左孩子序號(hào)為：2i+1,2i+1>=n，否則無(wú)左孩子；
3)若2i+2<n，右孩子序號(hào)為：2i+2,2i+2>=n，否則為右孩子。
補(bǔ)充：
增加一個(gè)度為2的結(jié)點(diǎn)，一定增加一個(gè)度為0的結(jié)點(diǎn)。
增加一個(gè)度為1的結(jié)點(diǎn)，一定減少一個(gè)度為0的結(jié)點(diǎn)，增加一個(gè)度為0的結(jié)點(diǎn).
5.1、二叉樹性質(zhì)練習(xí)題
第一題：
某二叉樹共有399個(gè)節(jié)點(diǎn)，其中有199個(gè)度為2的節(jié)點(diǎn)，則該二叉樹中的葉子節(jié)點(diǎn)數(shù)為（）
A.不存在這樣的二叉樹 B.200 C.198 D.199
第二題：
下列數(shù)據(jù)結(jié)構(gòu)中，不適合采用順序存儲(chǔ)結(jié)構(gòu)的是（）
A.非完全二叉樹 B.堆 C.隊(duì)列 D.棧
第三題：
在具有2n個(gè)節(jié)點(diǎn)的完全二叉樹中，葉子節(jié)點(diǎn)個(gè)數(shù)為（）
A.n B.n+1 C.n-1 D.n/2
第四題：
一顆完全二叉樹的節(jié)點(diǎn)數(shù)為531個(gè)，那么這顆數(shù)的高度為（）
A.11 B.10 C. 8 D.12文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-795215.html
第五題：
一個(gè)具有767個(gè)節(jié)點(diǎn)的完全二叉樹，其中葉子節(jié)點(diǎn)個(gè)數(shù)為（）
A.383 B.384 C.385 D.386
參考答案：1.B 2.A 3.B 4.B 5.B文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-795215.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)之樹和二叉樹】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
