線索二叉樹的定義
對於n個結點的二叉樹，在二叉鏈儲存結構中有n+1個空鏈域。
利用這些空鏈域存放在某種遍歷次序下該結點的前驅結點和後繼結點的指標，這些指標稱為線索，加上線索的二叉樹稱為線索二叉樹。
線索二叉樹分為先序、中序和後序線索二叉樹。
對二叉樹以某種方式遍歷使其變為線索二叉樹的過程稱為線索化。
在原二叉鏈中增加了ltag和rtag兩個標誌域。
以中序線索二叉樹為例
線索化二叉樹
中序線索化二叉樹類ThreadTree
採用中序遍歷進行中序線索化
在整個演算法中p總是指向當前訪問的結點，pre指向其前驅結點。
遍歷線索化二叉樹
該演算法是一個非遞迴演算法，演算法的時間複雜度為O(n)，空間複雜度為O(1)
哈夫曼樹的定義
給定4個葉子結點，設其權值分別為1、3、5、7，可以構造出形狀不同的4棵二叉樹。
哈夫曼樹的構造演算法
（1）根據給定的n0個權值W=(w1，w2，…，wn0)，對應結點構成n0棵二叉樹的森林T=(T1，T2，…，Tn0)，其中每棵二叉樹Ti（1≤i≤n0）中都只有一個帶權值為wi的根結點，其左、右子樹均為空。
（2）在森林T中選取兩棵根結點權值最小的子樹作為左、右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根的權值之和。稱為合併，每合併一次T中減少一棵二叉樹。
（3）重複（2）直到T只含一棵樹為止。這棵樹便是哈夫曼樹。
每次都是兩棵子樹合併 哈夫曼樹中沒有單分支結點
W=(1，3，5，7)來構造一棵哈夫曼樹
定理6.3 對於具有n0個葉子結點的哈夫曼樹，共有2n0-1個結點。
證明：從哈夫曼樹的構造過程看出，每次合併都是將兩棵二叉樹合併為一個，所以哈夫曼樹不存在度為1的結點，即n1=0。
由二叉樹的性質1可知n0=n2+1，即n2=n0-1
則結點總數n=n0+n1+n2= n0+n2=n0+2n0-1=2n0-1。
構造哈夫曼樹中採用靜態陣列ht儲存哈夫曼樹，即每個陣列元素存放一個結點。設計哈夫曼樹中結點類如下：
哈夫曼編碼
構造一棵哈夫曼樹。
規定哈夫曼樹中的左分支為0，右分支為1。
從根結點到每個葉子結點所經過的分支對應的0和1組成的序列便為該結點對應字元的編碼。這樣的編碼稱為哈夫曼編碼。
哈夫曼編碼的實質就是使用頻率越高的採用越短的編碼。
只有ht[0..n0-1]葉子結點才對應哈夫曼編碼，用hcd[i]（0≤i≤n0-1）表示ht[i]葉子結點的哈夫曼編碼。
輸出所有葉子結點的哈夫曼編碼的演算法
輸出ht的演算法
在一組字元的哈夫曼編碼中，任一字元的哈夫曼編碼不可能是另一字元哈夫曼編碼的字首。
樹到二叉樹的轉換及還原
樹到二叉樹的轉換
一棵樹可以按照以下規則轉換為二叉樹：
加線：在各兄弟結點之間加一連線，將其隱含的"兄－弟"關係以"雙親－右孩子"關係顯示錶示出來。
抹線：對任意結點，除了其最左子樹之外，抹掉該結點與其他子樹之間的"雙親－孩子"關係。
調整：以樹的根結點作為二叉樹的根結點，將樹根與其最左子樹之間的"雙親－孩子"關係改為"雙親－左孩子"關係，且將各結點按層次排列，形成二叉樹。
· 根結點只有左子樹而沒有右子樹。
· 左分支不變（左分支為最左孩子），兄弟變成右分支（右分支實為雙親的兄弟）。
樹中分支結點個數為m，則二叉樹中無右孩子的結點個數為m+1。這裡m=4。
一棵由樹轉換的二叉樹還原為樹
一棵二叉樹（由一棵樹轉換的）可以按照以下規則還原為一棵樹：
· 加線：在各結點的雙親與該結點右鏈上的每個結點之間加一連線，以"雙親－孩子"關係顯示錶示出來。
· 抹線：抹掉二叉樹中所有雙親結點與其右孩子之間的"雙親－右孩子"關係。
· 調整：以二叉樹的根結點作為樹的根結點，將各結點按層次排列，形成樹。
· 根結點不變。
· 左分支不變（左分支為最左孩子），右分支變成兄弟。
森林到二叉樹的轉換及還原
森林轉換為二叉樹
含有兩棵或兩棵以上樹的森林可以按照以下規則轉換為二叉樹：
· 轉換：將森林中的每一棵樹轉換成二叉樹，設轉換成的二叉樹為bt1、bt2、…、btm。
· 連線：將各棵轉換後的二叉樹的根結點相連。
· 調整：以bt1的根結點作為整個二叉樹的根結點，將bt2的根結點作為bt1的根結點的右孩子，將bt3的根結點作為bt2的根結點的右孩子，…，如此這樣得到一棵二叉樹，即為該森林轉換得到的二叉樹。
二叉樹還原為森林
當一棵二叉樹的根結點有m-1個右下孩子，這樣還原的森林中有m棵樹。這樣的二叉樹可以按照以下規則還原其相應的森林：
· 抹線：抹掉二叉樹根結點右鏈上所有結點之間的"雙親－右孩子"關係，分成若干個以右鏈上的結點為根結點的二叉樹，設這些二叉樹為bt1、bt2、…、btm。
· 轉換：分別將bt1、bt2、…、btm二叉樹各自還原成一棵樹。
· 調整：將轉換好的樹構成森林。