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

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

2、位置域 PTNode;typedef struct /樹(shù)結(jié)構(gòu) PTNode nodesMAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法6.4 樹(shù)和森林 這種存儲(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àn)無(wú)雙親的結(jié)點(diǎn)時(shí)，便找到了樹(shù)的根。但在這種表示方式中，求結(jié)點(diǎn)的孩子時(shí)需遍歷整個(gè)結(jié)構(gòu)。樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子表示法6.4 樹(shù)和森林 由于樹(shù)中每個(gè)結(jié)點(diǎn)可能有多棵子樹(shù)，則考慮用多重鏈表，即結(jié)點(diǎn)有多個(gè)指針域，其中每個(gè)指針指向一棵子樹(shù)的根結(jié)點(diǎn)，此時(shí)鏈表中的結(jié)點(diǎn)可以

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

4、個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，看成是一個(gè)線性表，且以單鏈表作存儲(chǔ)結(jié)構(gòu)，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表（葉子的孩子鏈表為空)。而n個(gè)頭指針又組成一個(gè)線性表，為便于查找，采用順序存儲(chǔ)結(jié)構(gòu)。6.4 樹(shù)和森林365120789KHGEFRDCBA0123456789DACREBFHGK樹(shù)的孩子鏈表存儲(chǔ)表示6.4 樹(shù)和森林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 /樹(shù)結(jié)構(gòu): CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子表示法6.4 樹(shù)和森林 與雙親表示法相反，孩子表示法便于涉及孩子的操作實(shí)現(xiàn)，卻不適用于Parent(T, x)操作。可根據(jù)某種需要，將二者結(jié)合起來(lái)，即帶雙親的孩子鏈表。6.4 樹(shù)和森林365120789CKHGEFRDBA0123456789DACREBFHGK466620-1044樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法6.4 樹(shù)和森林 或稱(chēng)二叉樹(shù)表示法，或稱(chēng)二叉鏈表表示法。即以二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和

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

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

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

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