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

樹轉(zhuǎn)換為二叉樹

（1）加線。在所有兄弟結(jié)點之間加一條連線。

（2）去線。樹中的每個結(jié)點，只保留它與第一個孩子結(jié)點的連線，刪除它與其它孩子結(jié)點之間的連線。

（3）層次調(diào)整。以樹的根節(jié)點為軸心，將整棵樹順時針旋轉(zhuǎn)一定角度，使之結(jié)構(gòu)層次分明。（注意第一個孩子是結(jié)點的左孩子，兄弟轉(zhuǎn)換過來的孩子是結(jié)點的右孩子）

???????????????????????

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

（1）把每棵樹轉(zhuǎn)換為二叉樹。

（2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹的根結(jié)點的右孩子，用線連接起來。

?

二叉樹轉(zhuǎn)換為樹

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

（1）加線。若某結(jié)點X的左孩子結(jié)點存在，則將這個左孩子的右孩子結(jié)點、右孩子的右孩子結(jié)點、右孩子的右孩子的右孩子結(jié)點…，都作為結(jié)點X的孩子。將結(jié)點X與這些右孩子結(jié)點用線連接起來。

（2）去線。刪除原二叉樹中所有結(jié)點與其右孩子結(jié)點的連線。

（3）層次調(diào)整。

?

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

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

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

（2）將每棵分離后的二叉樹轉(zhuǎn)換為樹。

?

《大話數(shù)據(jù)結(jié)構(gòu)》

?

轉(zhuǎn)載于:https://www.cnblogs.com/kexianting/p/8612268.html

總結(jié)

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

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