目錄

一、樹

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

1.1.1雙親表示法

1.1.2孩子鏈表

1.1.3孩子兄弟表示法

1.2樹與二叉樹的轉(zhuǎn)換

1.2.1將樹轉(zhuǎn)換成二叉樹：

?1.2.2將二叉樹轉(zhuǎn)換成樹

二、森林

2.1森林與二叉樹的轉(zhuǎn)換

2.1.1將森林轉(zhuǎn)換成二叉樹

2.1.2二叉樹轉(zhuǎn)換成森林

三、樹和森林的遍歷

3.1樹的遍歷

3.2森林的遍歷

3.2.1先序遍歷

?3.2.2中序遍歷

---

一、樹

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

1.1.1雙親表示法

實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組，存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：

數(shù)據(jù)域——存放結(jié)點(diǎn)本身信息；雙親域——指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的位置

根結(jié)點(diǎn)數(shù)組下標(biāo)為0，個(gè)數(shù)n=10

（找雙親容易，找孩子難）

1.1.2孩子鏈表

孩子結(jié)點(diǎn)結(jié)構(gòu)：child next ；雙親結(jié)構(gòu)特點(diǎn)： data firstchild

（找孩子容易，找雙親難）

帶雙親的孩子鏈表

1.1.3孩子兄弟表示法

實(shí)現(xiàn)：用二叉鏈表作樹的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。

1.2樹與二叉樹的轉(zhuǎn)換

給定一棵樹，可以找到唯一的一棵二叉樹與之對(duì)應(yīng)。

1.2.1將樹轉(zhuǎn)換成二叉樹：

①加線：在兄弟之間加一條線

②抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系

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

樹變二叉樹：兄弟相連留長子

例：

?1.2.2將二叉樹轉(zhuǎn)換成樹

①加線：若p結(jié)點(diǎn)時(shí)雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來

②抹線：抹掉原二叉樹中雙親與右孩子之間的連線

③調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)

二叉樹變樹：左孩右右連雙親，去掉原來右孩線

例：

?

二、森林

2.1森林與二叉樹的轉(zhuǎn)換

2.1.1將森林轉(zhuǎn)換成二叉樹

①將各棵樹分別轉(zhuǎn)換成二叉樹

②將每棵樹的根結(jié)點(diǎn)用線相連

③以第一棵樹的根結(jié)點(diǎn)作為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)

森林變二叉樹：樹變二叉根相連

例：

2.1.2二叉樹轉(zhuǎn)換成森林

①抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿有分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹

②還原：將孤立的二叉樹還原成樹

二叉樹變森林：去掉全部右孩線，孤立二叉再還原

例：

三、樹和森林的遍歷

3.1樹的遍歷

先根遍歷：若樹不空，則先訪問根結(jié)點(diǎn)，再依次先根遍歷各棵子樹

后根遍歷：若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)

層次遍歷：若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)

例：

3.2森林的遍歷

把森林看作由三部分構(gòu)成：

①森林中第一棵樹的根結(jié)點(diǎn)

②森林中第一棵樹的子樹森林

③森林中其他樹構(gòu)成的森林

3.2.1先序遍歷

若森林不空，則：

①訪問森林中第一棵樹的根結(jié)點(diǎn)

②先序遍歷森林中第一棵樹的子樹森林

③先序遍歷森林中（除第一棵樹之外）其余樹構(gòu)成的森林

即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行先根遍歷

例：

?3.2.2中序遍歷

若森林不空，則：

①中序遍歷森林中第一棵樹的子樹森林

②訪問森林中第一棵樹的根結(jié)點(diǎn)

③中序遍歷森林中（除第一棵樹之外）其余樹構(gòu)成的森林

即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行后根遍歷

例：