設一棵二叉樹有 n 個結點，則有 n1 條邊(指針連線) ， 而 n 個結點共有 2n 個指針域
    (cd 和 rcd) ，顯然有 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 二叉樹的還原。將各棵孤立的二叉樹按二叉樹還原為樹的方法還原成一般的樹。
    5、樹的遍曆
    由樹結構的定義可知，樹的遍曆有二種方法。
    (1) 先序遍曆：先訪問根結點，然後依次先序遍曆完每棵子樹。如圖，先序遍曆的次序是：
    abcdefgijhk
    (2) 後序遍曆：先依次後序遍曆完每棵子樹，然後訪問根結點。如圖，後序遍曆的次序是：
    cdbfijgheka
    樹的先序遍曆實質上與將樹轉換成二叉樹後對二叉樹的先序遍曆相同。
    樹的後序遍曆實質上與將樹轉換成二叉樹後對二叉樹的中序遍曆相同
    【2019 年】若將一棵樹 t 轉化為對應的二叉樹 bt，則下列對 bt 的遍曆中，其遍曆序列
    本小章還未完，請點擊下一頁繼續閱讀後麵精彩內容！
    與 t 的後根遍曆序列相同的是）
    a.先序遍曆 b.中序遍曆 c.後序遍曆 d.按層遍曆
    【2020 年】已知森林 f 及與之對應的二叉樹 t，若 f 的先根遍曆序列是 a, b, c, d, e, f，中
    根遍曆序列是 b, a, d, f, e, c 則 t 的後根遍曆序列是：
    a、b, a, d, f, e, c b、b, d, f, e, c, a c、b, f, e, d, c, a d、f, e, d, c, b, a 考點 15：哈夫曼樹(★★★)    1 結點路徑：從樹中一個結點到另一個結點的之間的分支構成這兩個結點之間的路徑。
    2 路徑長度：結點路徑上的分支數目稱為路徑長度。
    3 結點的帶權路徑長度：從該結點的到樹的根結點之間的路徑長度與結點的權(值)的乘積
    4權(值)：各種開銷、代價、頻度等的抽象稱呼。
    5樹的路徑長度：從樹根到每一個結點的路徑長度之和。    1 根據 n 個權值1, 2, ? ,n，構造成 n 棵二叉樹的集合 f=t1, t2, ? ,tn，其中每棵二
    叉樹隻有一個權值為 i 的根結點，沒有左、右子樹；
    2 在 f 中選取兩棵根結點權值最小的樹作為左、右子樹構造一棵新的二叉樹，且新的二
    叉樹根結點權值為其左、右子樹根結點的權值之和；
    3 在 f 中刪除這兩棵樹，同時將新得到的樹加入 f 中；
    4 重複2、3，直到 f 隻含一顆樹為止。    的左子樹，權值大的二叉樹作為新構造的二叉樹的右子樹；在取值相等時，深度小的二叉樹
    作為新構造的二叉樹的左子樹，深度大的二叉樹作為新構造的二叉樹的右子樹。
    圖是權值集合 =8, 3, 4, 6, 5, 5構造
    是： p=6x2+3x3+4x3+8x2+5x3+5x3 =79。    由於每個字符都是葉子結點，不可能出現在根結點到其它字符結點的路徑上，所以一個    若字符集 c=a, b, c, d, e, f所對應的權值集合為 =8, 3, 4, 6, 5, 5，如圖所示，則字符    以字符集 c 作為葉子結點，次數或頻度集  作為結點的權值來構造 huffan 樹。規定    從根結點到每個葉子結點所經曆的路徑分支上的“0”或“1”所組成的字符串，為該結    喜歡離語請大家收藏：()離語書更新速度全網最快。