一、樹的概念
一個結點有一個前驅和多個後繼結點，這種資料結構是樹形結構
1、樹的定義
樹(Tree)是n個結點的集合，集合中有一個稱為根(root)的特殊節點，在根節點分布着一些互相不相交的集合，每個集合又是一個樹，這些樹稱為根節點的子樹
(1)空集合也是樹
(2)單個結點是一棵樹，樹根就是該結點本身
(3)若某樹有多個結點，則每個節點都可以看成是根結點
(4)在一棵樹中，有且僅有一個結點沒有前驅，這個結點就是根節點
(5)除根結點外，其餘每個結點有且僅有一個前驅，如圖B的前驅為A，不能有其它前驅
(6)每個結點可以有任意多個後繼例如：A有B、C、D三個後繼
2、樹的相關術語
(1)父節點、子節點、兄弟結點
每個節點的子樹的根稱為該結點的兒子(子結點)，相應的，該結點被稱為子結點的父親(父節點)，具有同一父結點的的結點稱為兄弟結點，例如結點A是B、C、D的父結點，相應的，結點B、C、D就是結點A的子結點，而結點B、C、D之間是兄弟結點。對這種層次關系進行擴充，可得出祖先結點和子孫結點等關系
(2)結點的度
一個結點的子樹的數量稱為該結點的 "度"。例如：結點A有3個子樹，是以結點A的"度"是3；而結點B、C、D的"度"分别為1、2、2
(3)樹的度
一棵樹的度是指該樹中結點的最大度數，上圖樹的度為3(結點A的度為3)
4)葉結點和分支結點
樹中度為零的結點稱為葉節點或終端節點。樹中度不為零的結點稱為分支結點或非終端節點。節點E、J、K、L、M、N為葉節點
(5)節點的層數
樹是一種層次結構，每個節點都是處在一定的層次上
(6)樹的深度
一棵樹中節點的最大層數稱為樹的深度。例如，圖中所示的樹的深度為4
(7)有序樹和無序樹
若樹中各節點的子樹(兄弟節點)是按一定次序從左向右安排的，稱為有序樹，否則稱為無序樹
(8)森林
森林是m(m>=0)課互不相交的樹的集合。如果删去圖中所示樹的根節點A，留下的3棵子樹就構成了一個森林
3、樹的表示
樹的表示方法很多，常用的方法是用括号：先将根節點放入一對圓括号中，然後把它的子樹由左至右的順序放入括号中，而對子樹也采用同樣的方法處理；同層子樹與它的根節點用圓括号括起來，同層子樹之間用逗号隔開，最後用閉括号括起來
( A( B(E) ) ,(C(F(J)),(G (K,L))),(D(H),(I(M,N))))
二、二叉樹的概念
在樹的應用中，二叉樹特别重要，這是因為處理樹的許多算法應用到二叉樹時變得非常簡單，而任意的樹又可以友善的轉換為對應的二叉樹。是以，隻需要定義二叉樹的算法，然後将其它樹轉換為二叉樹，即可友善的對所有樹進行操作
1、二叉樹的定義
一個二叉樹是n個結點的集合，此集合要麼是空集，要麼是由一個根節點加上分别稱為左子樹和右子樹的兩個互不相交的二叉樹
二叉樹任意節點最多隻能有兩個子節點；如果隻有一個子節點，可以是左子樹也可以是右子樹。是以，二叉樹有5種基本形态：
(1)空
沒有任何節點
(2)僅有根節點
隻有根節點，沒有子節點
(3)僅有左子樹
(4)僅有右子樹
(5)左右子樹都有
2、二叉樹和樹的兩個主要差别如下：
(1)樹中節點的最大度數沒有限制，而二叉樹節點的最大度數為2
(2)樹的節點無左右之分，而二叉樹的節點有左右之分，因為二叉樹有左右之分，是以二叉樹是有序樹
3、特殊的二叉樹
(1)滿二叉樹
在二叉樹中，除最下一層的葉子節點外，每層的節點都有2個子節點，就構成了滿二叉樹
(2)完全二叉樹
除二叉樹最後一層外，其它各層的節點數都達到最大個數，且最後一層從左向右的葉節點連續存在，隻缺右側若幹節點，就是完全二叉樹
4、二叉樹的性質
(1)在二叉樹中，第i層的節點總數最多為
個
(2)深度為k的二叉樹最多有
個節點(k>=1)
(3)對于一個二叉樹，如果其葉節點數為n0，而度為2的節點總數為n2，則n0=n2+1
(4)具有n個節點的完全二叉樹的深度k為：k = [log2n ] + 1
(5)有n個節點的完全二叉樹各節點如果用順序方式存儲，對任意節點i，有如下關系：
如果i!=1，則其父節點的編号為i/2
如果2*i<=n，則其左子樹根節點編号為2*i；若2*I > n，則無左子樹
如果2*i + 1 <=n，則其右子樹根節點編号為2*i + 1；若2*i +1 > n，則無右子樹
三、二叉樹的存儲
二叉樹通常可采用順序存儲結構和鍊式存儲結構
1、順序存儲結構
與線性表的順序存儲類似，二叉樹的順序存儲結構一般也由一個一維數組來構成，二叉樹上的節點按某種規定的次序逐個儲存到數組的各個單元中
二叉樹順序存儲結構的資料定義如下：
#define MAXSIZE 100 //最大節點數
typedef int DATA ; //元素類型
typedef DATA seqBinTree[MAXSIZE ];
seqBinTree SBT; //定義儲存二叉樹組
對于一個完全二叉樹，若用順序存儲，各節點之間具有對應關系。如下：
對于一個完全二叉樹，若用順序存儲，各節點之間具有對應關系。例如，對于節點i，其父節點為i/2(若商不整數，則進行取整)，而其左子節點的編号為2*i，右子節點的編号為2*i+1
對于節點E，由于存儲在數組第5個位置，可推算出其父節點的序号為5/2 = 2，即其父節點為節點B。而如果節點E有子節點，則其左子節點的序号為2*5 =10，即其左子節點為J。同樣，如果有右子節點，則其右子節點的序号為11，即節點K
如果順序存儲的二叉樹不是完全二叉樹，由于節點和數組中的序号沒了對應關系，就比較麻煩了。為了能使節點與數組序号有對應關系，一般采用的方法是；将非完全二叉樹轉換為完全二叉樹，将左側缺少的節點虛設為無資料的節點(這裡用“#”)
将此圖所示的完全二叉樹按順序儲存到一維數組中，得到下圖所示：
但是，儲存A---H共7個節點占用15個存儲空間，造成存儲空間的浪費。是以，對于二叉樹的順序存儲，一般是适用于一些特殊情況(如儲存完全二叉樹)
2、鍊式存儲結構
由于二叉樹的順序存儲結構會造成空間浪費，是以，大多數情況下，二叉樹都采用鍊式存儲結構。使用鍊式存儲結構非常符合二叉樹的邏輯結構，一個節點可以由節點元素和兩個分别指向左、右子樹的指針組成
四、操作二叉樹
1、定義二叉樹鍊式結構
#include
#include
#define QUEUE_MAXSIZE 50;//隊列大小
typedef char DATA
typedef struct chainTree{
DATA data; //元素資料
struct chainTree *left;//左子樹指針
struct chainTree *right;//右子樹指針
} chainBinTree;
2、初始化二叉樹
chainBinTree * binTreeInit(chainBinTree * node){//初始化二叉樹根節點
if(node ! = NULL)
{
return node;
}else{
return NULL;
}
}
3、添加節點到二叉樹
bt 為父節點，node為子節點，n=1表示添加左子樹，n=2表示添加右子樹
int binTreeAddNode(chainBinTree *bt,chainBinTre *node,int n)
{
if(bt == NULL){
printf("父節點不存在，請先設定父節點！");
return 0;
}
switch(n){
case 1:
if(bt->left)//左子樹不為空
{
printf("左子樹不能為空");
return 0;
}else{
bt->left = node;
}
break;
case 2:
if(bt->right)//右子樹不為空
{
printf("右子樹不能為空");
return 0;
}else{
bt->right = node;
}
break;
default:
printf("參數錯誤");
return 0;
}
return 1;
}
4、擷取二叉樹左右的子樹
chainBinTree *binTreeLeft(chainBinTree *bt)
{
if(bt){
return bt->left;
}else{
return NULL;
}
}
chainBinTree *binTreeRight(chainBinTree *bt)
{
if(bt){
return bt->right;
}else{
return NULL;
}
}
5、擷取二叉樹狀态
檢查二叉樹是否為空
int binTreeIsEmpty(chainBinTree *bt){
if(bt)
return 0;
else
return 1;
}
求二叉樹的深度
int binTreeDeph(chainBinTree *bt){
int dep1,dep2;
if(bt==NULL){
return 0;//空樹深度為0
}else{
//左子樹深度(遞歸調用)
dep1 = binTreeDeph(bt->left)
//右子樹深度(遞歸調用)
dep2 = binTreeDeph(bt->right)
if(dep1 > dep2){
return dep1 + 1;
}else{
return dep2 + 1;
}
}
}
6、在二叉樹中查找
chainBinTree *binTreeFind(chainBinTree *bt,DATA data){
chainBinTree *p;
if(bt == NULL){
return NULL;
}else{
if(b->data == data){
return bt;
}else{
if(p = binTreeFind(bt->left,data))
return p;
else if(p = binTreeFind(bt->right,data))
return p;
else
return NULL;
}
}
}
該函數有2個參數，bt是需要查找的二叉樹的根節點，data為需要查找的節點資料
7、清空二叉樹
在向二叉樹添加節點時，每個節點都由malloc函數申請配置設定記憶體，是以需要清空二叉樹則必須使用free函數來釋放節點所占的記憶體。清空二叉樹的操作就是通過遞歸調用，對二叉樹進行周遊，釋放各個節點所占的記憶體
105 void binTreeClear(chainBinTree *bt)
106 {
107 if(bt)
108 {
109 binTreeClear(bt->left);//清空左子樹
110 binTreeClear(bt->right);//清空了右子樹
111 free(bt);//釋放目前節點所占記憶體
112 bt = NULL;
113 }
114 return;
115 }
該函數有一個參數bt，就是需要清空二叉樹的根節點。第107行進行判斷，若目前節點bt不為空(表示還占用了系統記憶體)，這時，不能直接使用free釋放目前節點所占記憶體，因為該節點還可能有子樹，如果直接将該節點所占記憶體釋放，則無法再連結到其左右子樹，造成記憶體被無效占用。是以，這裡首先需要執行第109、110行遞歸調用目前函數，用來清空目前節點的左子樹和右子樹，最後在執行第111行釋放目前節點所占記憶體
五、周遊二叉樹
由于二叉樹是非線性結構，那麼将資料按二叉樹結構儲存時，怎樣才能在所有節點中查找所需要的資料呢？這就需要定義一種算法，将二叉樹的各個節點轉換成一個線性序列來表示，以友善對各節點資料的檢索，這就是二叉樹的周遊
周遊是對樹的一種最基本的運算，所謂周遊二叉樹，就是按一定的規則和順序走遍二叉樹的所有節點，使每一個節點都被通路一次，而且隻能被通路一次
如下圖所示具有左右子樹的二叉樹，其中D表示根節點，L表示左子樹，R表示右子樹，對其進行周遊有3種方式：
1、先序周遊(DLR)：稱為先根次序周遊，即先通路根節點，再按先序周遊左子樹，最後按先序周遊右子樹
2、中序周遊(LDR)：稱為中根次序周遊，即先按中序周遊左子樹，再通路根節點，最後按中序周遊右子樹
3、後序周遊(LRD)：稱為後根次序周遊，即先按後序周遊左子樹，再按後序周遊右子樹，最後通路根節點
先序周遊
1、算法的僞代碼描述
void binTree_DLR(binTree)
{
if(二叉樹不為空)
{
通路根節點；
binTree_DLR(left); //先序周遊左子樹
binTree_DLR(right);//先序周遊右子樹
}
}
2、代碼實作
void preOrder(binTree root){
if(root != NULL ){
printf("%d",root->data);//通路根結點
preOrder(root->lchild); //先序周遊根節點的左子樹
preOrder(root->rchild); //先序周遊根節點的右子樹
}
}
中序周遊
void inOrder(binTree root){
if(root !=NULL ){
inOrder(root->lchild);//中序周遊根結點的左子樹
printf("%d",root->data);//通路根節點
inOrder(root->rchild);//中序周遊根結點的右子樹
}
}
後序周遊
void postOrder(binTree root){
if(root !=NULL ){
postOrder (root->lchild);//中序周遊根結點的左子樹
postOrder (root->rchild);//中序周遊根結點的右子樹
printf("%d",root->data);//通路根節點
}
}
周遊二叉樹的基本操作就是通路節點，不論按照哪種次序周遊，對于含有n個節點的二叉樹，周遊算法的時間複雜度都為O(n)。因為在周遊的過程中，每進行一次遞歸調用，都将函數的“活動記錄”壓入棧中，是以，棧的最大長度恰為樹的高度。是以，在最壞情況下，二叉樹有n個節點且高度為n的單枝樹，周遊算法的空間複雜度也為O(n)
借助一個棧，可将二叉樹的遞歸算法轉換為非遞歸算法。下面給出中序周遊的非遞歸算法
int inOrderTraverse(binTree root){
initStack(st);//建立個空棧
p = root;//p指向樹根節點
while(p!=NULL || !initStack(st)){
if(p!=NULL){//不是空樹
push(st,p);//根節點指針進棧
p = p->lchild;//進入根的左子樹
}else{
q = top(st); pop(st);//棧頂元素出棧
printf("%d",q->data);//通路根節點
p = q->rchild;//進入根的右子樹
}
}
}
對于二叉樹，還有層次周遊。設二叉樹的根節點所在層樹為1,層序周遊就是從樹的根節點出發，首先通路第1層的樹根節點，然後從左到右依次通路第2層上的節點，其次是第3層上的節點，以此類推，自上而下，自左至右逐層通路樹中各節點的過程就是層序周遊
上圖中按照層次周遊的結果為：ABCDEFGHIJKL
//按照層次周遊
public static void binTree_level(TreeNode root){
int QUEUE_MAXSIZE = 6;
TreeNode p;
TreeNode q[]=new TreeNode[QUEUE_MAXSIZE];//定義個順序隊列
int head = 0;//定義首序号
int tail = 0;//定義尾序号
if(root!=null){
//計算循環隊列隊尾序号
tail = (tail + 1)%QUEUE_MAXSIZE;
q[tail] = root;
}
//隊列不為空，進行循環
while(head!=tail){
//計算循環隊列隊首序号
head = (head + 1)%QUEUE_MAXSIZE;
//擷取隊首元素
p = q[head];
//若節點有左子樹，則左子樹進隊
if(p.left!=null){
tail = (tail+1)%QUEUE_MAXSIZE;
q[tail] = p.left;
}
//若節點有右子樹，則右子樹進隊
if(p.right!=null){
tail = (tail+1)%QUEUE_MAXSIZE;
q[tail] = p.right;
}
}
for(TreeNode obj:q){
if(obj!=null){
System.out.println(obj.value);
}
}
}
六、線索二叉樹
對于二叉樹進行周遊得到的節點序列，可以将周遊的結果看成是一個線性表。在該線性表中，除了第1個節點外，每個節點都有(且僅有)一個前驅；除了最後一個節點外，每個節點都有(且僅有)一個後繼。例如：下列二叉樹經過中序周遊後結果為
B F D A C G E H
線索二叉樹的表示
當以二叉樹連結清單形式來儲存二叉樹時，隻能找到節點的左右子樹資訊，而不能直接得到節點的前驅和後繼(隻有通過周遊，在動态過程中才能查到前驅和後繼的資訊)。如果增加前驅和後繼的指針那麼增加了存儲的開銷。其實由二叉樹性質可知，對于一顆具有n個節點的二叉樹，對應的二叉樹連結清單中共有2n個指針域，其中n-1個用于指向除根節點外的n-1個節點，另外n+1個指針域為空。可以利用二叉樹中的這些空指針域來存放節點的前驅和後繼。将每個節點中為空的左指針或右指針分别用于指向節點的前驅和後繼，即可得到線索二叉樹
在一個線索二叉樹中，為了差別每個節點的左、右指針域所存放的是子樹指針，還是線索，必須在節點結構中增加兩個标志域：一個是左線索标志域lflag，另一個是右線索标志域eflag。若某個标志為1，則表示對應的指針域為線索，否則，對應的指針域為子樹指針
七、哈夫曼樹
1. 哈夫曼樹的構造
給定N個權值分别為w1, w2, ..., Wn的節點。構造哈夫曼樹的算法描述如下：
1)将這N個結點分别作為N棵樹僅含一個結點的二叉樹，構成森林F
2)構造一個新節點，并從F中選取兩棵根結點權值最小的樹作為新節點的左、右子樹， 并且将新節點的權值置為左、右子樹上根結點的權
值之和
3)從F中删除剛才選出的兩棵樹，同時将新得到的樹加入F中
4)重複步驟2和3，直至F中隻剩下一棵樹為止
2. 哈夫曼編碼
哈夫曼編碼是一種被廣泛應用而且非常有效的資料壓縮編碼，它是可變長度編碼。可變長編碼即可以對待處理字元串中不同字元使用不等長的二進制位表示，可變長編碼比固定長度編碼好很多，可以對頻率高的字元賦予短編碼，而對頻率較低的字元則賦予較長一些的編碼，進而可以使平均編碼長度減短，起到壓縮資料的效果。
哈夫曼編碼是字首編碼。如果沒有一個編碼是另一個編碼的字首，則稱這樣的編碼為字首編碼。對字首編碼的解碼也是相對簡單的，因為沒有一個碼是另一個編碼的字首，是以可以識别出第一個編碼，将它翻譯為原碼，再對餘下的編碼檔案重複同樣操作。
哈夫曼編碼首先要構造一棵哈夫曼樹，首先，将每個出現的字元當做一個獨立的結點，其權值作為它出現的頻度(或次數)，然後構造哈夫曼樹。顯然所有字元節點均出現在葉子結點中。我們可以将字元的編碼解釋為從根至該字元路徑上标記的序列，其中标記為0表示"轉向左孩子"，标記為1表示為"轉向右孩子"。 如下圖，矩形方塊表示字元及出現的次數
是以，這棵哈夫曼樹的WPL為：
WPL = 1*45 + 3 * (13+12+16) + 4 * (5+9) = 224
哈夫曼樹練習
1、設哈夫曼樹中的節點總數為49，若用二叉連結清單作為存儲結構，則該哈夫曼樹中總共有個空指針域？
2、對于n(n大于等于2)個權值均不相同的字元構成哈夫曼樹，以下叙述正确的是()
A、樹中一定沒有度為1的節點
B、該樹一定是一顆完全二叉樹
C、樹中任一非葉節點的權值一定不小于子孫中任一節點的權值
D、樹中兩個權值最小的節點一定是兄弟節點(假設這兩個節點恰好有兩個)
3、若以(4、5、6、7、8)作為葉節點的權值構造哈夫曼樹，則其帶權路徑長度是多少？
4、某段文本中各個字母出現的頻率是a為4、b為3、o為12、h為7，i為10，使用哈夫曼編碼，則可能的編碼是
A、 a(001) 、b(000)、h(01)、i(10)、o(11)
B、 a(000) 、b(0001)、h(001)、o(01)、i(1)
C、 a(000) 、b(001)、h(01)、i(10)、o(00)
D、 a(0000) 、b(0001)、h(001)、o(000)、i(1)
5、用二進制來編碼字元串“xyzwxyxx”，需要能夠根據編碼解碼回原來的字元串，則最少需要()長度的二進制字元串
A、12 B、14 C、15 D、18 E、24