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

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

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

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

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

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

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

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

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

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