《數(shù)據(jù)結(jié)構(gòu)》樹

1、計科系計科系 王丹丹王丹丹第6章 樹主要內(nèi)容主要內(nèi)容樹的定義和存儲結(jié)構(gòu)二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)二叉樹的遍歷、建立和線索化樹、森林與二叉樹的轉(zhuǎn)換赫夫曼樹及其應(yīng)用重點和難點重點和難點二叉樹的數(shù)組、結(jié)構(gòu)數(shù)組及鏈表的表示法二叉樹的建立算法二叉樹的遍歷算法（前序、中序、后序）二叉樹的查找算法二叉樹的結(jié)點刪除算法6.1 開場白開場白AVATAR6.2 樹的定義樹的定義樹的表示法ABCDEFHIJG根結(jié)點根結(jié)點6.2.1 結(jié)點分類結(jié)點分類樹的結(jié)點樹的結(jié)點結(jié)點的度結(jié)點的度葉結(jié)點葉結(jié)點分支結(jié)點分支結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點擁有的子樹數(shù)。（Degree）度為0的結(jié)點。（終端結(jié)點）度不為0

2、的結(jié)點。（非終端結(jié)點/內(nèi)部結(jié)點）樹的度樹的度樹內(nèi)各結(jié)點的度的最大值。例：思考結(jié)點A、B、C、D、E、J是什么類型，度是多少？ABCDEFHIJG6.2.2 結(jié)點間關(guān)系結(jié)點間關(guān)系孩子結(jié)點（孩子結(jié)點（Child）結(jié)點的子樹的根稱為該結(jié)點的孩子。雙親結(jié)點（雙親結(jié)點（Parent）孩子結(jié)點的上層結(jié)點叫該結(jié)點的雙親結(jié)點。祖先祖先結(jié)點（結(jié)點（ancestor）從根到該結(jié)點的所經(jīng)路徑上的所有結(jié)點均稱為祖先結(jié)點。兄弟兄弟結(jié)點（結(jié)點（Sibling）同一雙親的孩子互稱為兄弟結(jié)點。堂堂兄弟結(jié)點兄弟結(jié)點（Cousin）雙親在同一層上的結(jié)點互稱為堂兄結(jié)點。子孫子孫結(jié)點結(jié)點以某結(jié)點為根的子樹中任一結(jié)點都稱為該結(jié)點的子孫

3、結(jié)點。思考：結(jié)點E的孩子、雙親、兄弟、堂兄弟、祖先、子孫結(jié)點分別是哪些？ABCDEFHIJG6.2.3 樹的其他相關(guān)概念樹的其他相關(guān)概念結(jié)點的層次(Level)從根開始定義起。樹的深度(Depth)/高度：樹中結(jié)點的最大層次。ABCDEFHIJG第一層第二層第三層第四層深度為4有序樹和無序樹 如果將樹中結(jié)點的各子樹看成從左至右是有秩序的，不能互換的，則稱該樹為有序樹，否則稱為無序樹。森林(Forst) m(m0)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。對比線性表與樹的結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)第一個數(shù)據(jù)元素：無前驅(qū)第一個數(shù)據(jù)元素：無前驅(qū)最后一個數(shù)據(jù)元素：無后繼最后一個數(shù)據(jù)元素

4、：無后繼中間元素：一個前驅(qū)一個后繼中間元素：一個前驅(qū)一個后繼樹結(jié)構(gòu)樹結(jié)構(gòu)根結(jié)點：無雙親，唯一根結(jié)點：無雙親，唯一葉結(jié)點：無孩子，可以多個葉結(jié)點：無孩子，可以多個中間結(jié)點：一個雙親多個孩子中間結(jié)點：一個雙親多個孩子6.3 樹的抽象數(shù)據(jù)類型樹的抽象數(shù)據(jù)類型ADT 樹樹(Tree)Data樹是由一個根結(jié)點和若干棵子樹構(gòu)成。樹中結(jié)點樹是由一個根結(jié)點和若干棵子樹構(gòu)成。樹中結(jié)點具有相同數(shù)據(jù)類型及層次關(guān)系。具有相同數(shù)據(jù)類型及層次關(guān)系。OperationInitTree(*T)：構(gòu)造空樹。：構(gòu)造空樹。Destroy(*T)：銷毀樹：銷毀樹T。CreateTree(*T,definition)：按：按defin

5、ition中給出樹中給出樹的定義來構(gòu)造樹。的定義來構(gòu)造樹。ClearTree(*T)：若樹：若樹T存在，則將樹存在，則將樹T清為空樹。清為空樹。TreeEmpty(*T)：若：若T為空樹，返回為空樹，返回true，否則返，否則返回回false。接上頁接上頁TreeDepth(*T)：返回：返回T的深度。的深度。Root(T)：返回：返回T的根結(jié)點。的根結(jié)點。Value(T,cur_e)：cur_e是樹是樹T中一個結(jié)點，返回此中一個結(jié)點，返回此結(jié)點的值。結(jié)點的值。Assign(T,cur_e,value)：給樹：給樹T的結(jié)點的結(jié)點cur_e賦值為賦值為value。Parent(T,cur_e)：

6、若：若cur_e是樹是樹T的非根結(jié)點，則的非根結(jié)點，則返回它的雙親，否則返回空。返回它的雙親，否則返回空。LeftChild(T,cur_e)：若：若cur_e是樹是樹T的非葉結(jié)點，的非葉結(jié)點，則返回它的雙親，否則返回空。則返回它的雙親，否則返回空。接上頁接上頁RightSibling(T,cur_e)：若：若cur_e有有兄弟，則返有有兄弟，則返回它的右兄弟，否則返回空回它的右兄弟，否則返回空。InisertChild(*T,*p,i,c)：其中：其中p指向樹指向樹T的某個結(jié)的某個結(jié)點，點，i為所指結(jié)點為所指結(jié)點p的的度度上加上加1，非空樹，非空樹c與與T不相交，操不相交，操作結(jié)果為插入作結(jié)

7、果為插入c為樹為樹T中中p指結(jié)點的第指結(jié)點的第i棵子樹?？米訕洹?DeleteChild(*T,*p,i)：其中其中p指向樹指向樹T的某個結(jié)點，的某個結(jié)點，i為所指結(jié)點為所指結(jié)點p的度，操作的度，操作結(jié)果結(jié)果為刪除為刪除T中中p指結(jié)點的第指結(jié)點的第i棵子樹棵子樹。endADT6.4 樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯樞蝽樞虼鎯Υ鎯?結(jié) 點 的 存儲位置無法直接反映邏輯關(guān)系。 充分利用二者的特點完全可以實現(xiàn)對樹的存儲結(jié)構(gòu)的表示！6.4.1 雙親表示法雙親表示法假設(shè)以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中，附設(shè)一個指示器指示其雙親結(jié)點在數(shù)組中的位置。其結(jié)點結(jié)構(gòu)為： data是數(shù)據(jù)域，存

8、儲結(jié)點的數(shù)據(jù)信息； parent是指針域，存儲該結(jié)點的雙親在數(shù)組中的下標(biāo)。 約定根結(jié)點的位置域為-1，則所有的結(jié)點都存有它雙親的位置。dataparent雙親表示法的結(jié)點結(jié)構(gòu)定義代碼/*樹的雙親表示法結(jié)點結(jié)構(gòu)定義樹的雙親表示法結(jié)點結(jié)構(gòu)定義*/#define MAX_TREE_SIZE 100typedef int TElemType;/樹結(jié)點的數(shù)據(jù)類型樹結(jié)點的數(shù)據(jù)類型typedef struct PTNode/結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)TElemType data;/結(jié)點數(shù)據(jù)結(jié)點數(shù)據(jù)int parent;/雙親位置雙親位置PTNode;typedef struct/樹結(jié)構(gòu)樹結(jié)構(gòu)PTNode nodesM

9、AX_TREE_SIZE;/結(jié)點數(shù)組結(jié)點數(shù)組int r, n;/根的位置和結(jié)點樹根的位置和結(jié)點樹PTree;樹結(jié)構(gòu)和樹雙親表示ABCDEFHIJG下標(biāo)下標(biāo) dataparent0A-11B02C03D14E25F26G37H38I39J4 根據(jù)結(jié)點的parent指針很容易找到它的雙親結(jié)點，所用時間復(fù)雜度為O(1)。 結(jié)點的孩子呢？遍歷整個結(jié)構(gòu)！改進(jìn)：增加長子域，如果沒有長子域就設(shè)置為-1。ABCDEFHIJG下標(biāo)下標(biāo) data parent firstchild0A-111B032C043D164E295F2-16G3-17H3-18I3-19J4-1 對于有0或1個孩子的結(jié)點，解決了要找結(jié)點

10、孩子的問題。 關(guān)注各兄弟之間的關(guān)系？方法：增加一個右兄弟域來體現(xiàn)兄弟關(guān)系。 每一個結(jié)點如果它存在右兄弟，則記錄下右兄弟的下標(biāo)；否則，賦值為-1。ABCDEFHIJG下標(biāo)下標(biāo) data parentrightsib0A-1-11B022C0-13D1-14E255F2-16G377H388I3-19J4-1 存儲結(jié)構(gòu)的設(shè)計是一個非常靈活的過程。設(shè)計是否合理，取決于基于該存儲結(jié)構(gòu)的運算是否適合、是否方便，時間復(fù)雜度好不好等。6.4.2 孩子表示法孩子表示法多重鏈表表示法 每個結(jié)點有多個指針域，其中每個指針域指向一棵子樹的根結(jié)點。 不過，樹的每個結(jié)點的度是不同，故可以設(shè)計兩種方案來解決。方案一：指針

11、域的個數(shù)等于樹的度。其結(jié)構(gòu)為： data：數(shù)據(jù)域； child1childd：指針域，用來指向該節(jié)點的孩子結(jié)點。datachild1chilid2 child3 childd對于下圖的樹，樹的度是3，故指針域是3。ABCDEFHIJGABCDEFG H IJ頭指針很多結(jié)點的指針域都是空的。很多結(jié)點的指針域都是空的。對于樹中各結(jié)點的度相差很大對于樹中各結(jié)點的度相差很大時，是很浪費空間的。時，是很浪費空間的。方案二：每個結(jié)點的指針域的個數(shù)等于該結(jié)點的度，專門取一個位置來存儲結(jié)點指針域的個數(shù)。其結(jié)構(gòu)為： data：數(shù)據(jù)域； degree：度域，存儲該結(jié)點孩子結(jié)點的個數(shù)； child1childd：指

12、針域，指向該結(jié)點的各個孩子結(jié)點。data degree child1 chilid2childd方法實現(xiàn)ABCDEFHIJGA2B1C2D3E1F0頭指針H 0IJ0G 0 克服了浪費空間的缺點，空間利用率提高； 各鏈表結(jié)構(gòu)不同、維護(hù)結(jié)點的度數(shù)值，在運算上帶來時間上的損耗。能否有更好的方法，既可以減少空指針的浪費又能使結(jié)點結(jié)構(gòu)相同？孩子表示法孩子表示法 把每個結(jié)點的孩子結(jié)點排列起來，以單鏈表作存儲結(jié)構(gòu)，則n個結(jié)點有n個孩子鏈表，如果是葉子結(jié)點則此單鏈表為空。 然后n個頭指針又組成一個線性表，采用順序存儲結(jié)構(gòu)，存放進(jìn)一個一維數(shù)組中。下標(biāo)下標(biāo)0123456789ABCDEFGHIJdata fir

13、stchild1child next23456789設(shè)計兩種結(jié)點結(jié)構(gòu)孩子鏈表的孩子結(jié)點child：數(shù)據(jù)域，用來存儲某個結(jié)點在表頭數(shù)組中的下標(biāo)；next：指針域，用來存儲指向某結(jié)點的下一個孩子結(jié)點的指針。表頭數(shù)組的表頭結(jié)點data：數(shù)據(jù)域，存儲某結(jié)點的數(shù)據(jù)信息；firstchild：頭指針域，存儲該結(jié)點的孩子鏈表的頭指針。childnextdatafirstchild孩子表示法的結(jié)構(gòu)定義代碼/*樹的孩子表示法結(jié)構(gòu)定義樹的孩子表示法結(jié)構(gòu)定義*/#define MAX_TREE_SIZE 100typedef struct CTNode/孩子結(jié)點孩子結(jié)點int child;struct CTNode

14、 *next;*ChildPtr;typedef struct /表頭結(jié)構(gòu)表頭結(jié)構(gòu)TElemType data;ChildPtr firstchild;CTBox;typedef struct /樹結(jié)構(gòu)樹結(jié)構(gòu)CTBox nodesMAX_TREE_SIZE;/結(jié)點數(shù)組結(jié)點數(shù)組int r, n;CTree;6.4.3 孩子兄弟表示法孩子兄弟表示法任意一棵樹，它的結(jié)點的第一個孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我們設(shè)置兩個指針，分別指向該結(jié)點的第一個孩子和此結(jié)點的右兄弟。結(jié)點結(jié)構(gòu)為：data：數(shù)據(jù)域；firstchild：指針域，存儲該結(jié)點第一個孩子結(jié)點的存儲地址；righ

15、tsib：指針域，存儲該結(jié)點的右兄弟的存儲地址。datafirstchildrightsib結(jié)構(gòu)代碼/*樹的孩子兄弟表示法結(jié)構(gòu)定義樹的孩子兄弟表示法結(jié)構(gòu)定義*/typedef struct CSNodeTElemType data;struct CSNode *firstchild, *rightsib;CSNode,*CSTree;ABCDEF 頭指針G H I J 最大好處：把一棵復(fù)雜的樹變成一棵二叉樹。ABCDEF 頭指針G H I J 這樣就可以充分這樣就可以充分利用二叉樹的特利用二叉樹的特性和算法來處理性和算法來處理這棵樹了！這棵樹了！6.5 二叉樹二叉樹猜數(shù)字？猜數(shù)字？規(guī)則：只告訴

16、是“大了”或“小了”。 對于這種在某個階段都是兩種結(jié)果的情形，都適合用樹狀結(jié)構(gòu)來建模，而這種樹是一種很特殊的樹狀結(jié)構(gòu)，叫作二叉樹。二叉樹 n(n0)個結(jié)點的有限集合，該集合或者為空集(空二叉樹)，或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。ABCDEFHIJGABCDEFHIJG二叉樹不是二叉樹6.5.1 二叉樹特點二叉樹特點每個結(jié)點最多有兩棵子樹，所以二叉樹不存在度大于2的結(jié)點。左子樹和右子樹是有順序的，次序不能任意顛倒。即使樹中某結(jié)點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。ABCDEFHIJG樹1樹2二叉樹的特點：二叉樹的五種基本形態(tài)空二叉樹空二叉樹A

17、只有一個只有一個根節(jié)點根節(jié)點AAA根結(jié)點只根結(jié)點只有左子樹有左子樹根結(jié)點只根結(jié)點只有右子樹有右子樹根結(jié)點既有左子根結(jié)點既有左子樹，又有右子樹樹，又有右子樹例：3個結(jié)點的二叉樹樹1樹2樹3樹4樹5形態(tài)：兩層和三層；形態(tài)：兩層和三層；二叉樹：區(qū)別左右，二叉樹：區(qū)別左右，演變?yōu)檠葑優(yōu)? 5中形態(tài)。中形態(tài)。6.5.2 特殊二叉樹特殊二叉樹斜樹 所有結(jié)點只有左子樹的二叉樹叫左斜樹。 所有結(jié)點只有右子樹的二叉樹叫右斜樹。例：斜樹左斜樹右斜樹斜樹的特點： 每每一一層都只有層都只有一個結(jié)點，結(jié)點的一個結(jié)點，結(jié)點的個數(shù)與二叉樹的深個數(shù)與二叉樹的深度相同。度相同。線性線性表結(jié)構(gòu)？！表結(jié)構(gòu)？！滿二叉樹 在一棵二叉樹

18、中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。如下圖：滿二叉樹的特點： 葉子只能出現(xiàn)在最下一層；非葉子結(jié)點的度一定是2；在同樣深度的二叉樹中，滿二叉樹的結(jié)點個數(shù)最多，葉子數(shù)最多。完全二叉樹 對一棵具有n個結(jié)點的二叉樹按層序編號，如果編號為i(1in)的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹。如下圖所示：12984105367滿二叉樹一定是一棵完全二叉樹，完全二叉樹不一定是滿的。判斷：下列樹是否是完全二叉樹。123114589121367101415123114589126710123456712

19、3456樹1樹2樹4樹31231145896710123114589126710123458967樹1樹3樹2判斷某二叉樹是否是完全二叉樹的辦法：給樹的示意圖中每個結(jié)點按照滿二叉樹的結(jié)構(gòu)逐層順序編號，如果編號出現(xiàn)空擋，就說明不是完全二叉樹，否則就是。完全二叉樹的特點01葉子結(jié)點只能出現(xiàn)在最下兩層。02030405最下層的葉子一定集中在左部連續(xù)位置。倒數(shù)第二層若有葉子結(jié)點，一定都在右部連續(xù)位置。若結(jié)點度為1，則該結(jié)點只有左孩子。同樣結(jié)點樹的二叉樹，完全二叉樹的深度最小。6.6 二叉樹的性質(zhì)二叉樹的性質(zhì)ABCDEGHIJF01如果2in，則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點)；否則其左孩子是結(jié)點2i

20、。02如果2i+1n，則結(jié)點i無右孩子；否則其右孩子是結(jié)點2i+1.03129845367106.7 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)二叉樹順序存儲結(jié)構(gòu) 二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的結(jié)點，且結(jié)點的存儲位置(數(shù)組下標(biāo))要能體現(xiàn)結(jié)點之間的邏輯關(guān)系。 例：一棵完全二叉樹如圖所示ABCDEGHIJF 將這棵二叉樹存入到數(shù)組中，相應(yīng)的下標(biāo)對應(yīng)其同樣的位置：12345678910ABCDEGHIJF下標(biāo)ABCDEFGHIJ 由于完全二叉樹定義嚴(yán)格，所以順序結(jié)構(gòu)也可以表現(xiàn)出二叉樹的結(jié)構(gòu)來。 例：對于一棵一般二叉樹 盡管層序編號不能反映邏輯關(guān)系，但可以將其按完全二叉樹編號，把不存在的結(jié)點設(shè)

21、置為“”。ABCDEGHIJF12345678910下標(biāo)ABCEGJABDC12345678910 11 12 13 14 15下標(biāo)ABCCD二叉鏈表 二叉樹每個結(jié)點最多有兩個孩子，所以為它設(shè)計一個數(shù)據(jù)域和兩個指針域，我們稱這樣的鏈表叫做二叉鏈表。結(jié)點結(jié)構(gòu)如下圖所示, data：數(shù)據(jù)域 lchild、rchild：指針域，分別存放指向左孩子和右孩子的指針。lchilddatarchild/*二叉樹的二叉鏈表結(jié)點結(jié)構(gòu)定義二叉樹的二叉鏈表結(jié)點結(jié)構(gòu)定義*/typedef struct BiTNode/結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)TElemType data;/結(jié)點數(shù)據(jù)結(jié)點數(shù)據(jù)struct BiTNode *lc

22、hild, *rchild;/左右孩子指針左右孩子指針BiTNode,*BiTree; 結(jié)構(gòu)示意圖ABCDE F 頭指針 G H I J 三叉鏈表 根據(jù)需要增加一個指向其雙親的指針域，就稱為三叉鏈表。typedef struct node datatype data; struct node *lchild, *rchild, *parent;JD;ABCDEFG A B C D E F Glchilddataparentrchild6.8 遍歷二叉樹遍歷二叉樹二叉樹的遍歷(traversing binary tree)是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中所有結(jié)點，使得每個結(jié)點被訪問

23、一次且僅被訪問一次。訪問：訪問：根據(jù)實際需要根據(jù)實際需要來確定具體做什么。來確定具體做什么。比如：對每個結(jié)點進(jìn)比如：對每個結(jié)點進(jìn)行相關(guān)計算、輸出打行相關(guān)計算、輸出打印等。印等。樹的結(jié)點之間不存在樹的結(jié)點之間不存在唯一的前驅(qū)和后繼關(guān)唯一的前驅(qū)和后繼關(guān)系。由于系。由于選擇方式的選擇方式的不同，遍歷的次序就不同，遍歷的次序就完全不同。完全不同。為什么要研究遍歷方法？ 計算機只會處理線性序列，而4種遍歷方法把樹中結(jié)點變成某種意義的線性序列；不同的遍歷提供了對結(jié)點依次處理的不同方式，可以在遍歷過程中對結(jié)點進(jìn)行各種處理。 遍歷操作是一個遞歸的過程，因此，這三種遍歷操作的算法可以用遞歸函數(shù)實現(xiàn)。6.8.2

24、二叉樹的遍歷方法二叉樹的遍歷方法 二叉樹的遍歷方式可以很多，如果限制從左到右的習(xí)慣方式，則主要分為4種：前序遍歷ABCDFGHIE規(guī)則：規(guī)則：若二叉樹為空，若二叉樹為空，則空操作返回，否則則空操作返回，否則(1)訪問根結(jié)點，訪問根結(jié)點，(2)前序遍歷左子樹，前序遍歷左子樹，(3)前序遍歷右子樹。前序遍歷右子樹。遍歷的順序為：遍歷的順序為：ABDGHCEIFABDGHCEIF二叉樹的前序遍歷算法/*二叉樹的前序遍歷遞歸算法二叉樹的前序遍歷遞歸算法*/void PreOrderTraverse(BiTree T)if (T = NULL)return;printf(%c, T-data);/顯示結(jié)

25、點數(shù)據(jù)顯示結(jié)點數(shù)據(jù)PreOrderTraverse(T-lchild);/先序遍歷左子樹先序遍歷左子樹PreOrderTraverse(T-rchild);/先序遍歷右子樹先序遍歷右子樹中序遍歷ABCDFGHIE規(guī)則：規(guī)則：若二叉樹為空，若二叉樹為空，則空操作返回，否則則空操作返回，否則從根結(jié)點開始，從根結(jié)點開始，(1)中序遍歷根節(jié)點的中序遍歷根節(jié)點的左子樹左子樹(2)訪問根節(jié)點訪問根節(jié)點(3)中序遍歷右子樹。中序遍歷右子樹。中序遍歷中序遍歷的順序為的順序為：GDHBAEICFGDHBAEICF二叉樹的中序遍歷算法/*二叉樹二叉樹的的中序中序遍歷遍歷遞歸算法遞歸算法*/void InOrder

26、Traverse(BiTree T)if (T = NULL)return;InOrderTraverse(T-lchild); /中序中序遍歷遍歷左子樹左子樹printf(%c, T-data);/顯示結(jié)點顯示結(jié)點數(shù)據(jù)數(shù)據(jù)InOrderTraverse(T-rchild);/中中序序遍歷右子樹遍歷右子樹后序遍歷ABCDFGHIE規(guī)則：規(guī)則：若二叉樹為空，若二叉樹為空，則空操作返回，否則則空操作返回，否則從左到右先葉子后結(jié)從左到右先葉子后結(jié)點的方式遍歷訪問左點的方式遍歷訪問左右子樹，最后是訪問右子樹，最后是訪問根結(jié)點。根結(jié)點。后后序遍歷序遍歷的順序為的順序為：GHDBIEFCAGHDBIEFC

27、A二叉樹的后序遍歷算法/*二叉樹二叉樹的后序遍歷的后序遍歷遞歸算法遞歸算法*/void PostOrderTraverse(BiTree T)if (T = NULL)return;PostOrderTraverse(T-lchild);/后序后序遍歷遍歷左子樹左子樹PostOrderTraverse(T-rchild);/后序后序遍歷右子遍歷右子樹樹printf(%c, T-data);/顯示結(jié)點顯示結(jié)點數(shù)據(jù)數(shù)據(jù)層序遍歷ABCDFGHIE規(guī)則：規(guī)則：若二叉樹為空，若二叉樹為空，則空操作返回，否則則空操作返回，否則從樹的第一層，也就從樹的第一層，也就是根結(jié)點開始訪問，是根結(jié)點開始訪問，從上而下

28、逐層遍歷，從上而下逐層遍歷，在同一層中，按從左在同一層中，按從左到右的順序?qū)Y(jié)點逐到右的順序?qū)Y(jié)點逐個訪問。個訪問。層序遍歷層序遍歷的順序為的順序為：ABCDEFGHIABCDEFGHI練習(xí)：求出二叉樹的先序、中序、后序遍歷結(jié)果。先序遍歷結(jié)果：ABDEGHCFI中序遍歷結(jié)果：DBGEHACFI后序遍歷結(jié)果：DGHEBIFCA練習(xí)：求出二叉樹的先序、中序、后序遍歷結(jié)果。G HD E FB CA先序遍歷結(jié)果：ABDGCEFH中序遍歷結(jié)果：DGBAECHF后序遍歷結(jié)果：GDBEHFCA練習(xí)-+/a*b-efcd先序遍歷結(jié)果：- + a * b c d / e f中序遍歷結(jié)果：a + b * c d

29、e / f后序遍歷結(jié)果：a b c d - * + e f / -層序遍歷結(jié)果：- + / a * e f b c d6.8.6 推推導(dǎo)導(dǎo)遍歷結(jié)果遍歷結(jié)果已知一棵二叉樹的前序遍歷序列為ABCDEF，中序遍歷序列為CBAEDF，請問這棵二叉樹的后序遍歷序列結(jié)果是多少？二叉樹的中序序列為ABCDEFG，后序序列為BDCAFGE，求前序序列？二叉樹遍歷的性質(zhì)注意：已知前序和后序遍歷是不能確定一棵二叉樹的。已知前序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹。已知后序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹。后序序列：CBEFDA前序序列：EACBDGF6.9 二叉樹的建立二叉樹的建立如果我們

30、要在內(nèi)存中建立一個如下圖的樹，為了能讓每個結(jié)點確認(rèn)是否有左右孩子，我們對它進(jìn)行了擴展，即將二叉樹中每個結(jié)點的空指針引出一個虛結(jié)點，其值為一個特定值。我們稱這種處理后的二叉樹為原二叉樹的擴展二叉樹。ABCDABCD# # # # # #原二叉樹原二叉樹擴展擴展二叉樹二叉樹假設(shè)二叉樹的結(jié)點均為一個字符，擴展二叉樹的前序遍歷序列結(jié)果是多少？將該前序遍歷序列用鍵盤一次鍵入，就生成該二叉樹。實現(xiàn)代碼見下頁：ABCD# # # # # #擴展擴展二叉樹二叉樹前序遍歷前序遍歷序：序：AB#D#C#/*按前序輸入二叉樹中結(jié)點的值（一個字符）按前序輸入二叉樹中結(jié)點的值（一個字符）*/*#表示空樹，構(gòu)造二叉鏈表表

31、示二叉樹表示空樹，構(gòu)造二叉鏈表表示二叉樹T*/void CreateBitree(BiTree *T)TElemType ch;scanf(%c, &ch);if (ch = #)*T = NULL;else*T=(BiTree)malloc(sizeof(BiTNode);if (!*T)exit(OVERFLOW);(*T)-data = ch;/生成根結(jié)點生成根結(jié)點CreateBitree(&(*T)-lchild);/構(gòu)造左子樹構(gòu)造左子樹CreateBitree(&(*T)-rchild);/構(gòu)造右子樹構(gòu)造右子樹基本操作：構(gòu)造空二叉樹基本操作：構(gòu)造空二叉樹/*構(gòu)

32、造空二叉樹構(gòu)造空二叉樹T*/Status InitBiTree(BiTree *T)*T = NULL;return OK;課堂練習(xí) 建立二叉樹，并實現(xiàn)二叉樹的3種遍歷的遞歸算法 void CreateBiTree(BiTree *T) void PreOrderTraverse(BiTree T) void InOrderTraverse(BiTree T) void PostOrderTraverse(BiTree T) 要求：在編譯器上調(diào)試通過寫到作業(yè)本上，提交紙質(zhì)作業(yè)。6.10 線索線索二叉樹二叉樹線索二叉樹原理ABCDE F 頭指針 G H I J 觀察：指針域有許多“”(空指針域)

33、。想辦法利用起來？！中序遍歷：HDIBJEAFCG清楚的知道任意一個結(jié)點的前驅(qū)和后繼?？紤]利用空地址存放指向結(jié)點的某種遍歷次序下的前驅(qū)和后繼結(jié)點的地址。6.10.1 線索二叉樹原理線索二叉樹原理線索線索線索鏈表線索鏈表線索二叉樹線索二叉樹線索化線索化指向前驅(qū)和后繼的指針。按照不同的遍歷次序進(jìn)行線索化，可得到不同的線索二叉樹。加上線索的二叉鏈表。對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程。把二叉樹進(jìn)行中序遍歷后，將所有的空指針域中的rchilid改為指向它的后繼結(jié)點。ABCDE F G HI J頭指針NULL中 序 遍 歷 ：HDIBJEAFCG共有共有6 6個空指針個空指針域被利用。域被利

34、用。把二叉樹的所有空指針域中的lchilid改為指向當(dāng)前結(jié)點的前驅(qū)。ABCDEFGHIJ頭指針NULL中 序 遍 歷 ：HDIBJEAFCG共有共有5 5個空指針個空指針域被利用。域被利用。把一棵二叉樹轉(zhuǎn)變成一個雙向鏈表ABCDFGHIEJ 如何知道某一結(jié)點的lchild是指向它的左孩子還是指向前驅(qū)？rchild是指向它的右孩子還是后繼？再增設(shè)兩個標(biāo)志域ltag和rtag，只是存放0或1數(shù)字的布爾型變量。結(jié)點結(jié)構(gòu)為 ltag=0，指向該結(jié)點的左孩子； ltag=1，指向該結(jié)點的前驅(qū)。 rtag=0，指向該結(jié)點的右孩子； rtag=1，指向該結(jié)點的后繼。lchildltagdatartagrch

35、ild二叉鏈表圖修改后，如下圖0 A 0頭指針1 G 10 B 00 D 01 H 11I11 J 11 F 10 C 00 E 16.10.2 線索二叉樹結(jié)構(gòu)實現(xiàn)線索二叉樹結(jié)構(gòu)實現(xiàn)/*二叉樹的二叉線索存儲結(jié)構(gòu)定義二叉樹的二叉線索存儲結(jié)構(gòu)定義*/*Link=0表示指向左右孩子指針表示指向左右孩子指針*/*Thread=1表示指向前驅(qū)或后繼的線索表示指向前驅(qū)或后繼的線索*/typedef enum Link, Thread PointerTag; typedef struct BiThrNode/二叉線索存儲結(jié)點結(jié)構(gòu)二叉線索存儲結(jié)點結(jié)構(gòu)TElemType data;/結(jié)點數(shù)據(jù)結(jié)點數(shù)據(jù)struct

36、 BiThrNode *lchild, *rchild;/左右孩子指針左右孩子指針PointerTag LTag;PointerTag RTag;/左右標(biāo)志左右標(biāo)志BiThrNode,*BiThrTree;知識回顧知識回顧(枚舉類型枚舉類型)適用情況：一個變量只有幾種可能的值。枚舉：把可能的值一一列舉出來，變量的值只限于列舉出來的值的范圍內(nèi)。聲明枚舉類型的一般形式 enum 枚舉名 枚舉元素列表 例：enum Weekday sun,mon,tue,wed,thu,fri,sat;使用枚舉類型定義變量 例：enum Weekday workday,weekend;枚舉變量線索化的過程就是在遍歷

37、的過程中修改空指針的過程。中序遍歷線索化的遞歸函數(shù)代碼：BiThrTree pre;/全局變量，始終指向剛剛訪問過的結(jié)點全局變量，始終指向剛剛訪問過的結(jié)點void InThreading(BiThrTree p)if (p)InThreading(p-lchild);/遞歸左子樹線索化遞歸左子樹線索化if (!p-lchild)/沒有左孩子沒有左孩子p-LTag = Thread;/前驅(qū)線索前驅(qū)線索p-lchild = pre;/左孩子指針指向前驅(qū)左孩子指針指向前驅(qū)接上頁if (!pre-rchild)/前驅(qū)沒有右孩子前驅(qū)沒有右孩子pre-RTag = Thread;/后繼線索后繼線索pre-

38、LTag = p;/前驅(qū)右孩子指針前驅(qū)右孩子指針指指/向后繼向后繼(當(dāng)前結(jié)點當(dāng)前結(jié)點p)pre=p;InThreading(p-rchild);/遞歸右子樹線索化遞歸右子樹線索化6.11 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換將樹轉(zhuǎn)換為二叉樹的步驟：01在所有兄弟結(jié)在所有兄弟結(jié)點之間加一條點之間加一條連線。連線。加線加線02對樹中每個結(jié)點，對樹中每個結(jié)點，只保留它與第一個只保留它與第一個孩子結(jié)點的連線，孩子結(jié)點的連線，刪除它與其他孩子刪除它與其他孩子結(jié)點之間的連線。結(jié)點之間的連線。去線去線03以樹的根結(jié)點為軸以樹的根結(jié)點為軸心，將整棵樹順時心，將整棵樹順時針旋轉(zhuǎn)一定角度，針旋轉(zhuǎn)一定角度，

39、使之結(jié)構(gòu)層次分明。使之結(jié)構(gòu)層次分明。層次層次調(diào)整調(diào)整ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI 樹轉(zhuǎn)換成的二叉樹其右子樹一定為空。例：練習(xí)：將下面的樹轉(zhuǎn)換為二叉樹(a) 一般的樹ABCDEFGH(b) 相鄰兄弟加連線ABCDEFGH(c) 刪除雙親與不是第一個孩子的連線ABCDEFGH(d) 整理后的二叉樹ABCDEFGH6.11.2 森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹的步驟：1 把每個樹轉(zhuǎn)換為二叉樹。 第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹的根節(jié)點的右孩子，用線連接起來。2例：ABCDEF

40、GHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ擁有三棵樹的森林步驟1：森林中每棵樹轉(zhuǎn)換為二叉樹步驟2：將所有二叉樹轉(zhuǎn)換成一棵二叉樹練習(xí)：將下面森林轉(zhuǎn)換為二叉樹ABCKEFGHIDLJ6.11.3 二叉樹轉(zhuǎn)換為樹二叉樹轉(zhuǎn)換為樹步驟： 1.加線。加線。若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來。 2.去去線。線。刪除原二叉樹中所有結(jié)點與其右孩子結(jié)點的連線。 3.層次調(diào)整。層次調(diào)整。使之結(jié)構(gòu)層次分明。例：ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI練習(xí)：將下列二叉樹轉(zhuǎn)換

41、為樹(d) 一般樹ABCDEFGH(a) 二叉樹ABCDEFGH(b) 添加連線ABCDEFGH(c) 刪除連線ABCDEFGH6.11.4 二叉樹轉(zhuǎn)換為森林二叉樹轉(zhuǎn)換為森林步驟： 抹抹線：線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹。 還原：還原：將孤立的二叉樹還原成樹。例：ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉樹步驟1：尋找右孩子去線步驟2：將分離的二叉樹轉(zhuǎn)換成樹6.11.5 樹與森林的遍歷樹與森林的遍歷樹的遍歷 1.先根遍歷樹。先訪問樹的根結(jié)點，再依次先根遍歷根的每棵子樹。 2.后根遍歷

42、樹。先依次后根遍歷每棵子樹，再訪問根結(jié)點。 例：ABDFCG GE E先根遍歷序列：ABEFCDG后根遍歷序列：EFBCGDA森林的遍歷 1.前序遍歷：訪問森林中第一棵樹的根結(jié)點，再依次先根遍歷根的每棵子樹，然后依次用同樣的方式遍歷除去第一棵樹的剩余樹構(gòu)成的森林。 2.后序遍歷：先訪問森林中第一棵樹，后根遍歷的方式遍歷每棵子樹，再訪問根結(jié)點，然后依次同樣方式遍歷除去第一棵樹的剩余樹構(gòu)成的森林。6.12 赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用赫夫曼樹(舉例) 有些課程需要將最終的分?jǐn)?shù)由百分制轉(zhuǎn)換成五級分制：if (a60)b=“不及格不及格”else if (a70)b=“及格及格”else if (

43、a80)b=“良好良好”else if (a90)b=“中等中等”elseb=“優(yōu)秀優(yōu)秀” 如果學(xué)生的成績在5個等級上的分布規(guī)律如表所示 將這棵二叉樹重新進(jìn)行分配：分?jǐn)?shù)分?jǐn)?shù)059 6069 7079 8089 90100所占比例5%15%40%30%10%大約占大約占80%80%的成績都需要的成績都需要經(jīng)過經(jīng)過3 3次以上的判斷才可次以上的判斷才可以得到結(jié)果。以得到結(jié)果。從圖中感覺，應(yīng)該效從圖中感覺，應(yīng)該效率要高一些。率要高一些。6.12.2 赫夫曼樹定義與原理赫夫曼樹定義與原理赫夫曼樹的基本概念 例：先把這兩棵樹簡化成葉子結(jié)點帶權(quán)的二叉樹。ABCDE515403010CD DEA AB515403010二叉樹a二叉樹b權(quán)權(quán)(Weight)：樹結(jié)點間的邊樹結(jié)點間的邊相關(guān)