2.8　樹和森林

2.8.1　普通樹轉(zhuǎn)化為二叉樹

普通樹可以轉(zhuǎn)化為二叉樹，轉(zhuǎn)化步驟如下：

（1）在普通樹的兄弟結(jié)點(diǎn)之間加一條線，使兄弟結(jié)點(diǎn)互連，如圖2-115所示。

（2）對于樹中的每個結(jié)點(diǎn)，只保留其與第一孩子結(jié)點(diǎn)的連線，刪除結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)之間的連線，如圖2-116所示。

（3）調(diào)整樹的層次結(jié)構(gòu)。以樹的根結(jié)點(diǎn)為軸心，將整棵樹旋轉(zhuǎn)一定的角度，使樹結(jié)構(gòu)層次分明，如圖2-117所示。

2.8.2　森林轉(zhuǎn)化為二叉樹

森林由多棵樹組成。森林可以轉(zhuǎn)化為二叉樹，轉(zhuǎn)化步驟如下：

（1）將森林中的每棵樹轉(zhuǎn)化為二叉樹，如圖2-118所示。

（2）保持第一棵不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹的根結(jié)點(diǎn)的右孩子，用線連接起來，如圖2-119所示。

（3）調(diào)整樹的層次結(jié)構(gòu)。以樹的根結(jié)點(diǎn)為軸心，將整棵樹旋轉(zhuǎn)一定的角度，使樹結(jié)構(gòu)層次分明，如圖2-120所示。

2.8.3　樹的遍歷

樹的遍歷分為以下兩種：

（1）先根遍歷。先訪問樹的根結(jié)點(diǎn)，再依次先根遍歷根的每棵子樹。

（2）后根遍歷。先依次遍歷每棵子樹，再訪問根結(jié)點(diǎn)。

圖2-121所示的樹，先根遍歷的結(jié)果為ABEFCGDHIJ，后根遍歷的結(jié)果為EFBGCHIJDA。

2.8.4　森林的遍歷

森林的遍歷也分為先跟遍歷和后根遍歷，其實(shí)就是按照樹的先根遍歷和后根遍歷依次訪問森林的每一棵樹。

在圖2-122所示的森林中，森林的先根遍歷結(jié)果為ABCDEFGHI，森林的后根遍歷結(jié)果為BCDAFEHIG。

2.8.5　樹和森林常見面試考點(diǎn)

（1）普通樹與二叉樹間的轉(zhuǎn)換。

（2）森林與二叉樹間的轉(zhuǎn)換。

（3）樹的遍歷方式。

（4）森林的遍歷方式。