1 樹的存儲(chǔ)結(jié)構(gòu)

1）雙親表示法 用一組連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)樹的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附加一個(gè)指數(shù)器（整數(shù)域），用以指示雙親結(jié)點(diǎn)的位置（下標(biāo)值）。

typedef int ElemType;
typedef struct PTNode {
    ElemType data;
    int parent;
} PTNode;
typedef struct {
    PTNode nodes[MAXSIZE];
    int root;//根結(jié)點(diǎn)位置
    int num;//結(jié)點(diǎn)數(shù)
} Ptree;

利用了任一結(jié)點(diǎn)的父結(jié)點(diǎn)唯一的性質(zhì)。可以方便地直接找到任一結(jié)點(diǎn)的父結(jié)點(diǎn)，求結(jié)點(diǎn)的子結(jié)點(diǎn)時(shí)需要掃描整個(gè)數(shù)組。

2）孩子鏈表表示法 樹中每個(gè)結(jié)點(diǎn)有多個(gè)指針域，每個(gè)指針指向其一顆子樹的根結(jié)點(diǎn)。有兩種結(jié)點(diǎn)結(jié)構(gòu)
①定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)
指針域的數(shù)目就是樹的度。其特點(diǎn)是：鏈表結(jié)構(gòu)簡(jiǎn)單，但指針域的浪費(fèi)明顯。在一棵有n個(gè)結(jié)點(diǎn)，度為k的樹中必有n(k-1)+1個(gè)空指針域。
②不定長(zhǎng)結(jié)點(diǎn)結(jié)構(gòu)
樹中每個(gè)結(jié)點(diǎn)的指針域數(shù)量不同，是該結(jié)點(diǎn)的度。沒(méi)有多余的指針域，操作不便。
③復(fù)合鏈表結(jié)構(gòu)
對(duì)于樹中的每個(gè)結(jié)點(diǎn)，其孩子結(jié)點(diǎn)用頭結(jié)點(diǎn)的單鏈表表示。
n個(gè)結(jié)點(diǎn)的樹有n個(gè)（孩子）單鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空），而n個(gè)頭結(jié)點(diǎn)又組成一個(gè)線性表且以順序存儲(chǔ)結(jié)構(gòu)表示。

typedef struct listNode {
    int childNo;//孩子結(jié)點(diǎn)編號(hào)
    struct listNode *next;
} CTNode;//表結(jié)點(diǎn)結(jié)構(gòu)
typedef struct {
    ElemType data;
    CTNode *firstChild;
} HNode;//頭結(jié)點(diǎn)結(jié)構(gòu)
typedef struct {
    HNode nodes[MAXSIZE];
    int root;//根結(jié)點(diǎn)位置
    int num;//結(jié)點(diǎn)數(shù)
} CLinkList;//頭結(jié)點(diǎn)結(jié)構(gòu)

3）孩子兄弟表示法 這是一種常用的存儲(chǔ)結(jié)構(gòu)。在樹中，每個(gè)結(jié)點(diǎn)除其信息域外，再增加兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)的指針。 兩個(gè)指針域:分別指向結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。

typedef int ElemType;
typedef struct CSnode {
    ElemType data;
    struct CSnode *firstchild, *nextsibing;//第一個(gè)孩子結(jié)點(diǎn)，親兄弟結(jié)點(diǎn)
} CSNode;

孩子兄弟表示法

2 森林和二叉樹的轉(zhuǎn)換

由于二叉樹和樹都可用二叉鏈表（孩子兄弟表示法）作為存儲(chǔ)結(jié)構(gòu)，對(duì)比各自的結(jié)點(diǎn)結(jié)構(gòu)可以看出，以二叉鏈表作為媒介可以導(dǎo)出樹和二叉樹之間的一個(gè)對(duì)應(yīng)關(guān)系。
從物理結(jié)構(gòu)來(lái)看，樹和二叉樹的二叉鏈表是相同的，只是對(duì)指針的邏輯解釋不同而 已。
從樹的二叉鏈表表示的定義可知，任何一棵和樹對(duì)應(yīng)的二叉樹，其右子樹一定為空。(因?yàn)楦Y(jié)點(diǎn)只有孩子，沒(méi)有兄弟)

1)樹轉(zhuǎn)換為二叉樹
對(duì)于一棵無(wú)序樹，樹中結(jié)點(diǎn)的各孩子的次序是無(wú)關(guān)緊要的，而二叉樹中結(jié)點(diǎn)的左、右孩
子結(jié)點(diǎn)是有區(qū)別的。為避免發(fā)生混淆，約定樹中每一個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)按從左到右的次序順 序編號(hào)。將一棵樹轉(zhuǎn)換為二叉樹的方法是:
(1)樹中所有相鄰兄弟之間加一條連線;
(2)對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線;
(3)以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之結(jié)構(gòu)層次分明?？梢?證明，樹作這樣的轉(zhuǎn)換所構(gòu)成的二叉樹是唯一的。 由轉(zhuǎn)換過(guò)程可以看出，在二叉樹中，左 分支上的各結(jié)點(diǎn)在原來(lái)的樹中是父子關(guān)系，而右分支上的各結(jié)點(diǎn)在原來(lái)的樹中是兄弟關(guān)系。
由于樹的根結(jié)點(diǎn)沒(méi)有兄弟，所以變換后的二叉樹的根結(jié)點(diǎn)的右孩子必為空。
事實(shí)上，一棵樹采用孩子兄弟表示法所建立的存儲(chǔ)結(jié)構(gòu)與它所對(duì)應(yīng)的二叉樹的二叉鏈表
存儲(chǔ)結(jié)構(gòu)是完全相同的。
舉例:將下列樹轉(zhuǎn)換成二叉樹。

旋轉(zhuǎn):以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn) 45°

2)二叉樹轉(zhuǎn)換為樹的過(guò)程
(1) 加虛線。若某結(jié)點(diǎn)i是其父結(jié)點(diǎn)的左子樹的根結(jié)點(diǎn)，則將該結(jié)點(diǎn)i的右子結(jié)點(diǎn)以及 沿右子鏈不斷地搜索所有的右子結(jié)點(diǎn)，將所有這些右子結(jié)點(diǎn)與 i 結(jié)點(diǎn)的父結(jié)點(diǎn)之間加虛線相 連。
(2) 去連線。去掉二叉樹中所有父結(jié)點(diǎn)與其右子結(jié)點(diǎn)之間的連線。
(3) 規(guī)整化。將圖中各結(jié)點(diǎn)按層次排列且將所有的虛線變成實(shí)線。

3)森林轉(zhuǎn)換為二叉樹
由森林的概念可知，森林是若干棵樹的集合，只要將森林中各棵樹的根視為兄弟，每棵樹又可以用二叉樹表示，這樣，森林也同樣可以用二叉樹表示。

4)二叉樹還原為森林
(1) 去連線。將二叉樹的根結(jié)點(diǎn)與其右子結(jié)點(diǎn)以及沿右子結(jié)點(diǎn)鏈方向的所有右子結(jié) 點(diǎn)的連線全部去掉，得到若干棵孤立的二叉樹，每一棵就是原來(lái)森林 F中的樹依次對(duì)應(yīng)的二叉樹。
(2)將各棵孤立的二叉樹按二叉樹還原為樹的方法還原成一般的樹。

image.png

3 樹和森林的遍歷

1.樹的遍歷
(1)先序遍歷：先訪問(wèn)根結(jié)點(diǎn)，然后依次先序遍歷完每棵子樹。
(2)后序遍歷：先依次后序遍歷完每棵子樹，然后訪問(wèn)根結(jié)點(diǎn)。
由于不分左右子樹，所以無(wú)中序遍歷。

總結(jié)：對(duì)于一顆樹的先序遍歷等于轉(zhuǎn)變?yōu)槎鏄浜蟮南刃虮闅v；
對(duì)于一棵樹的后序遍歷等于轉(zhuǎn)變?yōu)槎鏄浜蟮闹行虮闅v。

2.森林的遍歷
(1)先序遍歷：按先序遍歷樹的方式依次遍歷森林中的每棵樹。
(2)中序遍歷：按后序遍歷樹的方式依次遍歷森林中的每棵樹。（注意定義為中序遍歷）