樹,二叉樹,森林的轉(zhuǎn)化

對(duì)于一般樹，樹中孩子的次序并不重要，只要雙親與孩子的關(guān)系正確即可。但在二叉樹中，左、右孩子的次序是嚴(yán)格區(qū)分的。所以在討論二叉樹與一般樹之間的轉(zhuǎn)換時(shí)，為了不引起混淆，約定按樹上現(xiàn)有結(jié)點(diǎn)次序進(jìn)行轉(zhuǎn)換。這里研究二叉樹與一般樹之間的轉(zhuǎn)換，可以了解兩者之間的內(nèi)在本質(zhì)聯(lián)系，同時(shí)在研究解決一般樹的問題時(shí)，有時(shí)可以將其轉(zhuǎn)換為二叉樹問題來解決。樹或森林與二叉樹之間有一個(gè)自然的一一對(duì)應(yīng)關(guān)系。任何一個(gè)森林或一棵樹可唯一地對(duì)應(yīng)到一棵二叉樹。反之，任何一棵二叉樹也能唯一地對(duì)應(yīng)到一個(gè)森林或一棵樹。樹、森林到二叉樹的轉(zhuǎn)換1）將樹轉(zhuǎn)換為二叉樹樹中每個(gè)結(jié)點(diǎn)最多只有一個(gè)最左邊的孩子（長子）和一個(gè)右鄰的兄弟。按照這種關(guān)系很自然地就能將樹轉(zhuǎn)換成相應(yīng)的二叉樹。將一般樹轉(zhuǎn)化為二叉樹的思路，主要根據(jù)樹的孩子-兄弟存儲(chǔ)方式而來，步驟是:加線：在各兄弟結(jié)點(diǎn)之間用虛線相連?？衫斫鉃槊總€(gè)結(jié)點(diǎn)的兄弟指針指向它的一個(gè)兄弟。抹線：對(duì)每個(gè)結(jié)點(diǎn)僅保留它與其最左一個(gè)孩子的連線，抹去該結(jié)點(diǎn)與其他孩子之間的連線?？衫斫鉃槊總€(gè)結(jié)點(diǎn)僅有一個(gè)孩子指針，讓它指向自己的左孩子。旋轉(zhuǎn)：把虛線改為實(shí)線從水平方向向下旋轉(zhuǎn)45°C,成右斜下方向。原樹中實(shí)線成左斜下方向。這樣就樹的形狀成呈現(xiàn)出一棵二叉樹。下圖所示的樹可轉(zhuǎn)換為對(duì)應(yīng)的二叉樹。(a)W (b)加線(虛線表示要?jiǎng)h除的線)(c)抹線(c)抹線(d)旋轉(zhuǎn)2）將一個(gè)森林轉(zhuǎn)換為二叉樹森林是樹的有限集合。由上節(jié)可知一棵樹可以轉(zhuǎn)換為二叉樹（該二叉樹沒有右子樹），一個(gè)森林就可以轉(zhuǎn)換為二叉樹（沒有右子樹）的森林。將森林轉(zhuǎn)換為二叉樹的一般步驟為:將森林中每棵子樹轉(zhuǎn)換成相應(yīng)的二叉樹，形成由若干二叉樹組成的森林。按森林中原有樹的先后次序依次將后邊一棵二叉樹作為前邊一棵二叉樹根結(jié)點(diǎn)的右子樹，這樣整個(gè)森林就生成了一棵二叉樹，實(shí)際上第一棵樹的根結(jié)點(diǎn)便是生成后的二叉樹的根結(jié)點(diǎn)。下圖是將一個(gè)森林轉(zhuǎn)化為一棵二叉樹的示例圖a包含三棵樹的森林可轉(zhuǎn)換為圖c的二叉樹。下圖中,圖a包含三棵樹的森林可轉(zhuǎn)換為圖c的二叉樹。下圖中,（C）森林轉(zhuǎn)化得到的匚叉樹二叉樹到樹、森林的轉(zhuǎn)換1）二叉樹轉(zhuǎn)換為一般樹此時(shí)的二叉樹必須是由某一樹（一般樹）轉(zhuǎn)換而來的沒有右子樹的二叉樹（若二叉樹有右子樹則說明此二叉樹可以拆分成森林）。并非隨便一棵二叉樹都能還原成一般樹。其還原過程也分為三步：加線：若某結(jié)點(diǎn)i是雙親結(jié)點(diǎn)的左孩子，則將該結(jié)點(diǎn)i的右孩子以及當(dāng)且僅當(dāng)連續(xù)地沿著右孩子的右鏈不斷搜索到所有右孩子，都分別與結(jié)點(diǎn)i的雙親結(jié)點(diǎn)用虛線連接。抹線：把原二叉樹中所有雙親結(jié)點(diǎn)與其右孩子的連線抹去。這里的右孩子實(shí)質(zhì)上是原一般樹中結(jié)點(diǎn)的兄弟，抹去的連線是兄弟間的關(guān)系。進(jìn)行整理：把虛線改為實(shí)線，把結(jié)點(diǎn)按層次排列。下圖把二叉樹還原為一般樹：2）二叉樹轉(zhuǎn)換為森林將一棵二叉樹轉(zhuǎn)化成森林，可按如下步驟進(jìn)行:①抹線：將二叉樹根結(jié)點(diǎn)與其右孩子之間的連線，以及沿著此右孩子的右鏈連續(xù)不繼搜索到的右孩子間的連線抹掉。這樣就得到了若干棵根結(jié)點(diǎn)沒有右子樹的二叉樹。②將得到的這些二叉樹用前述方法分別轉(zhuǎn)化成一般樹。整理第②步得到的樹，使之規(guī)范，這樣得到森林?？偨Y(jié)根據(jù)樹與二叉樹的轉(zhuǎn)換關(guān)系以及二叉樹的遍歷定義可以推知，a?樹的先序遍歷與其轉(zhuǎn)換的相應(yīng)的二叉樹的先序遍歷的結(jié)果序列相同；b?樹的后序遍歷與其轉(zhuǎn)換的二叉樹的中序遍歷的結(jié)果序列相同；c,樹的層序遍歷與其轉(zhuǎn)換的二叉樹的后序遍歷的結(jié)果序列相同。由森林與二叉樹的轉(zhuǎn)換