數(shù)據(jù)結(jié)構(gòu)-第6章-樹和二叉樹-4.-樹和森林(V1)

6.1樹的基本概念6.2

二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5哈夫曼樹及其應(yīng)用6.4.1樹樹和二叉樹的區(qū)別：（1）二叉樹至多有兩個(gè)子樹，樹則不然；（2）二叉樹的子樹有左右之分，而樹的子樹沒有次序；（3）二叉樹允許樹為空，樹一般不允許為空（個(gè)別教材允許為空）6.4.1樹的存儲(chǔ)結(jié)構(gòu)1.雙親表示法2.孩子表示法3.孩子兄弟表示法最常用6.4.1樹的存儲(chǔ)結(jié)構(gòu)1.雙親表示法用一組連續(xù)的存儲(chǔ)空間來存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附加一個(gè)指示器(整數(shù)域)

，用以指示雙親結(jié)點(diǎn)的位置(下標(biāo)值)。結(jié)點(diǎn)的結(jié)構(gòu)表示：DataParent樹的結(jié)點(diǎn)結(jié)構(gòu)定義：typedefstructPTNode{ElemTypedata;intparent;}PTNode;6.4.1樹的存儲(chǔ)結(jié)構(gòu)

1.雙親表示法#defineMAX_SIZE100typedefstruct{PTNodeNodes[MAX_SIZE];intnum;/*結(jié)點(diǎn)數(shù)*/}Ptree;FGHIRABCDER-10A01B02C03D14E15F36G67H68I69......10~MAX_Size-16.4.1樹的存儲(chǔ)結(jié)構(gòu)2.孩子表示法每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)構(gòu)成一個(gè)單鏈表，即有n個(gè)結(jié)點(diǎn)就有n個(gè)孩子鏈表；n個(gè)孩子的數(shù)據(jù)和n個(gè)孩子鏈表的頭指針組成一個(gè)順序表；結(jié)點(diǎn)結(jié)構(gòu)定義：typedefstructPTNode{ElemTypedata;structPTNode*next;}PTNode;順序表定義：#defineN6/*結(jié)點(diǎn)數(shù)*/PTNodeNodes[N];6.4.1樹的存儲(chǔ)結(jié)構(gòu)6123451021324∧35∧46∧56∧23∧45∧

6.4.1樹的存儲(chǔ)結(jié)構(gòu)3.孩子兄弟表示法(二叉樹表示法)以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)鏈域，分別指向第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟(右兄弟)結(jié)點(diǎn)。第一個(gè)孩子結(jié)點(diǎn)下一個(gè)兄弟結(jié)點(diǎn)firstchilddatanextsibing6.4.1樹的存儲(chǔ)結(jié)構(gòu)typedefstructCSnode{ElemTypedata;structCSnode*firstchild,*nextsibing;}CSNode;6.4.1樹的存儲(chǔ)結(jié)構(gòu)FGRABCDE

R?

A?D

C??G?B?F??E?6.4.2樹、森林和二叉樹的轉(zhuǎn)換1.樹轉(zhuǎn)換為二叉樹將樹轉(zhuǎn)換成二叉樹在“孩子兄弟表示法”中已給出，其詳細(xì)步驟是：⑴加線。在樹的所有相鄰兄弟結(jié)點(diǎn)之間加一條連線。⑵去連線。除最左的第一個(gè)子結(jié)點(diǎn)外，父結(jié)點(diǎn)與所有其它子結(jié)點(diǎn)的連線都去掉。⑶旋轉(zhuǎn)。將樹以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)450，使之層次分明。6.4.2樹、森林和二叉樹的轉(zhuǎn)換(a)一般的樹

FGRABCDEFGRABCDE(b)加虛線，去連線后

(C)轉(zhuǎn)換后的二叉樹FGRACDBE6.4.2樹、森林和二叉樹的轉(zhuǎn)換2.森林轉(zhuǎn)化為二叉樹將F={T1,T2,?,Tn}中的每棵樹轉(zhuǎn)換成二叉樹。按森林中樹的次序，后一棵樹作為前一棵樹的根結(jié)點(diǎn)的右子樹，依次類推，則第一棵樹的根結(jié)點(diǎn)就是轉(zhuǎn)換后生成的二叉樹的根結(jié)點(diǎn)。ACBDGMLHK(a)森林(b)森林中每棵樹對(duì)應(yīng)的二叉樹ABCDGLKHM(c)森林對(duì)應(yīng)的二叉樹ABCDGLKHM6.4.2樹、森林和二叉樹的轉(zhuǎn)換3.二叉樹轉(zhuǎn)換為樹或森林其步驟是：⑴加虛線。若某結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子，則將該結(jié)點(diǎn)的右孩子、右孩子的右孩子、...，都與該結(jié)點(diǎn)的父結(jié)點(diǎn)加虛線相連，如圖(a)所示。⑵去連線。去掉原二叉樹中所有父結(jié)點(diǎn)與其右孩子之間的連線，如圖(b)所示。⑶規(guī)整化。將圖中各結(jié)點(diǎn)按層次排列且將所有的虛線變成實(shí)線，整理得到樹或者森林，如圖(c)所示。6.4.2樹、森林和二叉樹的轉(zhuǎn)換(C)還原后的樹FGRABCDE(a)加虛線后FGRACDBE(b)去連線后CFGRADBE6.4.2樹、森林和二叉樹的轉(zhuǎn)換二叉樹

CERADB

R?

A?D??C?

B?E?樹

RABCDE對(duì)應(yīng)關(guān)系

R?

A?D??C?

B?E??C?

B?E?

R

A?D?存儲(chǔ)解釋存儲(chǔ)解釋練習(xí)如圖所示的二叉樹BT是由森林T1轉(zhuǎn)換而來的二叉樹，那么森林T1中有（）葉子結(jié)點(diǎn)。ABCDELKHM技巧：無左孩子者即為葉子結(jié)點(diǎn)56.4.3樹和森林的遍歷1.樹的遍歷由樹結(jié)構(gòu)的定義可知，樹的遍歷有二種方法。⑴先序遍歷：先訪問根結(jié)點(diǎn)，然后依次先序遍歷完每棵子樹。⑵后序遍歷：先依次后序遍歷完每棵子樹，然后訪問根結(jié)點(diǎn)。等價(jià)于對(duì)應(yīng)二叉樹的先序遍歷等價(jià)于對(duì)應(yīng)二叉樹的中序遍歷6.4.3樹和森林的遍歷先序遍歷的次序是：ABCDEFGIJHK后序遍歷的次序是：CDBFIJGHEKAABDCKGJIFHE6.4.3樹和森林的遍歷1.森林的遍歷⑴先序遍歷：按先序遍歷樹的方式依次遍歷F中的每棵樹。(2)中序遍歷：按中序遍歷樹的方式依次遍歷F中的每棵樹。等價(jià)于樹的先序遍歷等價(jià)于樹的后序遍歷6.4樹和森林1、樹的存儲(chǔ)結(jié)構(gòu)：孩子兄弟表示法（二叉鏈表表示法）---掌握2、樹、森林和二叉樹之間的轉(zhuǎn)換：把樹的孩子兄弟表示法解釋為二叉樹的二叉