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

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

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

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

4、：無后繼中間元素：一個(gè)前驅(qū)一個(gè)后繼中間元素：一個(gè)前驅(qū)一個(gè)后繼樹結(jié)構(gòu)樹結(jié)構(gòu)根結(jié)點(diǎn)：無雙親，唯一根結(jié)點(diǎn)：無雙親，唯一葉結(jié)點(diǎn)：無孩子，可以多個(gè)葉結(jié)點(diǎn)：無孩子，可以多個(gè)中間結(jié)點(diǎn)：一個(gè)雙親多個(gè)孩子中間結(jié)點(diǎn)：一個(gè)雙親多個(gè)孩子6.3 樹的抽象數(shù)據(jù)類型樹的抽象數(shù)據(jù)類型ADT 樹樹(Tree)Data樹是由一個(gè)根結(jié)點(diǎn)和若干棵子樹構(gòu)成。樹中結(jié)點(diǎn)樹是由一個(gè)根結(jié)點(diǎn)和若干棵子樹構(gòu)成。樹中結(jié)點(diǎn)具有相同數(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é)點(diǎn)。的根結(jié)點(diǎn)。Value(T,cur_e)：cur_e是樹是樹T中一個(gè)結(jié)點(diǎn)，返回此中一個(gè)結(jié)點(diǎn)，返回此結(jié)點(diǎn)的值。結(jié)點(diǎn)的值。Assign(T,cur_e,value)：給樹：給樹T的結(jié)點(diǎn)的結(jié)點(diǎn)cur_e賦值為賦值為value。Parent(T,cur_e)：

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

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

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

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

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

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

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

13、stchild1child next23456789設(shè)計(jì)兩種結(jié)點(diǎn)結(jié)構(gòu)孩子鏈表的孩子結(jié)點(diǎn)child：數(shù)據(jù)域，用來存儲(chǔ)某個(gè)結(jié)點(diǎn)在表頭數(shù)組中的下標(biāo)；next：指針域，用來存儲(chǔ)指向某結(jié)點(diǎn)的下一個(gè)孩子結(jié)點(diǎn)的指針。表頭數(shù)組的表頭結(jié)點(diǎn)data：數(shù)據(jù)域，存儲(chǔ)某結(jié)點(diǎn)的數(shù)據(jù)信息；firstchild：頭指針域，存儲(chǔ)該結(jié)點(diǎn)的孩子鏈表的頭指針。childnextdatafirstchild孩子表示法的結(jié)構(gòu)定義代碼/*樹的孩子表示法結(jié)構(gòu)定義樹的孩子表示法結(jié)構(gòu)定義*/#define MAX_TREE_SIZE 100typedef struct CTNode/孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)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é)點(diǎn)數(shù)組結(jié)點(diǎn)數(shù)組int r, n;CTree;6.4.3 孩子兄弟表示法孩子兄弟表示法任意一棵樹，它的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我們?cè)O(shè)置兩個(gè)指針，分別指向該結(jié)點(diǎn)的第一個(gè)孩子和此結(jié)點(diǎn)的右兄弟。結(jié)點(diǎn)結(jié)構(gòu)為：data：數(shù)據(jù)域；firstchild：指針域，存儲(chǔ)該結(jié)點(diǎn)第一個(gè)孩子結(jié)點(diǎn)的存儲(chǔ)地址；righ

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

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

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

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

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

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

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

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

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

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

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

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

28、逐層遍歷，從上而下逐層遍歷，在同一層中，按從左在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。個(gè)訪問。層序遍歷層序遍歷的順序?yàn)榈捻樞驗(yàn)椋篈BCDEFGHIABCDEFGHI練習(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，請(qǐng)問這棵二叉樹的后序遍歷序列結(jié)果是多少？二叉樹的中序序列為ABCDEFG，后序序列為BDCAFGE，求前序序列？二叉樹遍歷的性質(zhì)注意：已知前序和后序遍歷是不能確定一棵二叉樹的。已知前序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹。已知后序遍歷序列和中序遍歷序列，可以唯一確定一棵二叉樹。后序序列：CBEFDA前序序列：EACBDGF6.9 二叉樹的建立二叉樹的建立如果我們

30、要在內(nèi)存中建立一個(gè)如下圖的樹，為了能讓每個(gè)結(jié)點(diǎn)確認(rèn)是否有左右孩子，我們對(duì)它進(jìn)行了擴(kuò)展，即將二叉樹中每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，其值為一個(gè)特定值。我們稱這種處理后的二叉樹為原二叉樹的擴(kuò)展二叉樹。ABCDABCD# # # # # #原二叉樹原二叉樹擴(kuò)展擴(kuò)展二叉樹二叉樹假設(shè)二叉樹的結(jié)點(diǎn)均為一個(gè)字符，擴(kuò)展二叉樹的前序遍歷序列結(jié)果是多少？將該前序遍歷序列用鍵盤一次鍵入，就生成該二叉樹。實(shí)現(xiàn)代碼見下頁：ABCD# # # # # #擴(kuò)展擴(kuò)展二叉樹二叉樹前序遍歷前序遍歷序：序：AB#D#C#/*按前序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符）按前序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符）*/*#表示空樹，構(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é)點(diǎn)生成根結(jié)點(diǎn)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í) 建立二叉樹，并實(shí)現(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清楚的知道任意一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼?？紤]利用空地址存放指向結(jié)點(diǎn)的某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的地址。6.10.1 線索二叉樹原理線索二叉樹原理線索線索線索鏈表線索鏈表線索二叉樹線索二叉樹線索化線索化指向前驅(qū)和后繼的指針。按照不同的遍歷次序進(jìn)行線索化，可得到不同的線索二叉樹。加上線索的二叉鏈表。對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程。把二叉樹進(jìn)行中序遍歷后，將所有的空指針域中的rchilid改為指向它的后繼結(jié)點(diǎn)。ABCDE F G HI J頭指針NULL中 序 遍 歷 ：HDIBJEAFCG共有共有6 6個(gè)空指針個(gè)空指針域被利用。域被利

34、用。把二叉樹的所有空指針域中的lchilid改為指向當(dāng)前結(jié)點(diǎn)的前驅(qū)。ABCDEFGHIJ頭指針NULL中 序 遍 歷 ：HDIBJEAFCG共有共有5 5個(gè)空指針個(gè)空指針域被利用。域被利用。把一棵二叉樹轉(zhuǎn)變成一個(gè)雙向鏈表ABCDFGHIEJ 如何知道某一結(jié)點(diǎn)的lchild是指向它的左孩子還是指向前驅(qū)？rchild是指向它的右孩子還是后繼？再增設(shè)兩個(gè)標(biāo)志域ltag和rtag，只是存放0或1數(shù)字的布爾型變量。結(jié)點(diǎn)結(jié)構(gòu)為 ltag=0，指向該結(jié)點(diǎn)的左孩子； ltag=1，指向該結(jié)點(diǎn)的前驅(qū)。 rtag=0，指向該結(jié)點(diǎn)的右孩子； rtag=1，指向該結(jié)點(diǎn)的后繼。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)實(shí)現(xiàn)線索二叉樹結(jié)構(gòu)實(shí)現(xiàn)/*二叉樹的二叉線索存儲(chǔ)結(jié)構(gòu)定義二叉樹的二叉線索存儲(chǔ)結(jié)構(gòu)定義*/*Link=0表示指向左右孩子指針表示指向左右孩子指針*/*Thread=1表示指向前驅(qū)或后繼的線索表示指向前驅(qū)或后繼的線索*/typedef enum Link, Thread PointerTag; typedef struct BiThrNode/二叉線索存儲(chǔ)結(jié)點(diǎn)結(jié)構(gòu)二叉線索存儲(chǔ)結(jié)點(diǎn)結(jié)構(gòu)TElemType data;/結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù)struct

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

37、的過程中修改空指針的過程。中序遍歷線索化的遞歸函數(shù)代碼：BiThrTree pre;/全局變量，始終指向剛剛訪問過的結(jié)點(diǎn)全局變量，始終指向剛剛訪問過的結(jié)點(diǎn)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é)點(diǎn)當(dāng)前結(jié)點(diǎn)p)pre=p;InThreading(p-rchild);/遞歸右子樹線索化遞歸右子樹線索化6.11 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換將樹轉(zhuǎn)換為二叉樹的步驟：01在所有兄弟結(jié)在所有兄弟結(jié)點(diǎn)之間加一條點(diǎn)之間加一條連線。連線。加線加線02對(duì)樹中每個(gè)結(jié)點(diǎn)，對(duì)樹中每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)只保留它與第一個(gè)孩子結(jié)點(diǎn)的連線，孩子結(jié)點(diǎn)的連線，刪除它與其他孩子刪除它與其他孩子結(jié)點(diǎn)之間的連線。結(jié)點(diǎn)之間的連線。去線去線03以樹的根結(jié)點(diǎn)為軸以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)心，將整棵樹順時(shí)針旋轉(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) 刪除雙親與不是第一個(gè)孩子的連線ABCDEFGH(d) 整理后的二叉樹ABCDEFGH6.11.2 森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹的步驟：1 把每個(gè)樹轉(zhuǎn)換為二叉樹。 第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹的根節(jié)點(diǎn)的右孩子，用線連接起來。2例：ABCDEF

40、GHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ擁有三棵樹的森林步驟1：森林中每棵樹轉(zhuǎn)換為二叉樹步驟2：將所有二叉樹轉(zhuǎn)換成一棵二叉樹練習(xí)：將下面森林轉(zhuǎn)換為二叉樹ABCKEFGHIDLJ6.11.3 二叉樹轉(zhuǎn)換為樹二叉樹轉(zhuǎn)換為樹步驟： 1.加線。加線。若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來。 2.去去線。線。刪除原二叉樹中所有結(jié)點(diǎn)與其右孩子結(jié)點(diǎn)的連線。 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é)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹。 還原：還原：將孤立的二叉樹還原成樹。例：ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉樹步驟1：尋找右孩子去線步驟2：將分離的二叉樹轉(zhuǎn)換成樹6.11.5 樹與森林的遍歷樹與森林的遍歷樹的遍歷 1.先根遍歷樹。先訪問樹的根結(jié)點(diǎn)，再依次先根遍歷根的每棵子樹。 2.后根遍歷

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

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