第06章_二叉樹遍歷

1、第六章第六章 樹、二叉樹樹、二叉樹 n 6.1 樹的定義和基本術(shù)語 n 6.2 二叉樹 n 6.3 遍歷二叉樹 n 6.4 樹和森林 n 6.6 赫夫曼樹及其應(yīng)用 6.1 樹的定義和基本術(shù)語樹的定義和基本術(shù)語 樹樹(Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T，非空樹 滿足以下條件: (1)有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn); (2) 除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相 交的有限集T1,T2.Tm,其中,每一個(gè)集合本身 又是一棵樹, 并且稱為根的子樹 n樹的定義 (b)(b)是只有一個(gè)根結(jié)點(diǎn)的樹是只有一個(gè)根結(jié)點(diǎn)的樹; ; (a)(a)是有是有1313個(gè)結(jié)點(diǎn)的樹個(gè)結(jié)點(diǎn)的樹, ,其中其中A A是根

2、是根, ,其余結(jié)點(diǎn)分成三個(gè)互不其余結(jié)點(diǎn)分成三個(gè)互不 相交的子樹；相交的子樹； ：包含一個(gè)數(shù)據(jù)元素及若干個(gè)指向其子樹的分支包含一個(gè)數(shù)據(jù)元素及若干個(gè)指向其子樹的分支 ：結(jié)點(diǎn)擁有的子樹數(shù)結(jié)點(diǎn)擁有的子樹數(shù) ：樹內(nèi)各結(jié)點(diǎn)的度的最大值樹內(nèi)各結(jié)點(diǎn)的度的最大值 （終端結(jié)點(diǎn)）：度為零的結(jié)點(diǎn)度為零的結(jié)點(diǎn) 非終端結(jié)點(diǎn)（）：度不為零的結(jié)點(diǎn)度不為零的結(jié)點(diǎn) ： ： ： 是是m m棵互不相交的樹的棵互不相交的樹的 集合集合 6.2 二叉樹二叉樹 n二叉樹的定義 度不大于度不大于2的樹稱為二叉樹。的樹稱為二叉樹。 n相關(guān)術(shù)語 左子結(jié)點(diǎn)、右子結(jié)點(diǎn)左子結(jié)點(diǎn)、右子結(jié)點(diǎn) (a) 空二叉樹空二叉樹 A (b) 根和空的根和空的 左右子

3、樹左右子樹 A B (c) 根和左根和左 子樹子樹 A B (d) 根和右根和右 子樹子樹 A C B (e) 根和左根和左 右子樹右子樹 n二叉樹的性質(zhì) n二叉樹的性質(zhì) (1)(1)當(dāng)當(dāng)i=1i=1時(shí)，該結(jié)點(diǎn)為根，它無雙親結(jié)點(diǎn)；時(shí)，該結(jié)點(diǎn)為根，它無雙親結(jié)點(diǎn)； (2)(2)當(dāng)當(dāng)i1i1時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為時(shí)，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為 i/2i/2 ； (3)(3)當(dāng)當(dāng)2in2in，則有編號為，則有編號為2i2i的左孩子，否則沒有左孩子；的左孩子，否則沒有左孩子； (4)(4)若若2i+1n2i+1n，則有編號為，則有編號為2i+12i+1的右孩子，否則沒有右孩子。的右孩子，否則沒有右孩子。

4、 順序存儲(chǔ)結(jié)構(gòu) 連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)完全二 叉樹上的結(jié)點(diǎn)元素。 a bc def g hijkl ABCDEFGHIJKL a b c de fg ABCDE0000FG 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) a bc ef ghi d a b c d ef i h g 二叉鏈表 三叉鏈表 a b c def g 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn); ; 除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)可分為除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)可分為m m個(gè)互不相交的有限集。個(gè)互不相交的有限集。 每個(gè)結(jié)點(diǎn)至多只有兩棵子樹每個(gè)結(jié)點(diǎn)至多只有兩棵子樹 遍歷二叉樹，遍歷二叉樹， 即如何按某條搜索路徑巡訪樹即如何按某條搜索路

5、徑巡訪樹 中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且 僅被訪問一次。僅被訪問一次。 操作排列次序：操作排列次序： 根、左、右根、左、右 左、根、右左、根、右 左、右、根左、右、根 根、右、左根、右、左 右、根、左右、根、左 右、左、根右、左、根 根、左、右根、左、右 左、根、右左、根、右 左、右、根左、右、根 先序先序(Preorder)遍歷遍歷 a bc ef h a bc e h f 若遍歷的二叉樹為空，執(zhí)行空操作；否則若遍歷的二叉樹為空，執(zhí)行空操作；否則 (1)訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； (2)先序遍歷左子樹；先序遍歷左子樹； (3)先序遍歷右子樹

6、。先序遍歷右子樹。 若遍歷的二叉樹為空，執(zhí)行空操作；否則若遍歷的二叉樹為空，執(zhí)行空操作；否則 (1)中序遍歷左子樹；中序遍歷左子樹； (2)訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； (3)中序遍歷右子樹。中序遍歷右子樹。 a bc ef h 中序中序(Inorder)遍歷遍歷 b a e h c f a bc ef h 若遍歷的二叉樹為空，執(zhí)行空操作；否則若遍歷的二叉樹為空，執(zhí)行空操作；否則 (1)后序遍歷左子樹；后序遍歷左子樹； (2)后序遍歷右子樹；后序遍歷右子樹； (3)訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。 后序后序(Postorder)遍歷遍歷 b h ef c a 后序遍歷算法后序遍歷算法 n例例:請分別寫出二

7、叉樹的先序、中序和后序序列請分別寫出二叉樹的先序、中序和后序序列 a e e a bf edh g i bedgfhi bgbfiha gdbihfa 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 n二叉樹的遍歷 遍歷序與二叉樹的對應(yīng) n前序遍歷序前序遍歷序+中序遍歷序唯一確定二叉樹中序遍歷序唯一確定二叉樹 n后序遍歷序后序遍歷序+中序遍歷序唯一確定二叉樹中序遍歷序唯一確定二叉樹 a bc ef ghi d 前序遍歷序：前序遍歷序：abdceghfi 中序遍歷序：中序遍歷序：dbagehcfi n線索二叉樹 定義 lchildLTagdataRTagrchild 其中：其中： Ltag

8、= 0 lchild域指示結(jié)點(diǎn)的左孩子域指示結(jié)點(diǎn)的左孩子 1 lchild域指示結(jié)點(diǎn)的前驅(qū)域指示結(jié)點(diǎn)的前驅(qū) Rtag= 0 rchild域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子 1 rchild域指示結(jié)點(diǎn)的后繼域指示結(jié)點(diǎn)的后繼 以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu), ,叫做叫做線索鏈線索鏈 表表, ,其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做線索線索. .加上線索的二叉樹稱加上線索的二叉樹稱 之為之為線索二叉樹線索二叉樹. .對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過 程叫做程叫

9、做線索化線索化. . a b c d ef i h g a bc def ihg 中序線索化二叉樹 n線索二叉樹 中序線索二叉樹的遍歷 a bc def ihg 若結(jié)點(diǎn)右標(biāo)志為若結(jié)點(diǎn)右標(biāo)志為1,1,則右鏈為線則右鏈為線 索索, ,指示其后繼指示其后繼; ;否則遍歷右子否則遍歷右子 樹時(shí)訪問的第一個(gè)結(jié)點(diǎn)為其后樹時(shí)訪問的第一個(gè)結(jié)點(diǎn)為其后 繼繼, ,即右子樹中最左下的結(jié)點(diǎn)。即右子樹中最左下的結(jié)點(diǎn)。 若結(jié)點(diǎn)左標(biāo)志為若結(jié)點(diǎn)左標(biāo)志為1,1,則左鏈為線則左鏈為線 索索, ,指示其前驅(qū)指示其前驅(qū); ;否則遍歷左子否則遍歷左子 樹時(shí)最后訪問的一個(gè)結(jié)點(diǎn)為其樹時(shí)最后訪問的一個(gè)結(jié)點(diǎn)為其 前驅(qū)。前驅(qū)。 A B CD E

10、G F+ H * - * / + - A+(B*(C-D)/E-F*(G+H) n樹的存儲(chǔ)結(jié)構(gòu) 雙親表示法 0 1 2 3 4 5 6 7 8 9 R -1 A0 0 0 B C D1 1E F3 G6 6 6 H K R AC DEF G B H K 假設(shè)以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn), 同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示 其雙親結(jié)點(diǎn)在鏈表中的位置。 R AC DEF G B H K 0 1 2 3 4 5 6 7 8 9 R A B C D E F G H K 45 6 123 789 a b c d e f j k l i a a b b e e d dc c i if fj jk kl l

11、 鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分 別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié) 點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。 n森林與二叉樹的轉(zhuǎn)換 樹=根+子樹森林 a a b b e e d dc c i if fj jk kl lm m q qn no op p n森林與二叉樹的轉(zhuǎn)換 二叉樹與樹的轉(zhuǎn)換 a a b b e e d dc c i if fj jk kl lm m q qn no op p Tree=(root, T1, , Tn) a a b b e e d d c c i i f fj j k k l l m m q q n n o o p p BiTree=(root, Tl, Tr) b b e e d dc c i

12、if fj jk kl lm m q qn no op p Forest=(T1, , Tn)=(root,T11,T1m),Tn) b b e e d d c c i i f fj j k k l l m m q q n n o o p p BiTree=(root, Tl, Tr) n森林與二叉樹的轉(zhuǎn)換 R AC DEF G B H K 先根序列：先根序列：R A D E B C F G H KR A D E B C F G H K 后根序列：后根序列：D E A B G H K F C RD E A B G H K F C R A BD G J E HCFI 先序序列：先序序列：A B

13、C D E F G H I JA B C D E F G H I J A BD G J E HCFI 中序序列：中序序列：B C D A F E H J I GB C D A F E H J I G n赫夫曼樹（最優(yōu)二叉樹） -路徑路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這 兩個(gè)結(jié)點(diǎn)之間的路徑。兩個(gè)結(jié)點(diǎn)之間的路徑。 -路徑長度路徑長度：路徑上的分支數(shù)稱為這兩點(diǎn)之間的路徑長度。：路徑上的分支數(shù)稱為這兩點(diǎn)之間的路徑長度。 -樹的路徑長度樹的路徑長度：樹的路徑長度是從樹的根到每一結(jié)點(diǎn)的：樹的路徑長度是從樹的根到每一結(jié)點(diǎn)的 路徑長度之和路徑長度之和。

14、-結(jié)點(diǎn)的帶權(quán)路徑長度結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)到樹根之間的路徑長度：從該結(jié)點(diǎn)到樹根之間的路徑長度 與結(jié)點(diǎn)上權(quán)的乘積。與結(jié)點(diǎn)上權(quán)的乘積。 -樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)帶權(quán)路徑長度之：樹中所有葉子結(jié)點(diǎn)帶權(quán)路徑長度之 和，通常記作和，通常記作 1 n kk k W P Lw l n赫夫曼樹（最優(yōu)二叉樹） (a)WPL=7*2+5*2+2*2+2*4=36 (b)WPL=4*2+7*3+5*3+2*1=46 (c)WPL=7*1+5*2+2*3+4*3=35 n赫夫曼算法 (1)(1)根據(jù)給定的根據(jù)給定的n n個(gè)權(quán)值個(gè)權(quán)值 W W1 1，W W2 2，W W n n 構(gòu)成 構(gòu)

15、成n n棵二叉樹棵二叉樹 的集合的集合F=TF=T1 1，T T2 2，T T n n ，其中每一棵二叉樹，其中每一棵二叉樹T T i i中只 中只 有一個(gè)帶權(quán)為有一個(gè)帶權(quán)為W Wi i的根結(jié)點(diǎn)，其左右子樹均空；的根結(jié)點(diǎn)，其左右子樹均空； (2)(2)在在F F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為一棵新的二叉中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為一棵新的二叉 樹的左右子樹，且置新二叉樹根結(jié)點(diǎn)的權(quán)值為兩棵子樹根樹的左右子樹，且置新二叉樹根結(jié)點(diǎn)的權(quán)值為兩棵子樹根 結(jié)點(diǎn)的權(quán)值之和；結(jié)點(diǎn)的權(quán)值之和； (3)(3)從從F F中刪去這兩棵樹，同時(shí)把新二叉樹加入中刪去這兩棵樹，同時(shí)把新二叉樹加入F F中；中； (4)

16、(4)重復(fù)重復(fù)(2)(2)和（和（3 3），直到），直到F F中只有一棵樹為止，此樹便是中只有一棵樹為止，此樹便是 哈夫曼樹。哈夫曼樹。 a 3 b 7 c 8 d 6 e 21 9 a 3 b 7 c 8 d 6 e 21 9 a 3 b 7 c 8 d 6 e 21 15 9 a 3 b 7 c 8 d 6 e 21 15 24 9 a 3 b 7 c 8 d 6 e 21 15 24 45 n赫夫曼編碼 定長編碼與變長編碼 若要設(shè)計(jì)長短不等的編碼，則必須是任一個(gè)字符的 編碼都不是另一個(gè)字符的編碼的前綴，這種編碼稱 為前綴編碼。 可以利用二叉樹來設(shè)計(jì)二進(jìn)制的前綴編碼。 A B CD 0 0 0 1 1 1 編碼：編碼：A(0) B(10) C(110) D(111) a:100 b:110 c:111 d:101 e:0 9 a 3 b 7 c 8 d 6 e 21 01 15 01 24 01 45 10 n赫夫曼編碼