【概述】

從樹的孩子兄弟表示法和二叉樹的二叉鏈表表示可以看出，樹的孩子兄弟表示法實(shí)質(zhì)上是二叉樹的二叉鏈表存儲形式，第一個(gè)孩子指針和右兄弟指針分別相當(dāng)于二叉鏈表的左孩子指針和右孩子指針。

因此，從物理結(jié)構(gòu)上看，樹的孩子兄弟表示法和二叉樹的二叉鏈表是相同的，只是解釋不同。

以二叉鏈表為媒介，可導(dǎo)出樹與二叉樹的對應(yīng)關(guān)系，即給出一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)，這樣樹的操作實(shí)現(xiàn)就可借助二叉樹存儲，利用二叉樹上的操作來實(shí)現(xiàn)。

【樹轉(zhuǎn)二叉樹】

將一棵樹轉(zhuǎn)為二叉樹的方法是：

加線：樹中所有相鄰兄弟結(jié)點(diǎn)間加一條線

去線：對樹中的每個(gè)結(jié)點(diǎn)，只保留他與第一個(gè)子結(jié)點(diǎn)的連線，刪除與其他子結(jié)點(diǎn)的連線

層次調(diào)整：以根結(jié)點(diǎn)為軸心，將樹順時(shí)針旋轉(zhuǎn)一定角度，使之層次分明

根據(jù)樹與二叉樹的轉(zhuǎn)換關(guān)系以及二叉樹的遍歷操作可知：

• 樹的前序遍歷 <----> 二叉樹的前序遍歷
• 樹的后序遍歷 <----> 二叉樹的中序遍歷

【森林轉(zhuǎn)二叉樹】

森林是若干棵樹的集合，將森林中的每棵樹轉(zhuǎn)為二叉樹，再將每棵樹的根節(jié)點(diǎn)視為兄弟，這樣森林就轉(zhuǎn)成了二叉樹。

將一棵樹轉(zhuǎn)為二叉樹的方法是：

轉(zhuǎn)樹：將森林中的每棵樹轉(zhuǎn)換成二叉樹

連接：從第二棵樹二叉樹開始，依次將后一棵二叉樹的根節(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子

【二叉樹轉(zhuǎn)樹或森林】

樹和森林都能轉(zhuǎn)成二叉樹，二者的不同是樹轉(zhuǎn)成的二叉樹其根結(jié)點(diǎn)無右子樹，森林轉(zhuǎn)成的二叉樹其根結(jié)點(diǎn)有右子樹。

顯然，這一轉(zhuǎn)換過程是可逆的，即根據(jù)二叉樹的根結(jié)點(diǎn)有無右子樹，將其還原成樹或森林。

將一棵二叉樹轉(zhuǎn)成樹或森林的方法是：

加線：若某結(jié)點(diǎn) x 是其雙親 y 的左孩子，則把結(jié)點(diǎn) x 的右孩子、右孩子的右孩子、……，都與結(jié)點(diǎn) y 用線連起來

去線：刪去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線

層次調(diào)整：整理 1、2 步得到的樹或森林，使之層次分明

【森林的遍歷】

森林有兩種遍歷方法：

• 前序遍歷：前序遍歷森林中的每一棵樹
• 后序遍歷：后序遍歷森林中的每一棵樹

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 二叉树 —— 树、森林、二叉树的转换的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。