樹、森林和二叉樹的轉換

1. 樹轉化為二叉樹

   （1）加線：在兄弟結點之間加一條連線

   （2）去線：樹中的每個結點，隻保留它第一個孩子結點的連線，删除與其他孩子之間的連線。

   （3）層次調整：以樹的根節點為軸心，将整棵樹順時針旋轉一定角度，使其結構層次分明。（第一個孩子結點變為左孩子，兄弟結點變右孩子）

   

2. 森林轉化為二叉樹

   （1）把每一棵樹轉化為二叉樹

   （2）第一棵二叉樹不動。從第二棵二叉樹開始，把後一棵二叉樹的根結點作為前一個二叉樹的右孩子，用線連起來。

   

3. 二叉樹轉化為樹

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

（2）去線：删除原有的孩子結點的右結點的連線。

（3）層次調整。

4. ## 二叉樹轉化為森林

如果一棵二叉樹的根結點有右孩子，則這棵二叉樹能轉換為森林，否則轉換為一棵樹。

（1）從根結點開始，右孩子存在，則把與右孩子結點的連線删除。再檢視分離後的二叉樹。若其根結點的右孩子存在，則連線删除，直到所有的根結點與右孩子的連線都删除為止。

（2）将每一棵分離後的二叉樹轉換為樹。

出自《大話資料結構》