數(shù)據(jù)結(jié)構(gòu)-樹和二叉樹ppt課件

1、第六章 樹和二叉樹,第六章 樹和二叉樹 6.1 樹的有關(guān)概念 6.2 二叉樹 6.3 二叉樹的遍歷 6.4 遍歷的應(yīng)用 6.5 * 線索二叉樹（簡單介紹） 6.6 樹和森林 6.7 哈夫曼樹及應(yīng)用,第六章 樹和二叉樹,6.1 樹的有關(guān)概念,1樹的定義,定義：樹是n個結(jié)點的有限集合。在任一棵非空樹中： （1）有且僅有一個稱為根的結(jié)點；。 （2）其余結(jié)點可分為m個互不相交的有限集合，而且這些集合中的每一集合本身又是一棵樹，稱為根的子樹,樹是遞歸結(jié)構(gòu)，在樹的定義中又用到了樹的概念,樹結(jié)構(gòu) （除了一個稱為根的結(jié)點外）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼,6.1 樹的有關(guān)概念,從邏

2、輯結(jié)構(gòu)看： 1）樹中只有根結(jié)點沒有前趨；2）除根外，其余結(jié)點都有且僅一個前趨； 3）樹的結(jié)點，可以有零個或多個后繼；4）除根外的其他結(jié)點，都存在唯一條從根到該結(jié)點的路徑； 5）樹是一種分枝結(jié)構(gòu),6.1 樹的有關(guān)概念,2樹的應(yīng)用1）樹可表示具有分枝結(jié)構(gòu)關(guān)系的對象,例1家族族譜,例2單位行政機構(gòu)的組織關(guān)系、系統(tǒng)功能模塊圖,6.1 樹的有關(guān)概念,2）樹是常用的數(shù)據(jù)組織形式 有些應(yīng)用中數(shù)據(jù)元素之間并不存在間分支結(jié)構(gòu)關(guān)系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。 例3 計算機的文件系統(tǒng) 不論是DOS文件系統(tǒng)還是window文件系統(tǒng)，所有的文件是用樹的形式來組織的,6.1 樹的有關(guān)概念,3 、

3、樹的基本術(shù)語,1）結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)。 2）樹的度：樹中各結(jié)點度的最大值,DA=3,DB=2,DC=1,DG=0,DTree=3,6.1 樹的有關(guān)概念,3）葉子結(jié)點：度為0的結(jié)點，也稱為終端結(jié)點。 4）分支結(jié)點：度不為0的結(jié)點，也稱為非終端結(jié)點,葉子結(jié)點：K,L,F,G,M,I,J,分支結(jié)點：A,B,C,D,E,H,6.1 樹的有關(guān)概念,5）孩子、雙親：樹中結(jié)點的子樹的根結(jié)點稱為這個結(jié)點的孩子結(jié)點，這個結(jié)點稱為它孩子結(jié)點的雙親結(jié)點； 6）兄弟：具有同一個雙親的孩子結(jié)點互稱為兄弟,孩子結(jié)點：B,C,D 雙親結(jié)點：A 兄弟結(jié)點：E，F(xiàn),6.1 樹的有關(guān)概念,7）路徑：如果樹的結(jié)點序列

4、n1, n2, , nk有如下關(guān)系：結(jié)點ni是ni+1的雙親，則把n1, n2, , nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度,結(jié)點序列： nA,nB, nE, nK 路經(jīng)長度=3,6.1 樹的有關(guān)概念,8）祖先、子孫：在樹中，如果有一條路徑從結(jié)點x到結(jié)點y，那么x就稱為y的祖先，而y稱為x的子孫,6.1 樹的有關(guān)概念,9）結(jié)點所在層數(shù)：根結(jié)點的層數(shù)為1；對其余任何結(jié)點，若某結(jié)點在第k層，則其孩子結(jié)點在第k+1層。 10）樹的深度：樹中所有結(jié)點的最大層數(shù)，也稱高度,6.1 樹的有關(guān)概念,11）有序樹、無序樹：如果一棵樹中結(jié)點的各子樹從左到右是有次序的（即不能互換），稱這

5、棵樹為有序樹；反之，稱為無序樹,數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹,6.1 樹的有關(guān)概念,12）森林：m (m0)棵互不相交的樹的集合,樹中每一個結(jié)點的子樹的集合即為森林,6.1 樹的有關(guān)概念,樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較,線性結(jié)構(gòu),樹結(jié)構(gòu),無前驅(qū),無雙親,無后繼,無孩子,一個前驅(qū),一個后繼,一個雙親,多個孩子,一對一 一對多,6.1 樹的有關(guān)概念,4、樹的基本操作 樹的應(yīng)用很廣，應(yīng)用不同基本操作也不同。下面列舉了樹的一些基本操作： 1）InitTree( /返回樹T的根值,6.1 樹的有關(guān)概念,8） Value(T, /按某種次序訪問樹中每個結(jié)點,6 2 二 叉 樹,樹是一種分枝結(jié)構(gòu)的對象，在樹的概念

6、中，對每一個結(jié)點孩子的個數(shù)沒有限制，因此樹的形態(tài)多種多樣，本章我們主要討論一種最簡單的樹二叉樹,6.2 二 叉 樹,一 二叉樹的概念 1 二叉樹的定義 二叉樹： 或為空樹，或由根及兩顆不相交的左子樹、右子樹構(gòu)成，并且左、右子樹本身也是二叉樹,說明： 1）二叉樹中每個結(jié)點最多有兩顆子樹；二叉樹每個結(jié)點度小于等于2; 2）左、右子樹不能顛例有序樹; 3）二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念,6.2 二 叉 樹,2 二叉樹的基本形態(tài),6.2 二 叉 樹,二、二叉樹性質(zhì) 性質(zhì)1 在二叉樹的第i 層上最多有2i-1個結(jié)點（i=1,證明： 當(dāng)i=1時，第1層只有一個根結(jié)點，結(jié)點數(shù)=20

7、=1，結(jié)論顯然成立,假設(shè)j=i-1時，結(jié)論正確，即第j層最多有2i-2,所以當(dāng)j=i時，第i層最多有2*2i-2=2i-1；結(jié)論正確,6.2 二 叉 樹,性質(zhì)2 一棵深度為k的二叉樹中，最多有2k-1個結(jié)點，最少有k個結(jié)點,證明：由性質(zhì)1可知，深度為k的二叉樹中結(jié)點個數(shù)最多 = =2k-1,每一層至少要有一個結(jié)點，因此深度為k的二叉樹，至少有k個結(jié)點,6.2 二 叉 樹,證明: 設(shè)n為二叉樹的結(jié)點總數(shù)，n1為二 叉樹中度為1的結(jié)點數(shù)，則有： nn0n1n2 在二叉樹中，除了根結(jié)點外，其余結(jié)點都有唯一的一個分枝進(jìn)入，由于這些分枝是由度為1和度為2的結(jié)點射出的，一個度為1的結(jié)點射出一個分枝，一個度

8、為2的結(jié)點射出兩個分枝，所以有： nn12n21 因此可以得到：n0n21,性質(zhì)3 在一棵二叉樹中，如果葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有: n0n21,6.2 二 叉 樹,兩種特殊的二叉樹 滿二叉樹：如果深度為k的二叉樹，有2k-1個結(jié)點則稱為滿二叉樹,滿二叉樹的特點,葉子只能出現(xiàn)在最下一層； 只有度為0和度為2的結(jié)點,滿二叉樹在同樣深度的二叉樹中結(jié)點個數(shù)最多 滿二叉樹在同樣深度的二叉樹中葉子結(jié)點個數(shù)最多,6.2 二 叉 樹,完全二叉樹 深度為K，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點都一一對應(yīng)時，稱之為完全二叉樹,6.2 二 叉 樹,在

9、滿二叉樹中，從最后一個結(jié)點開始，連續(xù)去掉任意個結(jié)點，即是一棵完全二叉樹,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,8,不是完全二叉樹，結(jié)點10與滿二叉樹中的結(jié)點10不是同一個結(jié)點,6.2 二 叉 樹,完全二叉樹的特點,1. 葉子結(jié)點只能出現(xiàn)在最下兩層； 2. 完全二叉樹中如果有度為1的結(jié)點，只可能有一個，且該結(jié)點只有左孩子。 3. 深度為k的完全二叉樹在k-1層上一定是滿二叉樹,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,8,6.2 二 叉 樹,性質(zhì)4 具有n個結(jié)點的完全二叉樹的深度為 log2n +1,6.2 二 叉 樹,

10、性質(zhì)5 對一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1in）的結(jié)點，有： （1）如果i1，則結(jié)點i的雙親結(jié)點的序號為 i/2（取整）；如果i1，則結(jié)點i是根結(jié)點，無雙親結(jié)點,6.2 二 叉 樹,2）如果2in，則結(jié)點i的左孩子的序號為2i； 如果2in，則結(jié)點i無左孩子,6.2 二 叉 樹,3）如果2i1n，則結(jié)點i的右孩子的序號為2i1； 如果2i1n，則結(jié)點 i無右孩子,6.2 二 叉 樹,對一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號，則 結(jié)點i的雙親結(jié)點為 i/2； 結(jié)點i的左孩子為2i； 結(jié)點i的右孩子為2i1,性質(zhì)5表明，在完全二叉樹中，結(jié)點的層序

11、編號反映了結(jié)點之間的邏輯關(guān)系,6.2 二 叉 樹,三二叉樹存貯結(jié)構(gòu) 1 二叉樹的順序結(jié)構(gòu),二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的結(jié)點，并且結(jié)點的存儲位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點之間的邏輯關(guān)系父子關(guān)系,如何利用數(shù)組下標(biāo)來反映結(jié)點之間的邏輯關(guān)系,完全二叉樹和滿二叉樹中結(jié)點的序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系,6.2 二 叉 樹,完全二叉樹的順序存儲,以編號 為下標(biāo),6.2 二 叉 樹,二叉樹的順序存儲,按照完全 二叉樹編號,以編號 為下標(biāo),6.2 二 叉 樹,二叉樹的順序存儲結(jié)構(gòu)一般僅 存儲完全二叉樹和滿二叉樹,6.2 二 叉 樹,2 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),1）基本思想：令二叉樹的每個結(jié)

12、點對應(yīng)一個鏈表結(jié)點，鏈表結(jié)點除了存放與二叉樹結(jié)點有關(guān)的數(shù)據(jù)信息外，還要設(shè)置指示左右孩子的指針,結(jié)點結(jié)構(gòu),其中，data：數(shù)據(jù)域，存放該結(jié)點的數(shù)據(jù)信息； lchild：左指針域，存放指向左孩子的指針； rchild：右指針域，存放指向右孩子的指針,6.2 二 叉 樹,二叉樹的二叉鏈表存儲表示： Typedef struct BiNode TElemType data; struct BiNode *lchild, *rchild;/ 左右孩子指針 BiNode, *BiTree,6.2 二 叉 樹,2）二叉鏈表 二叉鏈表中每個結(jié)點至少包含三個域：數(shù)據(jù)域、左指針域、 右指針域,在n個結(jié)點的二叉樹中

13、，有n+1個空鏈域,6.2 二 叉 樹,3 ）三叉鏈表 三叉鏈表中每個結(jié)點至少包含四個域：數(shù)據(jù)域、雙親指針域、左指針域、右指針域,結(jié)點結(jié)構(gòu),其中，data：數(shù)據(jù)域，存放該結(jié)點的數(shù)據(jù)信息； parent:雙親指針域，存放指向指向雙親節(jié)點的指針； lchild：左指針域，存放指向左孩子的指針； rchild：右指針域，存放指向右孩子的指針,rchild,6.2 二 叉 樹,第六章 樹和二叉樹,6.3 二叉樹的遍歷,一、二叉樹的遍歷方法,二叉樹的遍歷是指從根結(jié)點出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次,二叉樹遍歷操作的結(jié)果,對于線性結(jié)構(gòu)由于每個結(jié)點只有一個直接后

14、繼，遍歷是很容易的事。 二叉樹是非線性結(jié)構(gòu)，每個結(jié)點可能有兩個后繼，如何訪問二叉樹的每個結(jié)點，而且每個結(jié)點僅被訪問一次,二叉樹的遍歷方式： DLR、LDR、LRD、 DRL、RDL、RLD,如果限定先左后右，則二叉樹遍歷方式有三種： 前序：DLR 中序：LDR 后序：LRD,層序遍歷：按二叉樹的層序編號的次序訪問各結(jié)點,考慮二叉樹的組成,6.3 二叉樹的遍歷,1、先序（根）遍歷 若二叉樹為空，則空操作返回；否則： 訪問根結(jié)點； 先序遍歷根結(jié)點的左子樹； 先序遍歷根結(jié)點的右子樹,先序遍歷序列：A B D G C E F,6.3 二叉樹的遍歷,6.3 二叉樹的遍歷,2、中序（根）遍歷 若二叉樹為空

15、，則空操作返回；否則： 中序遍歷根結(jié)點的左子樹； 訪問根結(jié)點； 中序遍歷根結(jié)點的右子樹,中序遍歷序列：D G B A E C F,6.3 二叉樹的遍歷,3、后序（根）遍歷 若二叉樹為空，則空操作返回；否則： 后序遍歷根結(jié)點的左子樹； 后序遍歷根結(jié)點的右子樹； 訪問根結(jié)點,后序遍歷序列：G D B E F C A,4、層序遍歷 二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問,層序遍歷序列：A B C D E F G,6.3 二叉樹的遍歷,6.3 二叉樹的遍歷,例如,先序序列,中序序列,后序序列,A B C D E F G H

16、K,B D C A E H G K F,D C B H K G F E A,6.3 二叉樹的遍歷,二. 遍歷的遞歸算法,void Preorder (BiTree T, void( *visit)(TElemType/ 遍歷右子樹,先序遍歷遞歸算法,6.3 二叉樹的遍歷,二叉樹前序遍歷的非遞歸算法的關(guān)鍵：在前序遍歷過某結(jié)點的整個左子樹后，如何找到該結(jié)點的右子樹的根指針。 解決辦法：在訪問完該結(jié)點后，將該結(jié)點的指針保存在棧中，以便以后能通過它找到該結(jié)點的右子樹,先序遍歷非遞歸算法,先序遍歷算法的執(zhí)行軌跡,A,B,D,G,C,E,F,A,棧內(nèi)容,B,D,G,C,E,F,1.棧s初始化； 2.循環(huán)直

17、到root為空或棧s為空 2.1 當(dāng)root不空時循環(huán) 2.1.1 輸出root-data;（可將輸出變?yōu)槿魏翁幚恚?2.1.2 將指針root的值保存到棧中； 2.1.3 繼續(xù)遍歷root的左子樹 2.2 如果棧s不空，則 2.2.1 將棧頂元素彈出至root； 2.2.2 準(zhǔn)備遍歷root的右子樹,步驟,6.3 二叉樹的遍歷,void Preorder (BiTree T, void( *visit)(TElemType p=p-rchild,先序遍歷非遞歸算法（偽代碼,6.3 二叉樹的遍歷,2 中序遍歷遞歸算法,void Inorder (BiTree T, void( *visit)(

18、TElemType/ 遍歷右子樹,6.3 二叉樹的遍歷,中序遍歷非遞歸算法,void Inorder (BiTree T, void( *visit)(TElemType / 訪問結(jié)點 p=p-rchild,6.3 二叉樹的遍歷,3 后序遍歷遞歸算法,void Postorder (BiTree T, void( *visit)(TElemType / 訪問結(jié)點,若已知一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定,例如：已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABCDEFGHI 和BCAEDGHFI，如何構(gòu)造該二叉樹呢,6.3 二叉樹的遍歷,先序：A B C D

19、E F G H I 中序：B C A E D G H F I,先序：B C 中序：B C,先序： D E F G H I 中序： E D G H F I,6.3 二叉樹的遍歷,先序：F G H I 中序：G H F I,先序： D E F G H I 中序： E D G H F I,6.3 二叉樹的遍歷,第六章 樹和二叉樹,6.4 遍歷的應(yīng)用,遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，遍歷算法中對每個結(jié)點的訪問操作可以是多種形式及多個操作，根據(jù)遍歷算法的框架，適當(dāng)修改訪問操作的內(nèi)容，可以派生出很多關(guān)于二叉樹的應(yīng)用算法,6.4 遍歷的應(yīng)用,例1 編寫 求二叉樹的葉子結(jié)點個數(shù)的算法輸入：二叉樹的二叉鏈表結(jié)

20、果：二叉樹的葉子結(jié)點個數(shù) 基本思想：遍歷操作訪問二叉樹的每個結(jié)點，而且每個結(jié)點僅被訪問一次。所以可在二叉樹遍歷的過程中，統(tǒng)計葉子結(jié)點的個數(shù),void leaf(BiTree T) /n計數(shù)二叉樹的葉子結(jié)點的個數(shù)，初值n=0 if(T) if(T-lchild=null /if /leaf,例2 求二叉樹的結(jié)點個數(shù),void Count(BiNode *root) /n為全局量并已初始化為0 if (root) Count(root-lchild); n+ +; Count(root-rchild);,6.4 遍歷的應(yīng)用,例3 、求二叉樹的深度,int Depth(BiNode *root) i

21、f (root= =NULL) return 0; else hl= Depth(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1;,6.4 遍歷的應(yīng)用,二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1,6.4 遍歷的應(yīng)用,例4 為二叉樹建立二叉存儲鏈表 輸入：二叉樹的先序序列 結(jié)果：建立二叉樹的二叉存儲鏈表,按先序編歷的順序輸入先序序列（設(shè)每個元素是一個字符），建立二叉鏈表的所有結(jié)點并完成相應(yīng)結(jié)點的鏈接,為了建立一棵二叉樹，將二叉樹中每個結(jié)點的空指針引出一個虛結(jié)點，其值為一特定值如“#”，以標(biāo)識其為空，把這樣處理后的二叉樹稱為

22、原二叉樹的擴展二叉樹,擴展二叉樹的先序遍歷序列:A B # D # # C # ,6.4 遍歷的應(yīng)用,6.4 遍歷的應(yīng)用,Status CreateBiTree(BiTree /CreateBiTree,第六章 樹和二叉樹,6.5 線索二叉樹 1. 線索二叉樹的概念 2 線索鏈表 3. * 線索二叉樹的遍歷,6.5 線索二叉樹,一、 線索二叉樹,遍歷的目的： 將二叉樹中的結(jié)點按一定規(guī)律（先、中、后序）線性化的過程,問題：當(dāng)以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到某結(jié)點的左、右孩子信息，不能得到結(jié)點在某種遍歷序列中的前驅(qū)和后繼信息,解決辦法： 重新遍歷，在遍歷過程中得到前驅(qū)、后繼信息。但這種動態(tài) 訪問

23、浪費時間。 充分利用二叉鏈表的空鏈域，將遍歷過程中結(jié)點的前驅(qū)、后 繼信息保留下來,結(jié)點結(jié)構(gòu),6.5 線索二叉樹,線索：將二叉鏈表中的空指針域指向前驅(qū)結(jié)點和后繼結(jié)點的指針被稱為線索； 線索化：使二叉鏈表中結(jié)點的空鏈域存放其前驅(qū)或后繼信息的過程稱為線索化； 線索二叉樹：加上線索的二叉樹稱為線索二叉樹,ABDGCEF,DGBAECF,GDBEFCA,NULL,NULL,NULL,NULL,先序,中序,后序,DGBAECF,NULL,NULL,中序,找前驅(qū)結(jié)點 1、PLtag=1,PLchild為前驅(qū) 2、“根”P的前驅(qū)結(jié)點是中序遍歷P的左子樹時訪問的最后一個結(jié)點,找后繼結(jié)點 1、PRtag=1,PR

24、child為后繼驅(qū) 2、“根”P的后繼結(jié)點是其右子樹的“最左下端”的結(jié)點,A,頭指針,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序線索鏈表的建立過程,已經(jīng)建立起二叉鏈表,D G B A E C F,A,頭指針,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序線索鏈表的建立過程,中序遍歷二叉鏈表 p為正在訪問的結(jié)點 pre為剛訪問的結(jié)點,1,D,D G B A E C F,A,頭指針,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序線索鏈表的建立過程,中序遍歷二叉鏈表 p為正在訪問的結(jié)

25、點 pre為剛訪問的結(jié)點,1,1,D G,D G B A E C F,A,頭指針,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍歷二叉鏈表 p為正在訪問的結(jié)點 pre為剛訪問的結(jié)點,1,1,1,中序線索鏈表的建立過程,D G B,D G B A E C F,A,頭指針,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍歷二叉鏈表 p為正在訪問的結(jié)點 pre為剛訪問的結(jié)點,1,1,1,1,中序線索鏈表的建立過程,D G B A,D G B A E C F,A,頭指針,B,C,D,E,F,G,0,0,0,0,0,0,0,0

26、,0,0,0,0,0,0,中序遍歷二叉鏈表 p為正在訪問的結(jié)點 pre為剛訪問的結(jié)點,1,1,1,1,1,中序線索鏈表的建立過程,D G B A E,D G B A E C F,A,頭指針,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍歷二叉鏈表 p為正在訪問的結(jié)點 pre為剛訪問的結(jié)點,1,1,1,1,1,1,中序線索鏈表的建立過程,D G B A E C,D G B A E C F,A,頭指針,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍歷二叉鏈表 p為正在訪問的結(jié)點 pre為剛訪問的結(jié)點,1,1,1,1,1

27、,1,1,中序線索鏈表的建立過程,D G B A E C F,D G B A E C F,A,頭指針,B,C,D,E,F,G,0,0,0,0,0,0,0,0,0,0,0,0,0,0,中序遍歷二叉鏈表 p為正在訪問的結(jié)點 pre為剛訪問的結(jié)點,1,1,1,1,1,1,1,1,中序線索鏈表的建立過程,D G B A E C F,D G B A E C F,第六章 樹和二叉樹,6.6 樹和森林 一. 樹的存儲結(jié)構(gòu) 二. 樹和二叉樹的轉(zhuǎn)換 三. 樹的遍歷 四. 森林,6.6 樹和森林,一樹的存貯結(jié)構(gòu) 1、雙親表示法,基本思想：用一維數(shù)組來存儲樹的各個結(jié)點（一般按層序存儲），數(shù)組中的一個元素對應(yīng)樹中的一

28、個結(jié)點，包括結(jié)點的數(shù)據(jù)信息以及該結(jié)點的雙親在數(shù)組中的下標(biāo),6.6 樹和森林,define MAX_TREE_SIZE 100 type struct PTNode /結(jié)點結(jié)構(gòu) TEleType data; /數(shù)據(jù)域 int parent; /雙親在數(shù)組中的下標(biāo) PTNode; Typedef struct /樹結(jié)構(gòu) PTNode nodesMAX_TREE_SIZE int r,n /根的位置和結(jié)點數(shù) PTree,樹的雙親表示法實質(zhì)上是一個靜態(tài)鏈表,6.6 樹和森林,找某一結(jié)點的雙親，按照該結(jié)點的雙親下表即可找到。但求某一結(jié)點的孩子，要遍歷整個結(jié)構(gòu),6.6 樹和森林,2、孩子表示法,鏈表中的每

29、個結(jié)點包括一個數(shù)據(jù)域和多個指針域，每個指針域指向該結(jié)點的一個孩子結(jié)點,6.6 樹和森林,缺點：浪費空間,A,B,C,D,E,F,G,H,I,6.6 樹和森林,方案二： 指針域的個數(shù)等于該結(jié)點的度,其中：data：數(shù)據(jù)域，存放該結(jié)點的數(shù)據(jù)信息； degree：度域，存放該結(jié)點的度； child1childd：指針域，指向該結(jié)點的孩子,缺點：結(jié)點結(jié)構(gòu)不一致,A 2,B 3,C 2,E 1,I 0,G 0,H 0,F 0,D 0,6.6 樹和森林,6.6 樹和森林,方案三：將結(jié)點的所有孩子放在一起，構(gòu)成線性表,基本思想： 把每個結(jié)點的孩子排列起來，看成是一個線性表，且以單鏈表存儲，則n個結(jié)點共有 n 個孩子鏈表。這 n 個單鏈表共有 n 個頭指針，這 n 個頭指針又組成了一個線性表，構(gòu)成孩子鏈表的表頭數(shù)組,6.6 樹和森林,typedef struct CTNode int child; struct CTNode *next;,Typedef struct TElemType data; ChildPtr *firstchild;