樹的存儲結構
樹有三種表示法，分别是
雙親表示法：
每個結點（根結點外）中除了資料域還有一個指針域儲存其雙親結點的位置。
孩子表示法：
每個結點除了資料域還有多個指針域存放其子樹根結點的位置
孩子兄弟法：
每個結點除了資料域外，左指針用來存儲子樹根節點的位置，右指針存儲兄弟結點的位置。
樹與二叉樹與森林的轉換
轉換使用的是孩子兄弟法，即左指針連接配接孩子，右指針連接配接兄弟。
假設有如下的森林
A與E、I在同一層次，可視為兄弟根結點，B、C、D是兄弟結點
則第一棵樹按左子樹右兄弟的規律可轉換為如下二叉樹
三棵樹按此規律可轉換為下圖的二叉樹
A、E、I也連接配接起來，則該森林轉換為一棵二叉樹：
将二叉樹轉換為森林或樹跟上述類似，二叉樹的左結點是森林的子樹，右結點是森林的兄弟逆推即可。
哈夫曼樹
也叫最優樹，有下列概念：
路徑長度：一個結點到另一個結點的路徑數目。
樹的路徑長度：樹到一個結點的路徑長度，若到L層，則長度是L - 1
樹的帶權路徑長度：所有結點到根的路徑帶權值之和，記作WPL。
**建構哈夫曼樹：**選取兩棵根結點權值最小的子樹構造二叉樹，權值重的子樹放在右邊，則這顆二叉樹根結點的權值就是左右子樹權值之和。注意：相同權值的哈夫曼樹不唯一。
例：将要插入的結點按順序排好
取出25和34，25為左子樹，34為右子樹：
根結點的權值是子樹和，即59，比38大，則38放在左邊
以此類推，得到下列哈夫曼樹A
該樹的 WPL = 561 + 492 + 413 + 384 + (25+34)*5 = 585
類似還可以得到如下哈夫曼樹B
WPL = 56*1 + （41+49+38）*3 + （25+34）*4 = 676，比A的要大，WPL小的越優。
哈夫曼編碼是最優字首編碼：一串字元中，任何一個字元的編碼都不是其他字元編碼的字首。
比如有三個字元串，{ 01,001,010 }就不是字首編碼, '01001001’具有二義性，即存在歧義，例如可以看為010 01 001或者01 001 001.