樹、二叉樹與森林的相互轉(zhuǎn)換

本文只給出樹、森林與二叉樹之間的轉(zhuǎn)換方法，而詳細(xì)的證明過程不在本文討論范圍之內(nèi)。

樹 → 二叉樹

在所有兄弟結(jié)點之間加一連線。
對每個結(jié)點，除了保留與其長子的連線外，去掉該結(jié)點與其它孩子的連線。

二叉樹 → 樹

是樹轉(zhuǎn)換為二叉樹的逆過程。

加線。若某結(jié)點X的左孩子結(jié)點存在，則將這個左孩子的右孩子結(jié)點、右孩子的右孩子結(jié)點、右孩子的右孩子的右孩子結(jié)點…，都作為結(jié)點X的孩子。將結(jié)點X與這些右孩子結(jié)點用線連接起來。
去線。刪除原二叉樹中所有結(jié)點與其右孩子結(jié)點的連線。

森林 → 二叉樹

將森林中的每棵樹變?yōu)槎鏄?#xff1b;

因為轉(zhuǎn)換所得的二叉樹的根結(jié)點的右子樹均為空，故可將各二叉樹的根結(jié)點視為兄弟從左至右連在一起，就形成了一棵二叉樹。

二叉樹 → 森林

假如一棵二叉樹的根節(jié)點有右孩子，則這棵二叉樹能夠轉(zhuǎn)換為森林，否則將轉(zhuǎn)換為一棵樹。

從根節(jié)點開始，若右孩子存在，則把與右孩子結(jié)點的連線刪除。再查看分離后的二叉樹，若其根節(jié)點的右孩子存在，則連線刪除…。直到所有這些根節(jié)點與右孩子的連線都刪除為止。
將每棵分離后的二叉樹轉(zhuǎn)換為樹。

總結(jié)

以上是生活随笔為你收集整理的[数据结构]树、森林与二叉树之间的相互转换方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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