數(shù)據(jù)結(jié)構(gòu)章樹和叉樹

《數(shù)據(jù)結(jié)構(gòu)章樹和叉樹》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第6章樹和二叉樹（Tree&BinaryTree2021/9/9數(shù)據(jù)結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容2021/9/9數(shù)據(jù)結(jié)構(gòu)3第1章緒論第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第9章查找第10章內(nèi)排序目錄2021/9/9數(shù)據(jù)結(jié)構(gòu)4目錄6.1樹的定義和基本術(shù)語16.2二叉樹26.3遍歷二叉樹和線索二叉樹36.4樹和森林46.5赫夫曼樹及其應(yīng)用5782021/9/9數(shù)據(jù)結(jié)構(gòu)56.1樹的基本概念特點(diǎn)：非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼。6.1.1樹的定義注1：過去許多書籍中都定義樹為n≥1，曾經(jīng)有“空樹不

2、是樹”的說法，但現(xiàn)在樹的定義已修改。注2：樹的定義具有遞歸性，即“樹中還有樹”。由n個(gè)(n≥0)結(jié)點(diǎn)組成的有限集合T，有且僅有一個(gè)結(jié)點(diǎn)稱為根（root），當(dāng)n>1時(shí)，其余的結(jié)點(diǎn)分為m(m≥0)個(gè)互不相交的有限集合T1,T2，…，Tm。每個(gè)集合本身又是棵樹，被稱作這個(gè)根的子樹。ABCGEIDHFJFLK2021/9/9數(shù)據(jù)結(jié)構(gòu)66.1.2樹的邏輯表示方法一對(duì)多（1:n），有多個(gè)直接后繼（如家譜樹、目錄樹等等），但只有一個(gè)根結(jié)點(diǎn)，且子樹之間互不相交。特點(diǎn)：樹的5種表示法：圖形表示法嵌套集合表示法廣義表表示法凹入表示法左孩子－右兄弟表示法202

3、1/9/9數(shù)據(jù)結(jié)構(gòu)7圖形表示法教師學(xué)生其他人員2009級(jí)2010級(jí)2011級(jí)2012級(jí)……遼寧工程技術(shù)大學(xué)電氣系電信學(xué)院外語系……葉子根子樹2021/9/9數(shù)據(jù)結(jié)構(gòu)8嵌套集合表示法2021/9/9數(shù)據(jù)結(jié)構(gòu)9(A(B(E(K,L),F),C(G),D(H(M),I,J))約定：根作為由子樹森林組成的表的名字寫在表的左邊廣義表表示法2021/9/9數(shù)據(jù)結(jié)構(gòu)10凹入表示法又稱目錄表示法2021/9/9數(shù)據(jù)結(jié)構(gòu)11ABCDEFGHIJKLMdata左孩子右兄弟左孩子－右兄弟表示法多叉樹轉(zhuǎn)為了二叉樹2021/9/9數(shù)據(jù)結(jié)構(gòu)126.1.3若干術(shù)語——

4、即上層的那個(gè)結(jié)點(diǎn)(直接前驅(qū))——即下層結(jié)點(diǎn)的子樹的根(直接后繼)——同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）——即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)——即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)ABCGEIDHFJFLK根葉子森林有序樹無序樹——即根結(jié)點(diǎn)(沒有前驅(qū))——即終端結(jié)點(diǎn)(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個(gè)數(shù))雙親孩子兄弟堂兄弟祖先子孫——結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）——結(jié)點(diǎn)各子樹可互換位置。2021/9/9數(shù)據(jù)結(jié)構(gòu)13樹的度樹的深度(或高度)ABCGEIDHFJF

5、LK——所有結(jié)點(diǎn)度中的最大值（Max{各結(jié)點(diǎn)的度}）——指所有結(jié)點(diǎn)中最大的層數(shù)（Max{各結(jié)點(diǎn)的層次}）問：右上圖中的結(jié)點(diǎn)數(shù)＝；樹的度＝；樹的深度＝——即樹的數(shù)據(jù)元素——結(jié)點(diǎn)掛接的子樹數(shù)結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)——從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）——即度為0的結(jié)點(diǎn)，即葉子——即度不為0的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）（有幾個(gè)直接后繼就是幾度，亦稱“次數(shù)”）13342021/9/9數(shù)據(jù)結(jié)構(gòu)146.2二叉樹為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹？二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹，不失一般性

6、。6.2.1二叉樹的定義6.2.2二叉樹的性質(zhì)6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)2021/9/9數(shù)據(jù)結(jié)構(gòu)156.2.1二叉樹的定義定義：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。邏輯結(jié)構(gòu)：一對(duì)二（1:2）基本特征:①每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2的結(jié)點(diǎn)）；②左子樹和右子樹次序不能顛倒。問：具有3個(gè)結(jié)點(diǎn)的二叉樹可能有幾種不同形態(tài)？有5種基本形態(tài)：一般的樹有幾種？2021/9/9數(shù)據(jù)結(jié)構(gòu)166.2.2二叉樹的性質(zhì)(3+2)討論1：第i層的結(jié)點(diǎn)數(shù)最多是多少？（利用二進(jìn)制性質(zhì)可輕松求出）

7、性質(zhì)1:在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>0）。性質(zhì)2:深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k>0）。再提問：第i層上至少有個(gè)結(jié)點(diǎn)？1討論2：深度為k的二叉樹，最多有多少個(gè)結(jié)點(diǎn)？（利用二進(jìn)制性質(zhì)可輕松求出）2i-1個(gè)2k-1個(gè)2021/9/9數(shù)據(jù)結(jié)構(gòu)17性質(zhì)3:對(duì)于任何一棵二叉樹，若度為2的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）證明：∵二叉樹中全部結(jié)點(diǎn)數(shù)n＝n0+n1+n2(葉子數(shù)＋1度結(jié)點(diǎn)數(shù)＋2度結(jié)點(diǎn)數(shù))又∵二叉樹中全部結(jié)點(diǎn)數(shù)n＝B+1(總分支數(shù)＋根結(jié)點(diǎn))（除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)必有一個(gè)直接前趨，即

8、一個(gè)分支）而總分支數(shù)B=n1+2n2(1度結(jié)點(diǎn)必有1個(gè)直接后繼，2度結(jié)點(diǎn)必有2個(gè))三式聯(lián)立可得：n0+n1+n2=n1+2n2+1,即n0=n2+1物理意義：葉子數(shù)＝度為2結(jié)點(diǎn)數(shù)＋1討論3：二