設一棵二叉樹有 n 個結點，則有 n-1 條邊(指標連線) ， 而 n 個結點共有 2n 個指標域

(Lchild 和 Rchild) ，顯然有 n+1 個空閒指標域未用。則可以利用這些空閒的指標域來存放結

點的直接前驅和直接後繼資訊。

為避免混淆,對結點結構加以改進，增加兩個標誌域，如圖所示。用這種結點結構構成

的二叉樹的儲存結構；叫做線索連結串列；指向結點前驅和後繼的指標叫做線索；

2、線索二叉樹的構建

按照某種次序遍歷，加上線索的二叉樹稱之為線索二叉樹。線索化二叉樹: 二叉樹的線

索化指的是依照某種遍歷次序使二叉樹成為線索二叉樹的過程。

線索化的過程就是在遍歷過程中修改空指標使其指向直接前驅或直接後繼的過程。

【2013 年】若 x 是後序線索二叉樹中的葉結點，且 x 存在左兄弟結點 Y，則 x 的右

線索指向的是______。

A. x 的父結點 b. 以 Y 為根的子樹的最左下結點

c. x 的左兄弟結點 Y d. 以 Y 為根的子樹的最右下結點

【2014 年】若對如下的二叉樹進行中序線索化，則結點 x 的左、右線索指向的結點分

別是______。

A．e、c b．e、a c．d、c d．b、a 考點 14：樹和二叉樹（★★★）

1、樹轉化為二叉樹

對於一般的樹，可以方便地轉換成一棵唯一的二叉樹與之對應。將樹轉換成二叉樹在“孩

子兄弟表示法”中已給出，其詳細步驟是：

1 加虛線。在樹的每層按從“左至右”的順序在兄弟結點之間加虛線相連。

2 去連線。除最左的第一個子結點外，父結點與所有其它子結點的連線都去掉。

3 旋轉。將樹順時針旋轉 450，原有的實線左斜。

4 整型。將旋轉後樹中的所有虛線改為實線，並向右斜。

這樣轉換後的二叉樹的特點是：

◆ 二叉樹的根結點沒有右子樹，只有左子樹；

◆ 左子結點仍然是原來樹中相應結點的左子結點，而所有沿右鏈往下的右子結點均是原來

樹中該結點的兄弟結點。

由於二叉樹和樹都可用二叉連結串列作為儲存結構，對比各自的結點結構可以看出，以二叉

連結串列作為媒介可以匯出樹和二叉樹之間的一個對應關係。

◆ 從物理結構來看，樹和二叉樹的二叉連結串列是相同的，只是對指標的邏輯解釋不同而已。

◆ 從樹的二叉連結串列表示的定義可知，任何一棵和樹對應的二叉樹，其右子樹一定為空。

2、二叉樹轉換成樹

對於一棵轉換後的二叉樹，如何還原成原來的樹? 其步驟是：

（1）加虛線。若某結點 i 是其父結點的左子樹的根結點，則將該結點 i 的右子結點以及沿右

子鏈不斷地搜尋所有的右子結點，將所有這些右子結點與 i 結點的父結點之間加虛線相連，

如圖(a)所示。

（2）去連線。去掉二叉樹中所有父結點與其右子結點之間的連線，如圖(b)所示。

（3）規整化。將圖中各結點按層次排列且將所有的虛線變成實線，如圖(c)所示。

3、森林轉換成二叉樹

轉換步驟：

1 將 F={t1, t2,? ,tn} 中的每棵樹轉換成二叉樹。

2 按給出的森林中樹的次序，從最後一棵二叉樹開始，每棵二叉樹作為前一棵二叉樹的

根結點的右子樹，依次類推，則第一棵樹的根結點就是轉換後生成的二叉樹的根結點，如圖

所示。

4、二叉樹轉換成森林

上述轉換規則是遞迴的，可以寫出其遞迴演算法。以下給出具體的還原步驟。

1 去連線。將二叉樹 b 的根結點與其右子結點以及沿右子結點鏈方向的所有右子結點的連

線全部去掉，得到若干棵孤立的二叉樹，每一棵就是原來森林 F 中的樹依次對應的二叉樹。 2 二叉樹的還原。將各棵孤立的二叉樹按二叉樹還原為樹的