傳送門

樹、森林與二叉樹的轉換

1、樹轉換為二叉樹

由于二叉樹是有序的，為了避免混淆，對于無序樹，我們約定樹中的每個結點的孩子結點按從左到右的順序進行編號。

將樹轉換成二叉樹的步驟是：

• 加線。就是在所有兄弟結點之間加一條連線；
• 抹線。就是對樹中的每個結點，只保留他與第一個孩子結點之間的連線，刪除它與其它孩子結點之間的連線；
• 旋轉。就是以樹的根結點為軸心，將整棵樹順時針旋轉一定角度，使之結構層次分明（使每個結點的第一個孩子結點連線位于左孩子指針位置，使每個結點的右兄弟結點連線位于右孩子指針位置）。

?

樹轉換為二叉樹的過程示意圖

2、森林轉換為二叉樹

森林是由若干棵樹組成，可以將森林中的每棵樹的根結點看作是兄弟，由于每棵樹都可以轉換為二叉樹，所以森林也可以轉換為二叉樹。

將森林轉換為二叉樹的步驟是：

• 先把每棵樹轉換為二叉樹；
• 第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹的根結點的右孩子結點，用線連接起來。當所有的二叉樹連接起來后得到的二叉樹就是由森林轉換得到的二叉樹。

?

森林轉換為二叉樹的轉換過程示意圖

3、二叉樹轉換為樹

二叉樹轉換為樹是樹轉換為二叉樹的逆過程，其步驟是：

• 若某結點的左孩子結點存在，將左孩子結點的右孩子結點、右孩子結點的右孩子結點……都作為該結點的孩子結點，將該結點與這些右孩子結點用線連接起來；
• 刪除原二叉樹中所有結點與其右孩子結點的連線；
• 整理（1）和（2）兩步得到的樹，使之結構層次分明。

二叉樹轉換為樹的過程示意圖

4、二叉樹轉換為森林

二叉樹轉換為森林比較簡單，其步驟如下：

• 先把每個結點與右孩子結點的連線刪除，得到分離的二叉樹；
• 把分離后的每棵二叉樹轉換為樹；
• 整理第（2）步得到的樹，使之規范，這樣得到森林。

根據樹與二叉樹的轉換關系以及二叉樹的遍歷定義可以推知，樹的先序遍歷與其轉換的相應的二叉樹的先序遍歷的結果序列相同；樹的后序遍歷與其轉換的二叉樹的中序遍歷的結果序列相同；樹的層序遍歷與其轉換的二叉樹的后序遍歷的結果序列相同。由森林與二叉樹的轉換關系以及森林與二叉樹的遍歷定義可知，森林的先序遍歷和中序遍歷與所轉換得到的二叉樹的先序遍歷和中序遍歷的結果序列相同。

轉載于:https://www.cnblogs.com/ZhaoxiCheung/p/6142726.html

總結

以上是生活随笔為你收集整理的（转载）树、森林与二叉树的转换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。