樹(shù)、森林和二叉樹(shù)之間的轉(zhuǎn)換（左兄弟右孩子）

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

1. 加線

在所有兄弟結(jié)點(diǎn)之間加一條連線。

2. 去線

樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)的連線，刪除它與其它孩子結(jié)點(diǎn)之間的連線。

3. 層次調(diào)整

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

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

1. 把每棵樹(shù)轉(zhuǎn)換為二叉樹(shù)。

2. 第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)的根結(jié)點(diǎn)的右孩子，用線連接起來(lái)。

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

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

1. 加線

若某結(jié)點(diǎn)X的左孩子結(jié)點(diǎn)存在，則將這個(gè)左孩子的右孩子結(jié)點(diǎn)、右孩子的右孩子結(jié)點(diǎn)、右孩子的右孩子的右孩子結(jié)點(diǎn)…，都作為結(jié)點(diǎn)X的孩子。將結(jié)點(diǎn)X與這些右孩子結(jié)點(diǎn)用線連接起來(lái)。

2. 去線

刪除原二叉樹(shù)中所有結(jié)點(diǎn)與其右孩子結(jié)點(diǎn)的連線。

3. 層次調(diào)整。

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

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

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

2.?將每棵分離后的二叉樹(shù)轉(zhuǎn)換為樹(shù)。