資源描述：
《第8章樹和二叉樹》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、第8章樹和二叉樹樹二叉樹二叉樹設計二叉樹遍歷線索二叉樹哈夫曼樹等價問題樹與二叉樹的轉(zhuǎn)換樹的遍歷主要知識點8.1樹1.樹的定義樹是由n(n≥0)個結(jié)點組成的有限集合T。n=0的樹稱為空樹；對n>0的樹，有:(1)僅有一個特殊的結(jié)點稱為根結(jié)點，根結(jié)點沒有前驅(qū)結(jié)點；(2)當n>1時，除根結(jié)點外其余的結(jié)點分為m(m>0)個互不相交的有限集合T1,T2，…，Tm，其中每個集合Ti本身又是一棵結(jié)構(gòu)和樹類似的子樹。注：樹的定義具有遞歸性，即“樹中還有樹”。若干術語結(jié)點：由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關系的指針組成ABC
2、GEIDHFJFLK結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)葉結(jié)點：度為0的結(jié)點，也稱作終端結(jié)點分支結(jié)點：度不為0的結(jié)點孩子結(jié)點：樹中一個結(jié)點的子樹的根結(jié)點雙親結(jié)點：若樹中某結(jié)點有孩子結(jié)點，則這個結(jié)點就稱作它的孩子結(jié)點的雙親結(jié)點兄弟結(jié)點：具有相同的雙親結(jié)點的結(jié)點樹的度：樹中所有結(jié)點的度的最大值結(jié)點的層次：從根結(jié)點到樹中某結(jié)點所經(jīng)路徑上的分支數(shù)樹的深度：樹中所有結(jié)點的層次的最大值無序樹：樹中任意一個結(jié)點的各孩子結(jié)點之間的次序構(gòu)成無關緊要的樹有序樹：樹中任意一個結(jié)點的各孩子結(jié)點有嚴格排列次序的樹森林：m（m≥0）棵
3、樹的集合2.樹的表示方法(1)直觀表示法(2)形式化表示法(3)凹入表示法T=（D，R）DF=D1∪D2∪…∪Dm（1≤i,j≤m,Di∩Dj=￠）R={,i=1,2,…,n-1}ABCDEFGHIJKL3.樹的抽象數(shù)據(jù)類型數(shù)據(jù)集合:樹的結(jié)點集合，每個結(jié)點由數(shù)據(jù)元素和構(gòu)造數(shù) 據(jù)元素之間關系的指針組成。操作集合:（1）創(chuàng)建MakeTree(T)（2）撤消DestroyTree(T)（3）雙親結(jié)點Parent(T,curr)（4）左孩子結(jié)點LeftChild(T,curr)（5）右
4、兄弟結(jié)點RightSibling(T,curr)（6）遍歷樹Traverse(T,Visit())4.樹的存儲結(jié)構(gòu)樹的結(jié)點之間的邏輯關系主要有雙親-孩子關系，兄弟關系。因此，從結(jié)點之間的邏輯關系分，樹的存儲結(jié)構(gòu)主要有：雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法四種組合。指針有常規(guī)指針和仿真指針4H2G1F1E1D0C0B-1AI4dataparent012345678ABDEFHICG(1)雙親表示法(a)一棵樹（b)仿真指針的雙親表示法存儲結(jié)構(gòu)樹及其使用仿真指針的雙親表示法(2)孩子表示法
5、常規(guī)指針的孩子表示法rootBA∧CDEFGHI∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧雙親孩子表示法存儲結(jié)構(gòu)(3)雙親孩子表示法∧4H2G1F1E1D0C0B-1AI4dataparenthead012345678∧∧∧∧childnext∧87∧∧∧123456(4)孩子兄弟表示法常規(guī)指針的孩子兄弟表示法root∧BCDEFGHI∧∧∧∧∧∧∧∧∧A8.2二叉樹一、二叉樹：是n(n≥0)個結(jié)點的有限集合。n=0的樹稱為空二叉樹；n>0的二叉樹由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹
6、組成。邏輯結(jié)構(gòu)：一對二（1:2）基本特征:①每個結(jié)點最多只有兩棵子樹（不存在度大于2的結(jié)點）；②左子樹和右子樹次序不能顛倒。所以下面是兩棵不同的樹1.二叉樹的定義BACEDFGBACEDFG二、滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上，這樣的二叉樹稱為滿二叉樹。三、完全二叉樹：如果一棵深度為k，有n個結(jié)點的二叉樹中各結(jié)點能夠與深度為k的順序編號的滿二叉樹從1到n標號的結(jié)點相對應的二叉樹稱為完全二叉樹。如下圖所示BACEDFGHIJKLMNO(a)滿二叉
7、樹BACEDFGHIJ(b)完全二叉樹問題:一個高度為h的完全二叉樹最多有多少個結(jié)點?最少有多少個結(jié)點?數(shù)據(jù)集合：二叉樹的結(jié)點集合，每個結(jié)點由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關系的指針組成。操作集合：（1）創(chuàng)建MakeTree(T)（2）撤消DestroyTree(T)（3）左插入結(jié)點InsertLeftNode(curr,x)（4）右插入結(jié)點InsertRightNode(curr,x)（5）左刪除子樹DeleteLeftTree(curr)（6）右刪除子樹DeleteRightTree(curr)（7）遍
8、歷二叉樹Traverse(T,Visit())2.二叉樹抽象數(shù)據(jù)類型3.二叉樹的性質(zhì)性質(zhì)1在一棵非空二叉樹的第i層上至多有2i個結(jié)點（i≥0）。性質(zhì)2深度為k的二叉樹至多有2k+1-1個結(jié)點。說明：深度k=-1，表示沒有一個結(jié)點；深度k=0，表示只有一個根結(jié)點。性質(zhì)3對于一棵非空的二叉樹，如果葉結(jié)點個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有n0=n2+1。證明：設n為二叉樹的結(jié)點總數(shù)，n1為二叉樹中度為1的結(jié)點個數(shù)，則有：n=n0+n1+n2另
