樹和二叉樹課件

1、2021/3/271 線性結(jié)構(gòu)線性結(jié)構(gòu) A , B , C , ,X ,Y , Z 學(xué) 生 成 績 表 86胡孝臣 95劉忠賞 100張卓 成績姓名學(xué)號 線性表線性表結(jié)點間是以線性關(guān)系聯(lián)結(jié)結(jié)點間是以線性關(guān)系聯(lián)結(jié) 2021/3/272 樹形結(jié)構(gòu)樹形結(jié)構(gòu) 全校學(xué)生檔案管理的組織方式全校學(xué)生檔案管理的組織方式 2021/3/273 樹形結(jié)構(gòu)樹形結(jié)構(gòu) 結(jié)點間具有分層次的連接關(guān)系結(jié)點間具有分層次的連接關(guān)系 H BCD EFG A 2021/3/274 第六章第六章 樹和二叉樹樹和二叉樹 6.1 樹的定義樹的定義 由由n(n0)n(n0)個結(jié)點個結(jié)點組成的組成的有限集合有限集合。僅有一個根結(jié)點。僅有一個根

2、結(jié)點, ,結(jié)點間有結(jié)點間有 明顯的明顯的層次層次結(jié)構(gòu)關(guān)系。結(jié)構(gòu)關(guān)系。n1n1時時, ,其余結(jié)點可分為其余結(jié)點可分為m(m0)m(m0)個互不相交的個互不相交的 有限集有限集T T1 1,T,T2 2,.,T,.,Tm m，其中每一個集合本身又是一棵樹，稱為根的子其中每一個集合本身又是一棵樹，稱為根的子 樹。樹。 A C G T2 D H I T3 J M B E L K T1 F 現(xiàn)實世界中現(xiàn)實世界中,能用樹的結(jié)構(gòu)表示的例子能用樹的結(jié)構(gòu)表示的例子: 學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。 2021/3/275 介紹幾個概念介紹幾

3、個概念: 結(jié)點（結(jié)點（Node）:樹中的元素樹中的元素,包含包含數(shù)據(jù)項數(shù)據(jù)項及若干指向其子樹的及若干指向其子樹的分支分支。 結(jié)點的度（結(jié)點的度（Degree）：結(jié)點擁有的結(jié)點擁有的子樹數(shù)子樹數(shù)。 葉子（葉子（Leaf）：度為零度為零的結(jié)點的結(jié)點,也稱端結(jié)點也稱端結(jié)點。 孩子（孩子（Child）：結(jié)點結(jié)點子樹的根子樹的根稱為該結(jié)點的孩子結(jié)點稱為該結(jié)點的孩子結(jié)點。 雙親（雙親（Parent）：孩子結(jié)點的孩子結(jié)點的上層上層結(jié)點，稱為這些結(jié)點的雙親。結(jié)點，稱為這些結(jié)點的雙親。 兄弟（兄弟（Sibling）：同一雙親同一雙親的孩子的孩子。 結(jié)點的層次：結(jié)點的層次：從根結(jié)點開始算起，根為第一層從根結(jié)點開始

4、算起，根為第一層。 深度（深度（Depth)： 樹中結(jié)點的樹中結(jié)點的最大層次數(shù)最大層次數(shù)。 森林（森林（Forest）：m(m0)棵棵互不相交互不相交的樹的的樹的集合集合。 2021/3/276 A C G T2 D H I T3 J M B E L K T1 F 2021/3/277 因為樹的每個結(jié)點的度不同因為樹的每個結(jié)點的度不同,存儲困難存儲困難,使對樹的處理算法很使對樹的處理算法很 復(fù)雜。所以引出二叉樹的討論。復(fù)雜。所以引出二叉樹的討論。 樹的基本操作樹的基本操作: 構(gòu)造樹、銷毀樹、插入、刪除、遍歷等。構(gòu)造樹、銷毀樹、插入、刪除、遍歷等。 2021/3/278 6.2 二叉樹二叉樹 （

5、Binary Tree） 1 、二叉樹的定義及其性質(zhì)、二叉樹的定義及其性質(zhì) (1) 二叉樹的定義二叉樹的定義 二叉樹的五種基本形態(tài)二叉樹的五種基本形態(tài) 二叉樹是另外一種樹型結(jié)構(gòu)二叉樹是另外一種樹型結(jié)構(gòu),特點是樹中每個結(jié)點只有兩棵子特點是樹中每個結(jié)點只有兩棵子 樹樹,且子樹有左右之分，次序不能顛倒。且子樹有左右之分，次序不能顛倒。 空二叉樹空二叉樹 僅有僅有 根結(jié)點根結(jié)點 右子樹右子樹 為空為空 左子樹左子樹 為空為空 左右子樹左右子樹 均非空均非空 2021/3/279 二叉二叉樹樹是是n(nn(n 0)0)個結(jié)點的有限集合。它或為空個結(jié)點的有限集合。它或為空 樹樹( (n=0),n=0),或

6、由一個根結(jié)點和兩棵分別稱為根的左子或由一個根結(jié)點和兩棵分別稱為根的左子 樹和右子樹的互不相交的二叉樹組成。樹和右子樹的互不相交的二叉樹組成。 特別要注意特別要注意: :二叉樹不是二叉樹不是樹的特殊情況。樹的特殊情況。 a aa a b bb b 兩棵不同的二叉樹兩棵不同的二叉樹 2021/3/2710 二叉樹的基本操作二叉樹的基本操作: 構(gòu)造二叉樹、銷毀二叉樹、插入、刪除、遍歷等。構(gòu)造二叉樹、銷毀二叉樹、插入、刪除、遍歷等。 2021/3/2711 InsertChild(T,p,LR,c); 初始條件初始條件: :二叉樹二叉樹T T存在存在,p,p指向指向T T中某個結(jié)點中某個結(jié)點,LR,L

7、R為為0 0或或1 1，非空二叉樹，非空二叉樹c c 與與T T不相交且右子樹為空。不相交且右子樹為空。 操作結(jié)果操作結(jié)果: :根據(jù)根據(jù)LRLR為為0 0或或1 1，插入，插入c c為為T T中中p p所指結(jié)點的左或右子樹。所指結(jié)點的左或右子樹。p p所指結(jié)所指結(jié) 點的原有左或右子樹則成為點的原有左或右子樹則成為c c的右子樹。的右子樹。 A B C c 4 2 1 3 56 T p LR=0 5 4 2 1 3 6 T p A B C c 2021/3/2712 InsertChild(T,p,LR,c); 初始條件初始條件: :二叉樹二叉樹T T存在存在,p,p指向指向T T中某個結(jié)點中某

8、個結(jié)點,LR,LR為為0 0或或1 1，非空二叉樹，非空二叉樹c c 與與T T不相交且右子樹為空。不相交且右子樹為空。 操作結(jié)果操作結(jié)果: :根據(jù)根據(jù)LRLR為為0 0或或1 1，插入，插入c c為為T T中中p p所指結(jié)點的左或右子樹。所指結(jié)點的左或右子樹。p p所指結(jié)所指結(jié) 點的原有左或右子樹則成為點的原有左或右子樹則成為c c的右子樹。的右子樹。 A B C c 4 2 1 3 56 T p LR=1 6 5 4 2 1 3 T p A B C c 2021/3/2713 DeleteChild(T,p,LR); 初始條件初始條件: :二叉樹二叉樹T T存在存在,p,p指向指向T T中

9、某個結(jié)點中某個結(jié)點,LR,LR為為0 0或或1 1。 操作結(jié)果操作結(jié)果: :根據(jù)根據(jù)LRLR為為0 0或或1 1，刪除，刪除T T中中p p所指結(jié)點的左或右子樹。所指結(jié)點的左或右子樹。 4 2 1 3 56 T p LR=0 4 2 1 3 56 T p LR=1 4 2 1 3 56 T p 2021/3/2714 練習(xí)練習(xí): 給出給出InsertChild(T,p,LR,c)后的結(jié)果后的結(jié)果, 其中其中T,c如下圖所如下圖所 示示, LR=0。 A B C c7 4 2 1 3 56 T p LR=0 4 2 1 3 6 T p A B C c 5 7 2021/3/2715 A、 二叉樹

10、的第i層上至多有2 i-1（i 1）個結(jié)點。 (2) 二叉樹的基本性質(zhì)二叉樹的基本性質(zhì) 4 23 1 6 7 89 1 0 1 1 1 2 1 3 1 4 1 5 5 第三層上第三層上( (i=3),i=3),有有2 23-1 3-1=4 =4個節(jié)點。個節(jié)點。 第四層上第四層上( (i=4),i=4),有有2 24-1 4-1=8 =8個節(jié)點。個節(jié)點。 2021/3/2716 A、 二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點。 B、 深度為h的二叉樹中至多有2h-1個結(jié)點。 (2) 二叉樹的基本性質(zhì)二叉樹的基本性質(zhì) 4 23 1 6 7 89 1 0 1 1 1 2 1 3 1 4 1

11、5 5 此樹的深度此樹的深度h=4,h=4,共有共有2 24 4-1=15-1=15個節(jié)點。個節(jié)點。 2021/3/2717 A、 二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點。 B、 深度為h的二叉樹中至多含有2h-1個結(jié)點。 C、 若在任意一棵二叉樹中,有n0個葉子結(jié)點, 有n2個度為2的結(jié)點，則:n0=n2+1 (2) 二叉樹的基本性質(zhì)二叉樹的基本性質(zhì) 4 23 1 6 7 89 1 0 1 1 1 2 1 3 1 4 1 5 5 n n0 0=8=8 n n2 2=7=7 2021/3/2718 性質(zhì)性質(zhì)1:二叉樹的第二叉樹的第i層上至多有層上至多有2 i-1（i 1）個結(jié)點。個結(jié)

12、點。 證明證明:根據(jù)二叉樹的特點根據(jù)二叉樹的特點,結(jié)論是顯然的。結(jié)論是顯然的。 性質(zhì)性質(zhì)2:深度為深度為h的二叉樹中至多含有的二叉樹中至多含有2h-1個結(jié)點。個結(jié)點。 證明證明:深度為深度為h的二叉樹最多有的二叉樹最多有h層層,根據(jù)性質(zhì)根據(jù)性質(zhì)1,只要將第只要將第1層到第層到第 h層的最大結(jié)點數(shù)相加，就可得到整個二叉樹中結(jié)點的最大值層的最大結(jié)點數(shù)相加，就可得到整個二叉樹中結(jié)點的最大值 。 21-1 + 2 2-1+ 2 h-1 = 2 h-1 性質(zhì)性質(zhì)3:度為度為0的結(jié)點總比度為的結(jié)點總比度為2的結(jié)點多一個的結(jié)點多一個,即即 n0= n2+1 。 證明證明:設(shè)有設(shè)有n0個葉子結(jié)點個葉子結(jié)點,有

13、有n1個度為個度為1的結(jié)點的結(jié)點,有有n2個度為個度為2的結(jié)點，的結(jié)點， 則二叉樹中結(jié)點總數(shù)為則二叉樹中結(jié)點總數(shù)為：n=n0+n1+ n2 設(shè)所有進入分支的總數(shù)為設(shè)所有進入分支的總數(shù)為m,則總的結(jié)點個數(shù)為：則總的結(jié)點個數(shù)為：n=m+1 總的射出分支與總的進入分支數(shù)相等：總的射出分支與總的進入分支數(shù)相等：m= n1+2 n2 因此：因此： n0+n1+ n2 = n1+2 n2 +1 所以：所以： n0= n2+1 2021/3/2719 （3）滿二叉樹）滿二叉樹 4 23 1 6 7 89 1 0 111 2 1 3 1 4 1 5 5 特點特點: :每一層上都含有最大結(jié)點數(shù)。每一層上都含有最

14、大結(jié)點數(shù)。 2021/3/2720 4 23 1 67 89 10 11 12 5 非完全二叉樹非完全二叉樹 （4）完全二叉樹）完全二叉樹 4 23 1 67 89 10 11 12 5 完全二叉樹完全二叉樹 特點特點: :除最后一層外除最后一層外, ,每一層都取最大結(jié)點數(shù)每一層都取最大結(jié)點數(shù), , 最后一層結(jié)點都集中在該層最左邊的若干位置。最后一層結(jié)點都集中在該層最左邊的若干位置。 2021/3/2721 （5）樹與二叉樹的區(qū)別）樹與二叉樹的區(qū)別 A樹中結(jié)點的最大度數(shù)沒有限制樹中結(jié)點的最大度數(shù)沒有限制,二叉樹結(jié)點最大度數(shù)為二叉樹結(jié)點最大度數(shù)為2。 B樹的結(jié)點無左、右之分樹的結(jié)點無左、右之分,

15、二叉樹的結(jié)點子樹有明確的左、右之分。二叉樹的結(jié)點子樹有明確的左、右之分。 樹 二叉樹 2021/3/2722 2、二叉樹的存儲結(jié)構(gòu)、二叉樹的存儲結(jié)構(gòu) (2) 鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu) (1) 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) (1) 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 用一組連續(xù)的存儲單元存放二叉樹的用一組連續(xù)的存儲單元存放二叉樹的 數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置 蘊含著結(jié)點之間的關(guān)系。蘊含著結(jié)點之間的關(guān)系。 T16 若雙親結(jié)點在數(shù)組中若雙親結(jié)點在數(shù)組中i下標(biāo)處下標(biāo)處,其左孩子在其左孩子在2*i處處,右孩子在右孩子在2*i+1處。處。 1 1 A B C F E D 1 2 4

16、 8 910 5 6 3 7 1 2 1 3 1 4 1 5 2h-1=24-1 = 15 0000FE000DC0BA 1 5 1 4 1 3 1 2 1 1 1 0 9876543210 0 一般二叉樹必須按完全二叉樹的形式存儲一般二叉樹必須按完全二叉樹的形式存儲,將造成存儲的浪費。將造成存儲的浪費。 2021/3/2723 (2) 鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu) lchildDatarchild A D B C EF 圖為一般二叉圖為一般二叉 樹的二叉鏈表樹的二叉鏈表 結(jié)構(gòu)結(jié)構(gòu) A E C B D F 每個結(jié)點由數(shù)據(jù)域、左指針域和右指針域組成。每個結(jié)點由數(shù)據(jù)域、左指針域和右指針域組成。 202

17、1/3/2724 鏈式存儲結(jié)構(gòu)的描述鏈式存儲結(jié)構(gòu)的描述: Typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree; lchilddatarchild lchilddatarchild lchilddatarchild 2021/3/2725 6.3、 二叉樹的遍歷二叉樹的遍歷 查找某個結(jié)點查找某個結(jié)點,或?qū)Χ鏄渲腥拷Y(jié)點進行某種處理或?qū)Χ鏄渲腥拷Y(jié)點進行某種處理,就需要遍就需要遍 歷。歷。 （1）遍歷定義及遍歷算法）遍歷定義及遍歷算法 遍歷遍歷是指是指按某條搜索路線尋

18、訪樹中每個結(jié)點，按某條搜索路線尋訪樹中每個結(jié)點，且每個結(jié)且每個結(jié) 點只被訪問一次。點只被訪問一次。 按按先左后右先左后右的原則，一般使用三種遍歷的原則，一般使用三種遍歷: 先序遍歷先序遍歷(D L R): 訪問根結(jié)點，按先序遍歷左子樹，按先序遍歷右子樹。訪問根結(jié)點，按先序遍歷左子樹，按先序遍歷右子樹。 中序遍歷中序遍歷(L D R): 按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹。按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹。 后序遍歷后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。 二叉樹為空時，執(zhí)行空操作，即空二

19、叉樹已遍歷完。二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。 2021/3/2726 （2）遍歷算法遍歷算法 先序遍歷先序遍歷:D L R 中序遍歷中序遍歷:L D R 后序遍歷：后序遍歷：L R D A D B C T1 T2 T3 D L R A D L R D L R B D C D L R 以先序遍歷以先序遍歷D L RD L R 為例演示遍歷過程為例演示遍歷過程 ABDC BDAC DBCA 2021/3/2727 Void PreOderTraverse(BiTree T) if(T! =NULL) printf (T-data); PreOrderTraverse(T-lchil

20、d); PreOrderTraverser(T-rchild); /*先序遍歷先序遍歷*/ 主程序主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A CB D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回左是空返回 pre(T R); T 左是空返回左是空返回 T 右是空返回右是空返回 T 左是空返回左是空返回 T 右是空返回右是空返回 pre(T R); 202

21、1/3/2728 中序遍歷二叉樹的遞歸算法中序遍歷二叉樹的遞歸算法: void inOrderTraverse(BiTree T) if(T!=NULL) inOrderTraverse(T- lchild); printf(T-data); inOrderTraverse(T- rchild); 后序遍歷二叉樹的遞歸算法后序遍歷二叉樹的遞歸算法: void PostOrderTraverse(BiTree T) if(T!=NULL) PostOrderTraverse(T- lchild); PostOrderTraverse(T- rchild); printf(T-data); 202

22、1/3/2729 層序遍歷二叉樹的算法層序遍歷二叉樹的算法: void LevelOrder(BiTree BT) if (!BT) exit; InitQueue(Q); p=BT; Visit(p); EnQueue( /*訪問根結(jié)點訪問根結(jié)點,并將根結(jié)點入隊并將根結(jié)點入隊 */ while (!QueueEmpty(Q) /*當(dāng)隊非空時重復(fù)執(zhí)行下列操作當(dāng)隊非空時重復(fù)執(zhí)行下列操作*/ DeQueue( /*出隊出隊*/ if (p-lchild) Visit(p-Lchild);EnQueue( if (p-rchild) Visit(p-Rchild);EnQueue( 2021/3/2

23、730 （3）遍歷二叉樹的應(yīng)用）遍歷二叉樹的應(yīng)用 1) 建立一棵二叉樹建立一棵二叉樹 (在遍歷過程生成結(jié)點在遍歷過程生成結(jié)點,建立二叉樹的存儲結(jié)構(gòu)建立二叉樹的存儲結(jié)構(gòu),用用 鏈式存儲結(jié)構(gòu)）鏈式存儲結(jié)構(gòu)） void CreatBiTree( BiTree T ) scanf( if(ch= = ) T=NULL; else T=(BiTNode )malloc(sizeof(BiTNode); T-data=ch; /*生成根結(jié)點生成根結(jié)點*/ CreatBiTree(T-lchild); /*構(gòu)造左子樹構(gòu)造左子樹*/ CreatBiTree (T-rchild); /*構(gòu)造右子樹構(gòu)造右子樹*/

24、 A D BC A B D C A B D C 按先序遍歷按先序遍歷 2021/3/2731 ch=A T T A creat(T L) T= , Creat(T) 返回 creat(T R) T ch= D | = 返回 creat(T R) D = T ch= 返回 ch=D T T D creat(T L) = | creat(T R) ch=C T T C creat(T L) + ch=B T T B creat(T L) T ch= B T C ch= + 返回 creat(T R) T C ch= + 返回 A T A B A B D |= A B D A B D C+ B A

25、A B D C A B D C 2021/3/2732 （2）統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)）統(tǒng)計二叉樹中葉子結(jié)點的個數(shù) 方法方法:對二叉樹進行遍歷對二叉樹進行遍歷,判斷被訪問的結(jié)點是否葉子結(jié)點判斷被訪問的結(jié)點是否葉子結(jié)點,若是葉子若是葉子 結(jié)點，則將計數(shù)器加結(jié)點，則將計數(shù)器加1。 實現(xiàn)算法實現(xiàn)算法: int countleaf(BiTree T) int n1,n2; if (T= =NULL) return 0; else if (T-lchild= =NULL) else n1=countleaf (T-lchild); n2=countleaf (T-rchild); return (n1

26、+n2); 2021/3/2733 void change(BiTree T) if (T!=NULL) T-LT-R; change(T-L); change(T-R); A BC D A CB D A CB D 練習(xí)練習(xí):試以二叉鏈表作為存儲結(jié)構(gòu)試以二叉鏈表作為存儲結(jié)構(gòu),將二叉樹中所有結(jié)點的將二叉樹中所有結(jié)點的 左右子樹進行交換。左右子樹進行交換。 2021/3/2734 2.5.3哈夫曼樹及其應(yīng)用哈夫曼樹及其應(yīng)用 1、哈夫曼樹、哈夫曼樹 樹的路徑長度的概念樹的路徑長度的概念: : 從一個結(jié)點到另一個結(jié)點之間的從一個結(jié)點到另一個結(jié)點之間的分支數(shù)目分支數(shù)目稱為稱為 這對結(jié)點之間的這對結(jié)點之間

27、的路徑長度路徑長度。 樹的路徑長度樹的路徑長度是從樹的根結(jié)點到每一結(jié)點的是從樹的根結(jié)點到每一結(jié)點的 路徑長度之和路徑長度之和。 2021/3/2735 1 1 2 2 45 3 3 67 PL=0+1+1+2+2+2+2=10 樹的路徑長度用樹的路徑長度用PLPL表示。表示。 2021/3/2736 1 1 2 2 45 3 3 67 PL=0+1+1+2+2+2+2=10 1 1 2 2 45 3 67 PL=0+1+1+2+2+3+3=12 樹的路徑長度用樹的路徑長度用PLPL表示。表示。 2021/3/2737 結(jié)點的帶權(quán)路徑長度結(jié)點的帶權(quán)路徑長度: 從該結(jié)點到樹根之間的從該結(jié)點到樹根之

28、間的路徑長度路徑長度與與結(jié)點上權(quán)結(jié)點上權(quán)的的乘積乘積。 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度: 樹中所有葉子結(jié)點的樹中所有葉子結(jié)點的帶權(quán)路徑長度之和帶權(quán)路徑長度之和。 abcd 7524 WPL=7*2+5*2+2*2+4*2=36 2021/3/2738 樹的帶權(quán)路徑長度記作樹的帶權(quán)路徑長度記作: 其中其中:Wk為樹中每個葉子結(jié)點的權(quán)為樹中每個葉子結(jié)點的權(quán); L k為每個葉子結(jié)點到根的路徑長度。 為每個葉子結(jié)點到根的路徑長度。 n k KKL WWPL 1 abcd 7524 WPL=7*2+5*2+2*2+4*2=36 WPL最小的二叉樹就稱作最小的二叉樹就稱作最優(yōu)二叉樹最優(yōu)二叉樹或或哈夫曼樹

29、哈夫曼樹 。 2021/3/2739 abcd 7524 WPL=7*2+5*2+2*2+4*2=36 d c ab 2 4 75 WPL=7*3+5*3+2*1+4*2=4 6 a b cd 7 5 24 WPL=7*1+5*2+2*3+4*3=3 5 哈夫曼樹哈夫曼樹 （最優(yōu)樹）（最優(yōu)樹） 加權(quán)路徑長度最小的二叉樹就加權(quán)路徑長度最小的二叉樹就 是哈夫曼樹。是哈夫曼樹。 公式公式: n k K L K WWPL 1 2021/3/2740 6 75 cd (b) 11 b 5 7 cd (c) 18 a 7 11 cd b 5 6 24 (d) abcd 7524 (a) 2、哈夫曼樹的構(gòu)造

30、、哈夫曼樹的構(gòu)造Huffman算法算法 例例:給定權(quán)值給定權(quán)值7,5,2，4，構(gòu)造哈夫曼樹。，構(gòu)造哈夫曼樹。 方法方法: (1) 由原始數(shù)據(jù)生成森林由原始數(shù)據(jù)生成森林; (2) 在森林中選取兩棵根結(jié)點權(quán)值在森林中選取兩棵根結(jié)點權(quán)值最小最小的和的和次小次小的二的二 叉樹作為左右子樹構(gòu)造一棵新的二叉樹叉樹作為左右子樹構(gòu)造一棵新的二叉樹,其根結(jié)點的權(quán)其根結(jié)點的權(quán) 值為左右子樹根結(jié)點權(quán)值之和。值為左右子樹根結(jié)點權(quán)值之和。規(guī)定左子樹根結(jié)點的規(guī)定左子樹根結(jié)點的 權(quán)值小于右子樹根結(jié)點的權(quán)值。權(quán)值小于右子樹根結(jié)點的權(quán)值。 (3) 將新的二叉樹加入到森林將新的二叉樹加入到森林F中中,刪除原來兩棵權(quán)值刪除原來兩棵

31、權(quán)值 最小的樹最小的樹; (4)重復(fù)重復(fù)2、3步驟，直至步驟，直至F中只剩一棵樹為止。中只剩一棵樹為止。 2021/3/2741 練習(xí)練習(xí):給定權(quán)值給定權(quán)值5,15,40，30，10，構(gòu)造哈夫曼樹。，構(gòu)造哈夫曼樹。 2021/3/2742 練習(xí)練習(xí):給定權(quán)值給定權(quán)值5,15,40，30，10，構(gòu)造哈夫曼樹。，構(gòu)造哈夫曼樹。 cabde 51 5 403 0 10 2021/3/2743 練習(xí)練習(xí):給定權(quán)值給定權(quán)值5,15,40，30，10，構(gòu)造哈夫曼樹。，構(gòu)造哈夫曼樹。 15 bc ae d 154030 510 2021/3/2744 練習(xí)練習(xí):給定權(quán)值給定權(quán)值5,15,40，30，10，構(gòu)

32、造哈夫曼樹。，構(gòu)造哈夫曼樹。 15b c ae d 15 4030 510 30 2021/3/2745 練習(xí)練習(xí):給定權(quán)值給定權(quán)值5,15,40，30，10，構(gòu)造哈夫曼樹。，構(gòu)造哈夫曼樹。 15b c ae d 15 40 30 510 30 60 2021/3/2746 練習(xí)練習(xí):給定權(quán)值給定權(quán)值5,15,40，30，10，構(gòu)造哈夫曼樹。，構(gòu)造哈夫曼樹。 15b c ae d 15 40 30 510 30 60 100 WPL=40*1+30*2+15*3+5*4+10*4=20 5 2021/3/2747 3、哈夫曼樹的應(yīng)用、哈夫曼樹的應(yīng)用 （1）判定樹）判定樹 在解決某些判定問題時在

33、解決某些判定問題時,利用哈夫曼樹可以得到最利用哈夫曼樹可以得到最 佳判定算法。佳判定算法。 例例1 將學(xué)生百分成績按分數(shù)段分級的程序。將學(xué)生百分成績按分數(shù)段分級的程序。 若學(xué)生成績分布是均勻的若學(xué)生成績分布是均勻的,可用圖（可用圖（a)二叉樹結(jié)構(gòu)二叉樹結(jié)構(gòu) 來實現(xiàn)。來實現(xiàn)。 a60 a70 a80 a90 不及格不及格 中等中等 良好良好優(yōu)秀優(yōu)秀 及格及格 YN YN Y N YN (a) 2021/3/2748 分數(shù)分數(shù)0596069707980899099 比例比例0.050.150.40.30.1 70a 80 a60 及格及格 中等中等 良好良好 80a90 60a70 不及格不及格優(yōu)秀優(yōu)秀 Y N Y Y Y N N N (b) 不及格不及格 Y a90 a80 a70 a60 優(yōu)秀優(yōu)秀 中等中等 及格及格 良好良好 Y N N N (c) Y Y Y 學(xué)生成績分布不是均勻的情況學(xué)生成績分布不是均勻的情況: 以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼 樹樹,如（如（b)判斷樹所示。判斷樹所示。 再將每一比較框的兩次比較再將每一比較框的兩次比較 改為一次改為一次,