樹、森林與二叉樹的轉換

　　樹或森林與二叉樹之間有一個自然的一一對應關系任何一個森林或一棵樹可惟一地對應到一棵二叉樹反之任何一棵二叉樹也能惟一地對應到一個森林或一棵樹

．樹森林到二叉樹的轉換
（）將樹轉換為二叉樹
　　樹中每個結點最多只有一個最左邊的孩子(長子)和一個右鄰的兄弟按照這種關系很自然地就能將樹轉換成相應的二叉樹
　　①在所有兄弟結點之間加一連線
　　②對每個結點除了保留與其長子的連線外去掉該結點與其它孩子的連線
【例】下面(a)圖所示的樹可轉換為(c)圖所示的二叉樹具體轉換過程可【參見動畫演示】

　注意
　　由於樹根沒有兄弟故樹轉化為二叉樹後二叉樹的根結點的右子樹必為空

（）將一個森林轉換為二叉樹
　　具體方法是
　　① 將森林中的每棵樹變為二叉樹
　　② 因為轉換所得的二叉樹的根結點的右子樹均為空故可將各二叉樹的根結點視為兄弟從左至右連在一起就形成了一棵二叉樹
【例】下圖中左邊包含三棵樹的森林可轉換為右邊的二叉樹

         
       具體轉換過程可【參見動畫演示】

二叉樹到樹森林的轉換
　　把二叉樹轉換到樹和森林自然的方式是若結點x是雙親y的左孩子則把x的右孩子右孩子的右孩子…都與y用連線連起來最後去掉所有雙親到右孩子的連線
【例】下圖的森林就是由例中二叉樹轉換成的

 
　　具體轉換過程可【參見動畫演示】

From:http://tw.wingwit.com/Article/program/sjjg/201311/23267.html