數(shù)據(jù)結(jié)構(gòu)課件：第6章 樹和二叉樹3樹和森林

1、樹和森林第6章 樹和二叉樹樹的基本概念二叉樹遍歷二叉樹和線索二叉樹赫夫曼樹及其應(yīng)用樹的存儲(chǔ)結(jié)構(gòu)6.4 樹和森林三種常用的存儲(chǔ)結(jié)構(gòu)：(1)雙親表示法(2)孩子表示法(3)孩子兄弟表示法樹的存儲(chǔ)結(jié)構(gòu)雙親表示法6.4 樹和森林即以一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在鏈表中的位置。DACREBFHGK雙親結(jié)點(diǎn)下標(biāo)9876543210666311000-1KHGFEDCBAR樹的雙親表存儲(chǔ)表示6.4 樹和森林#define MAX_TREE_SIZE 100 typedef struct PTNode /結(jié)點(diǎn)結(jié)構(gòu) Elem data; int parent; / 雙親

2、位置域 PTNode;typedef struct /樹結(jié)構(gòu) PTNode nodesMAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;樹的存儲(chǔ)結(jié)構(gòu)雙親表示法6.4 樹和森林 這種存儲(chǔ)結(jié)構(gòu)利用每個(gè)結(jié)點(diǎn)（除根結(jié)點(diǎn)）只有唯一雙親的性質(zhì)，Parent(T, x)操作可在常量時(shí)間內(nèi)實(shí)現(xiàn)。反復(fù)調(diào)用Parent操作，直到遇見無雙親的結(jié)點(diǎn)時(shí)，便找到了樹的根。但在這種表示方式中，求結(jié)點(diǎn)的孩子時(shí)需遍歷整個(gè)結(jié)構(gòu)。樹的存儲(chǔ)結(jié)構(gòu)孩子表示法6.4 樹和森林 由于樹中每個(gè)結(jié)點(diǎn)可能有多棵子樹，則考慮用多重鏈表，即結(jié)點(diǎn)有多個(gè)指針域，其中每個(gè)指針指向一棵子樹的根結(jié)點(diǎn)，此時(shí)鏈表中的結(jié)點(diǎn)可以

3、有如下兩種結(jié)點(diǎn)格式：datadegreechild1child2childdydatachild1child2childdx采用第一種格式6.4 樹和森林datachild1child2childdx 多重鏈表中的結(jié)點(diǎn)是同構(gòu)的，其中dx為樹的度。由于樹中很多結(jié)點(diǎn)的度小于dx，所以鏈表中有很多空鏈域，造成空間浪費(fèi)。采用第二種格式6.4 樹和森林 多重鏈表中的結(jié)點(diǎn)是不同構(gòu)的，其中dy為結(jié)點(diǎn)的度，dergee域的值同dy，此時(shí)可以節(jié)省存儲(chǔ)空間，但操作不方便。datadegreechild1child2childdy6.4 樹和森林有沒有既能節(jié)省空間又操作方便的辦法呢？另一種方式6.4 樹和森林 把每

4、個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，看成是一個(gè)線性表，且以單鏈表作存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表（葉子的孩子鏈表為空)。而n個(gè)頭指針又組成一個(gè)線性表，為便于查找，采用順序存儲(chǔ)結(jié)構(gòu)。6.4 樹和森林365120789KHGEFRDCBA0123456789DACREBFHGK樹的孩子鏈表存儲(chǔ)表示6.4 樹和森林typedef struct CTNode /孩子結(jié)點(diǎn) int child; struct CTNode *next; *ChildPtr;typedef struct /雙親結(jié)點(diǎn)結(jié)構(gòu) Elem data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;typedef

5、 struct /樹結(jié)構(gòu): CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;樹的存儲(chǔ)結(jié)構(gòu)孩子表示法6.4 樹和森林 與雙親表示法相反，孩子表示法便于涉及孩子的操作實(shí)現(xiàn)，卻不適用于Parent(T, x)操作。可根據(jù)某種需要，將二者結(jié)合起來，即帶雙親的孩子鏈表。6.4 樹和森林365120789CKHGEFRDBA0123456789DACREBFHGK466620-1044樹的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法6.4 樹和森林 或稱二叉樹表示法，或稱二叉鏈表表示法。即以二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和

6、下一個(gè)兄弟結(jié)點(diǎn)。樹的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法6.4 樹和森林REKCFABGHDDACREBFHGK樹的二叉鏈表（孩子 - 兄弟）存儲(chǔ)表示6.4 樹和森林typedef struct CSNode Elem data; struct CSNode *firstchild , *nextsibling; CSNode, *CSTree;樹的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法6.4 樹和森林 這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)各種樹的操作。首先易于實(shí)現(xiàn)找結(jié)點(diǎn)孩子等的操作。如果為每個(gè)結(jié)點(diǎn)增設(shè)一個(gè)(parent)域，則同樣能方便地實(shí)現(xiàn)Parent(T, x)操作。森林和二叉樹的轉(zhuǎn)換6.4 樹和森林1. 樹和二叉樹的對(duì)應(yīng)關(guān)系 由于

7、二叉樹和樹都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則以二叉鏈表作為媒介可導(dǎo)出樹與二叉樹之間的一個(gè)對(duì)應(yīng)關(guān)系。DCABAEBDCAEBCD對(duì)應(yīng)EDCABEECABD存儲(chǔ)解釋解釋存儲(chǔ)樹轉(zhuǎn)換為二叉樹方法6.4 樹和森林1）對(duì)每個(gè)孩子進(jìn)行從左到右的排序；2）在兄弟之間加一條連線；3）對(duì)每個(gè)結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系； 4）以根結(jié)點(diǎn)為軸心，將整個(gè)樹順時(shí)針轉(zhuǎn)45。ABCDEGHFIaABCDEGHFIbABCDEGHFIc1）在兄弟之間加一條連線；2）對(duì)每個(gè)結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系； 3）以根結(jié)點(diǎn)為軸心，將整個(gè)樹順時(shí)針轉(zhuǎn)45。ABCDEGHFIdABCDEGHFIaABCDEG

8、HFIbABCDEGHFIcABCDEGHFId1）在兄弟之間加一條連線；2）對(duì)每個(gè)結(jié)點(diǎn)，除了左孩子外，去除其與其余孩子之間的聯(lián)系； 3）以根結(jié)點(diǎn)為軸心，將整個(gè)樹順時(shí)針轉(zhuǎn)45。森林和二叉樹的轉(zhuǎn)換6.4 樹和森林2. 森林和二叉樹的對(duì)應(yīng)關(guān)系 從樹的二叉鏈表表示的定義可知，任何一棵和樹對(duì)應(yīng)的二叉樹，其右子樹必空。 若把森林中第二棵樹的根結(jié)點(diǎn)看成是第一棵樹的根結(jié)點(diǎn)的兄弟，則同樣可導(dǎo)出森林和二叉樹的對(duì)應(yīng)關(guān)系。EFADBC樹與二叉樹對(duì)應(yīng)ADBCGIHJEFGJHIADBCEFGJHI森林與二叉樹對(duì)應(yīng)樹根相連森林轉(zhuǎn)二叉樹方法1BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId森林轉(zhuǎn)二

9、叉樹方法2兄弟相連長(zhǎng)兄為父孩子靠左頭根為根 二叉樹還原為森林ADBCEFGJHI要點(diǎn)：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?森林與二叉樹對(duì)應(yīng)ADBCEFGJHIEFADBCGIHJ樹與二叉樹對(duì)應(yīng)樹和森林的遍歷6.4 樹和森林1. 樹的遍歷：有三條搜索路徑先根(序)遍歷：若樹不空，則先訪問根結(jié)點(diǎn)， 然后依次先根遍歷各棵子樹。后根(序)遍歷：若樹不空，則先依次后根遍歷 各棵子樹，然后訪問根結(jié)點(diǎn)。按層次遍歷： 若樹不空，則自上而下自左至 右訪問樹中每個(gè)結(jié)點(diǎn)。例：樹的遍歷6.4 樹和森林對(duì)樹進(jìn)行先根遍歷，獲得的先根序列是：對(duì)樹進(jìn)行后根遍歷，獲得的后根序列是：ABCDEGHFIA B E F C D G H IE F B C G H I D A森林的遍歷6.4 樹和森林先序遍歷(對(duì)森林中的每一棵樹進(jìn)行先根遍歷) 1）若森林不空，訪問森林中第一棵樹的根結(jié)點(diǎn)； 2）先序遍歷森林中第一棵樹的子樹森林； 3）先序遍歷森林中(除第一棵樹外)其余樹構(gòu)成的森林。后序遍歷(對(duì)森林中的每一棵樹進(jìn)行后根遍歷) 1）若森林不空，后序遍歷森林中第一棵樹的