第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)個結(jié)點的有限集T，非空樹滿足以下條件:(1)有且僅有一個特定的稱為根的結(jié)點;(2) 除根結(jié)點外的其余結(jié)點可分為m(m0)個互不相交的有限集T1,T2.Tm,其中,每一個集合本身 又是一棵樹, 并且稱為根的子樹n樹的定義 (b)(b)是只有一個根結(jié)點的樹是只有一個根結(jié)點的樹; ;(a)(a)是有是有1313個結(jié)點的樹個結(jié)點的樹, ,其中其中A A是根是根, ,其余結(jié)點分成

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

3、和右子樹子樹ACB (e)根和左根和左右子樹右子樹n二叉樹的性質(zhì)n二叉樹的性質(zhì)(1)(1)當(dāng)當(dāng)i=1i=1時，該結(jié)點為根，它無雙親結(jié)點；時，該結(jié)點為根，它無雙親結(jié)點；(2)(2)當(dāng)當(dāng)i1i1時，該結(jié)點的雙親結(jié)點編號為時，該結(jié)點的雙親結(jié)點編號為 i/2i/2 ；(3)(3)當(dāng)當(dāng)2in2in，則有編號為，則有編號為2i2i的左孩子，否則沒有左孩子；的左孩子，否則沒有左孩子；(4)(4)若若2i+1n2i+1n，則有編號為，則有編號為2i+12i+1的右孩子，否則沒有右孩子。的右孩子，否則沒有右孩子。順序存儲結(jié)構(gòu) 連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素。abcdefghijk

4、lABCDEFGHIJKLabcdefgABCDE0000FG鏈?zhǔn)酱鎯Y(jié)構(gòu)abcefghidabcd efi h g 二叉鏈表三叉鏈表abcdefg有且僅有一個特定的稱為根的結(jié)點有且僅有一個特定的稱為根的結(jié)點; ;除根結(jié)點外的其余結(jié)點可分為除根結(jié)點外的其余結(jié)點可分為m m個互不相交的有限集。個互不相交的有限集。每個結(jié)點至多只有兩棵子樹每個結(jié)點至多只有兩棵子樹遍歷二叉樹，遍歷二叉樹， 即如何按某條搜索路徑巡訪樹即如何按某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。僅被訪問一次。操作排列次序：操作排列次序： 根、左、右根、左、右

5、 左、根、右左、根、右 左、右、根左、右、根 根、右、左根、右、左 右、根、左右、根、左 右、左、根右、左、根 根、左、右根、左、右 左、根、右左、根、右 左、右、根左、右、根先序先序(Preorder)遍歷遍歷abcefhabcehf若遍歷的二叉樹為空，執(zhí)行空操作；否則若遍歷的二叉樹為空，執(zhí)行空操作；否則(1)訪問根結(jié)點；訪問根結(jié)點；(2)先序遍歷左子樹；先序遍歷左子樹；(3)先序遍歷右子樹。先序遍歷右子樹。若遍歷的二叉樹為空，執(zhí)行空操作；否則若遍歷的二叉樹為空，執(zhí)行空操作；否則(1)中序遍歷左子樹；中序遍歷左子樹；(2)訪問根結(jié)點；訪問根結(jié)點；(3)中序遍歷右子樹。中序遍歷右子樹。abce

6、fh中序中序(Inorder)遍歷遍歷baehcfabcefh若遍歷的二叉樹為空，執(zhí)行空操作；否則若遍歷的二叉樹為空，執(zhí)行空操作；否則(1)后序遍歷左子樹；后序遍歷左子樹；(2)后序遍歷右子樹；后序遍歷右子樹；(3)訪問根結(jié)點。訪問根結(jié)點。后序后序(Postorder)遍歷遍歷bhefca后序遍歷算法后序遍歷算法n例例:請分別寫出二叉樹的先序、中序和后序序列請分別寫出二叉樹的先序、中序和后序序列aeeabfedhgibedgfhibgbfihagdbihfa6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹n二叉樹的遍歷 遍歷序與二叉樹的對應(yīng)n前序遍歷序前序遍歷序+中序遍歷序唯一確定二叉樹中

7、序遍歷序唯一確定二叉樹n后序遍歷序后序遍歷序+中序遍歷序唯一確定二叉樹中序遍歷序唯一確定二叉樹abcefghid前序遍歷序：前序遍歷序：abdceghfi中序遍歷序：中序遍歷序：dbagehcfin線索二叉樹 定義lchildLTagdataRTagrchild其中：其中：Ltag=0 lchild域指示結(jié)點的左孩子域指示結(jié)點的左孩子1 lchild域指示結(jié)點的前驅(qū)域指示結(jié)點的前驅(qū)Rtag=0 rchild域指示結(jié)點的右孩子域指示結(jié)點的右孩子1 rchild域指示結(jié)點的后繼域指示結(jié)點的后繼 以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu), ,叫做叫做線

8、索鏈線索鏈表表, ,其中指向結(jié)點前驅(qū)與后繼的指針叫做其中指向結(jié)點前驅(qū)與后繼的指針叫做線索線索. .加上線索的二叉樹稱加上線索的二叉樹稱之為之為線索二叉樹線索二叉樹. .對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做程叫做線索化線索化. .abcd efi h g abcdefihg中序線索化二叉樹n線索二叉樹 中序線索二叉樹的遍歷abcdefihg若結(jié)點右標(biāo)志為若結(jié)點右標(biāo)志為1,1,則右鏈為線則右鏈為線索索, ,指示其后繼指示其后繼; ;否則遍歷右子否則遍歷右子樹時訪問的第一個結(jié)點為其后樹時訪問的第一個結(jié)點為其后繼繼, ,即右子樹中最左下的結(jié)點。

9、即右子樹中最左下的結(jié)點。若結(jié)點左標(biāo)志為若結(jié)點左標(biāo)志為1,1,則左鏈為線則左鏈為線索索, ,指示其前驅(qū)指示其前驅(qū); ;否則遍歷左子否則遍歷左子樹時最后訪問的一個結(jié)點為其樹時最后訪問的一個結(jié)點為其前驅(qū)。前驅(qū)。ABCDEGF+H*-*/+-A+(B*(C-D)/E-F*(G+H)n樹的存儲結(jié)構(gòu) 雙親表示法0123456789R-1A000BCD11EF3G666HKRACDEFGBH K 假設(shè)以一組連續(xù)空間存儲樹的結(jié)點,同時在每個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在鏈表中的位置。RACDEFGBH K0123456789RABCDEFGHK456123789abcdef jkl i a ab be

10、ed dc ci if fj jk kl l 鏈表中結(jié)點的兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點。n森林與二叉樹的轉(zhuǎn)換 樹=根+子樹森林a ab be ed dc ci if fj jk kl lm mq qn no op pn森林與二叉樹的轉(zhuǎn)換 二叉樹與樹的轉(zhuǎn)換a ab be ed dc ci if fj jk kl lm mq qn no op pTree=(root, T1, , Tn)a ab be ed dc ci if fj jk kl lm mq qn no op pBiTree=(root, Tl, Tr)b be ed dc ci if fj jk kl lm

11、 mq qn no op pForest=(T1, , Tn)=(root,T11,T1m),Tn)b be ed dc ci if fj jk kl lm mq qn no op pBiTree=(root, Tl, Tr)n森林與二叉樹的轉(zhuǎn)換RACDEFGBH 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 RABDGJEHCFI先序序列：先序序列：A B C D E F G H I JA B C D E F G H I JABDGJEHCFI中序

12、序列：中序序列：B C D A F E H J I GB C D A F E H J I Gn赫夫曼樹（最優(yōu)二叉樹）-路徑路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑。兩個結(jié)點之間的路徑。-路徑長度路徑長度：路徑上的分支數(shù)稱為這兩點之間的路徑長度。：路徑上的分支數(shù)稱為這兩點之間的路徑長度。-樹的路徑長度樹的路徑長度：樹的路徑長度是從樹的根到每一結(jié)點的：樹的路徑長度是從樹的根到每一結(jié)點的路徑長度之和路徑長度之和。-結(jié)點的帶權(quán)路徑長度結(jié)點的帶權(quán)路徑長度：從該結(jié)點到樹根之間的路徑長度：從該結(jié)點到樹根之間的路徑長度與結(jié)點上權(quán)的乘積。與結(jié)

13、點上權(quán)的乘積。-樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點帶權(quán)路徑長度之：樹中所有葉子結(jié)點帶權(quán)路徑長度之和，通常記作和，通常記作1nkkkW P Lw ln赫夫曼樹（最優(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=35n赫夫曼算法(1)(1)根據(jù)給定的根據(jù)給定的n n個權(quán)值個權(quán)值 W W1 1，W W2 2，W W n n 構(gòu)成構(gòu)成n n棵二叉樹棵二叉樹的集合的集合F=TF=T1 1，T T2 2，T T n n ，其中每一棵二叉樹，其中每一棵二叉樹T T i i中只中只有一個

14、帶權(quán)為有一個帶權(quán)為W Wi i的根結(jié)點，其左右子樹均空；的根結(jié)點，其左右子樹均空；(2)(2)在在F F中選出兩棵根結(jié)點權(quán)值最小的樹作為一棵新的二叉中選出兩棵根結(jié)點權(quán)值最小的樹作為一棵新的二叉樹的左右子樹，且置新二叉樹根結(jié)點的權(quán)值為兩棵子樹根樹的左右子樹，且置新二叉樹根結(jié)點的權(quán)值為兩棵子樹根結(jié)點的權(quán)值之和；結(jié)點的權(quán)值之和；(3)(3)從從F F中刪去這兩棵樹，同時把新二叉樹加入中刪去這兩棵樹，同時把新二叉樹加入F F中；中；(4)(4)重復(fù)重復(fù)(2)(2)和（和（3 3），直到），直到F F中只有一棵樹為止，此樹便是中只有一棵樹為止，此樹便是哈夫曼樹。哈夫曼樹。a3b7c8d6e219a3b7c8d6e219a3b7c8d6e21159a3b7c8d6e2115249a3b7c8d6e21152445n赫夫曼編碼 定長編碼與變長編碼 若要設(shè)計長短不等的編碼，則必須是任一個字符的編碼都不是另一個字符的編碼的前綴，這種編碼稱為前綴編碼。 可以利用二叉樹來設(shè)計二進(jìn)制的前綴編碼。ABCD000111編碼：編碼：A(0) B(10) C(110) D(111)a:100b:110c:111d:101e:09a3b7c8d6e2101150124014510n赫夫曼編碼