網(wǎng)站開(kāi)發(fā)建設(shè)專(zhuān)業(yè)品牌網(wǎng)站建設(shè)制作
目錄
1.樹(shù)概念及結(jié)構(gòu)
1.1樹(shù)的概念
?1.2 樹(shù)的相關(guān)性質(zhì)
1.3 樹(shù)的表示
?1.4 樹(shù)在實(shí)際中的運(yùn)用(表示文件系統(tǒng)的目錄樹(shù)結(jié)構(gòu))
?2.二叉樹(shù)概念及結(jié)構(gòu)
2.1二叉樹(shù)概念
?2.2?特殊的二叉樹(shù)?
2.3?二叉樹(shù)的性質(zhì)
1.樹(shù)概念及結(jié)構(gòu)
1.1樹(shù)的概念
樹(shù)是一種非線(xiàn)性的數(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),稱(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ù)是遞歸定義的。
注意:樹(shù)形結(jié)構(gòu)中,子樹(shù)之間不能有交集,否則就不是樹(shù)形結(jié)構(gòu)
?1.2 樹(shù)的相關(guān)性質(zhì)
節(jié)點(diǎn)的度:一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的度; 如上圖:A的為6
葉節(jié)點(diǎn)或終端節(jié)點(diǎn)(葉子):度為0的節(jié)點(diǎn)稱(chēng)為葉節(jié)點(diǎn); 如上圖:B、C、H、I...等節(jié)點(diǎn)為葉節(jié)點(diǎn)
非終端節(jié)點(diǎn)或分支節(jié)點(diǎn):度不為0的節(jié)點(diǎn); 如上圖:D、E、F、G...等節(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ù)的度為6
節(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)互為堂兄弟;如上圖:H、I互為兄弟節(jié)點(diǎn)
節(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(m>0)棵互不相交的樹(shù)的集合稱(chēng)為森林;
1.3 樹(shù)的表示
樹(shù)結(jié)構(gòu)相對(duì)線(xiàn)性表就比較復(fù)雜了,要存儲(chǔ)表示起來(lái)就比較麻煩了,既要保存值域,也要保存結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系,實(shí)際中樹(shù)有很多種表示方式如:雙親表示法,孩子表示法、孩子雙親表示法以及孩子兄弟表示法 等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法(最合適的樹(shù)結(jié)構(gòu))。
//孩子兄弟表示法struct TreeNode
{int data;struct TreeNode * child;struct TreeNode * brother;
}
?1.4 樹(shù)在實(shí)際中的運(yùn)用(表示文件系統(tǒng)的目錄樹(shù)結(jié)構(gòu))
?2.二叉樹(shù)概念及結(jié)構(gòu)
2.1二叉樹(shù)概念
一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合,該集合:
1. 或者為空
2. 由一個(gè)根節(jié)點(diǎn)加上兩棵別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成
1. 二叉樹(shù)不存在度大于2的結(jié)點(diǎn)
2. 二叉樹(shù)的子樹(shù)有左右之分,次序不能顛倒,因此二叉樹(shù)是有序樹(shù)
對(duì)于任意的二叉樹(shù)都是由以下幾種情況復(fù)合而成的:
?2.2?特殊的二叉樹(shù)?
1. 滿(mǎn)二叉樹(shù):一個(gè)二叉樹(shù),如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值,則這個(gè)二叉樹(shù)就是滿(mǎn)二叉樹(shù)。也就是說(shuō),如果一個(gè)二叉樹(shù)的層數(shù)為K,且結(jié)點(diǎn)總數(shù)是 ,則它就是滿(mǎn)二叉樹(shù)。
2. 完全二叉樹(shù):完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹(shù)是由滿(mǎn)二叉樹(shù)而引出來(lái)的。對(duì)于深度為K 的,有n個(gè)結(jié)點(diǎn)的二叉樹(shù),當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì) 應(yīng)時(shí)稱(chēng)之為完全二叉樹(shù)。 要注意的是滿(mǎn)二叉樹(shù)是一種特殊的完全二叉樹(shù)。
PS:完全二叉樹(shù)節(jié)點(diǎn)的取值范圍:
2.3?二叉樹(shù)的性質(zhì)
1. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則一棵非空二叉樹(shù)的第i層上最多有2^(i-1)個(gè)結(jié)點(diǎn).(第i層滿(mǎn)了)
2. 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則深度為h的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是2^h-1.(滿(mǎn)二叉樹(shù))
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)多1)
完全二叉樹(shù)的度為1的節(jié)點(diǎn)要么是1個(gè)要么是0個(gè)。
?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)有:
1. 若i>0,i位置節(jié)點(diǎn)的雙親序號(hào):(i-1)/2;若i=0,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,則無(wú)右孩子?