二叉樹

• 二叉樹的存儲
  • 1 順序存儲
  • 2 二叉樹的連結存儲
    • 21 線索二叉樹
• 二叉樹的周遊
  • 1 二叉樹周遊的實作方式
• 二叉樹的實作
• 哈夫曼樹
  • 1 哈夫曼算法
• 總結

資料結構中，樹隻是一種邏輯結構，在最底層并沒有這種存儲結構的存在，隻是我們因為需要一種比較好的結構來描述我們的問題，是以樹結構就應運而生。

在樹的結構中，二叉樹是一種較為常用的樹結構，并且還很重要，幾乎我們平常程式設計時所說的樹，都是指的二叉樹。

其實家譜就是一種樹結構，他清晰的向我們傳達了家人之間的資訊。

1. 二叉樹的存儲

二叉樹的存儲也可以像矩陣一般，存儲在一維數組中，或者是通過連結清單進行存儲。存儲于數組中，需要相應的映射關系，并且還存在很多問題，如果存儲的是完全二叉樹，那麼從樹結構到數組的存儲映射關系就非常簡單了，而且浪費空間會少很多（原因後文會進行解釋）。

以連結清單形式存儲二叉樹，可以說是普遍的實作方式了。

1.1 順序存儲

順序存儲就是将一個二叉樹存儲在一個一維數組中，這種形式非常簡單，而且是最節省空間的存儲方式，多數完全二叉樹的存儲會采用這種形式實作。

這個原理非常簡單，就是對二叉樹上的結點按順序（從上到下，自左向右）進行編号，然後按照編号的順序将其按順序存儲在一維數組中，其映射關系為：

A[0]存儲二叉樹的根結點，A[i]存儲二叉樹中編号為i的結點，編号為i的結點，其左孩子如果存在，則存儲在A[2i+1]處，其右孩子如果存在，則存儲在A[2i+2]處。

如果要存儲一個非完全二叉樹，順序存儲也是可以的，但是卻并不像完全二叉樹存儲時那麼友善。

可以看到，在非完全二叉樹的順序存儲中，我們要先将非完全二叉樹補成完全二叉樹（方塊僅為了友善對其結點進行編号所假設補全的結點，實際并不存在），然後對二叉樹的結點進行編号，然後存儲到數組中，但是我們可以看到，數組中可能會空出多個位置，增大存儲開銷，帶來不必要的損失。

1.2 二叉樹的連結存儲

考慮到數組對于非完全二叉樹的存儲不是那麼友好，是以我們通常會選用連結存儲結構來進行二叉樹的存儲。

與矩陣類似，我們需要針對某個實際問題設計對應的存儲結點。

圖中∧符号表示空指針，結點中Left表示左孩子指針，Right表示右孩子指針，Data表示資料域，資料域可根據具體問題而不同。

struct Node
{
    int data;
    Node *left, *right;
    Node(int data = , Node *left = null, *right = null);
};
           

1.2.1 線索二叉樹

二叉樹的連結存儲模式下，衍生出了不少的二叉樹種類，線索二叉樹就是其中的一種。

線索二叉樹的樹結點在原有結點内容下，增加了前驅和後繼結點的指針。

這裡隻給出中序線索二叉樹的連結表示，先序與後序暫不給出（什麼是先序，中序，後序在後文會逐漸講解）。

我們從圖中可以看出，就隻是五個結點的存儲，線索二叉樹的空指針就占了很大比重，這表示存儲空間的浪費問題并沒有得到解決。

為了改進這種情況，有人提出另一種方案：

• 将原指針域Pred和Succ替換成存儲一個二進制位的域LThread和RThread
• 若結點t有左孩子，則left指向t的左孩子結點，LThread值為0；若無，則left指向t的前驅結點，LThread值為1，此時我們稱該left指針為線索。

• 若結點t有右孩子，則right指向t的右孩子結點，RThread值為0；若無，則right指向t的後繼結點，RThread值為1，此時我們稱right指針為線索。

  根據這種方案進行改進後，不僅釋放了指針域Pred和Succ所占的空間，還充分的利用了left和right指針域，減少了空指針的存在。

2. 二叉樹的周遊

二叉樹有三種周遊的形式，分别為先根序，中根序，後根序（亦稱先根周遊，中根周遊，後根周遊），其主要差別是對根的通路時機。

我們以先根序為例，進行通路根，周遊左右子樹操作的解析。

這個二叉樹周遊的結果為ABDFCE

• 先根周遊二叉樹Tree_0
  1. 通路Tree_0的根結點A
  2. 先根周遊A的左子樹（即以B為根的子樹T1）
     • 通路T1的根結點B
     • 先根周遊B的左子樹（左子樹為空，傳回B結點）
     • 先根周遊B的右子樹（右子樹不為空，則通路以D為根的子樹T2）
       • 通路T2的根結點D
       • 先根周遊D的左子樹（不為空，則通路以D為根的子樹T3）
         • 通路T3的根結點F
         • 先根周遊F的左子樹（為空，傳回F）
         • 先根周遊F的右子樹（為空，傳回F）
       • T3已周遊完成，傳回T2子樹的根結點D
     • T2子樹已周遊完成，傳回T1子樹的根結點B
     • T1子樹已周遊完成，傳回根結點A
  3. 先根周遊A的右子樹（即以C為結點的子樹T4）
     • 通路T4的跟結點C
     • 先根周遊C的左子樹（不為空，即通路以E為根結點的子樹T5）
       • 通路T5的根結點E
       • 先根周遊E的左子樹（為空，傳回E）
       • 先根周遊E的右子樹（為空，傳回E）
     • 傳回T4的根結點C
     • 先根周遊C的右子樹（為空，傳回結點A）
  4. 根結點A已周遊完成，算法結束。

中根周遊，後根周遊與先根周遊操作類似，僅對根的通路時機不同。

2.1 二叉樹周遊的實作方式

我們現在知道對二叉樹的周遊有先根序，中根序以及後根序三種，而在對先根周遊方式的算法描述，我們用到的是遞歸的思想，實作起來也比較簡單，隻需不斷的調用函數自身，等到滿足遞歸出口條件時，就可以結束算法。

void PreOrder(Node *t)const
{
    if (t != NULL)     //遞歸出口
    {
        cout<<t->GetData()<<endl;    //列印根結點值
        PreOrder(t->GetLeft());     //先根周遊左子樹
        PreOrder(t->GetRight());    //先根周遊右子樹
    }
}
           

這隻是遞歸的方式周遊，我們還有其他的非遞歸方式，如堆棧，隊列等。

在設計堆棧方式時，我們需要考慮到出棧和彈棧的恢複性，是以在堆棧上，我們為每個結點增加了一項資訊——通路計數（設為i）。表示為（結點，i）

這裡我們給出一個後根周遊的算法步驟：

• i=0，将（結點P，1）壓棧，若該結點左子樹存在，則将（左孩子（P），1）壓棧，準備周遊其左子樹。
• i=1，此時宜周遊完結點P的左子樹，将（結點P，2）壓棧，即将i設定為2，若其右子樹不為空，則将（右孩子（P），1）壓棧，準備周遊其右子樹。
• 若i=2，此時已周遊完成結點P的右子樹，通路結點P的資料域。

這段算法也是按順序重複進行的，直到滿足出口條件。

上述的是堆棧法，接下來的層次周遊，我們需要用到隊列，這個周遊方式不同于先根，中根，後根周遊的方法。

層次周遊是将樹分層，自根結點所在層開始，由0開始編号，逐層增大。

層次周遊的方法為：

• 根結點入隊
• 若隊列非空，取隊首元素通路，若其坐指針域不為空，則将其左孩子入隊；若其右指針域非空，則将其右孩子入隊；重複本步驟直到隊列空。

void LevelOrder(Node *t)const
{
    if (t == NULL) return;
    Node *p;
    AQueue q;        //假設實作了一個名為AQueue的隊列
    if (t != NULL)
        q.QInsert(t);   //根結點入隊
    while (!q.IsEmpty())
    {
        q.QDelete(p);    //QDelete中的p用來存放被删除的結點
        cout<<p->GetData()<<endl;
        if (p->GetLeft()) != NULL)
            q.QInsert(p->GetLeft());
        if (p->GetRight() != NULL)
            q.QInsert(p->GetRight());
    }
}
           

3. 二叉樹的實作

關于存儲方式和二叉樹的周遊方式就已經算是講完了，接下來要進行二叉樹的具體實作。

首先，針對實際的問題，我們需要選擇二叉樹的存儲方式，是順序存儲，還是連結存儲（但大多數情況我們都選用連結結構，故而該步驟可以省略）。

其次，針對我們選擇的存儲方式，我們進行相應的結構設計，假設選擇連結存儲。

做完這些，我們需要考慮二叉樹都需要哪些具體的操作，比如，建立，複制，增加，删除，修改，查找，周遊這些操作，都是二叉樹的基本操作。我們必須要實作。

在這裡設計一個通用化的二叉樹：

class Node
{
    private:
        char data;
        Node *left;
        Node *right;
    public:
        //構造器
        //get(),set()等函數
};
           

class BinTree
{
    private:
        Node *root;   //根結點
        int stop;      //構造二叉樹時的結束符
    public:
        BinTree(Node *t = NULL):root(t) { };
        virtual ~BinTree() { Del(root); }
        Node *Father(Node *t, Node *p);   //搜尋父結點
        Node *Find(Node *t, const char &item);    //查找二叉樹中資料域為item的值
        void DelSubTree(Node *t);   //删除結點t的子樹（左右子樹） 

        //基本操作
        void CreateBinTree(int stop = );   //預設遇到0結束建立
        Node *Create();
        Node *CopyTree(Node *t); 
        Node GetRoot() { return root; }
        void SetRoot(Node *t) { root = t; }
        int GetStop() { return stop; }
        void SetStop(int s) { stop = s; }
        int IsEmpty() { return root == NULL; }

        //周遊方式，均以參數中的結點為根
        void PreOrder(Node *t)const;    //先序周遊
        void InOrder(Node *t)const;    //中序周遊
        void PostOrder(Node *t)const;    //後根周遊
        void LevelOrder(Node *t)const;   //層次周遊
        void NorecPreOrder(Node *t)const;    //非遞歸先根周遊
        void NorecInOrder(Node *t)const;    //非遞歸中根周遊
        void NorecPostOrder(Node *t)const;  //非遞歸後根周遊
};
           

4. 哈夫曼樹

哈夫曼樹的提出是為了解決資料壓縮問題的。

為什麼要進行資料壓縮？要知道計算機誕生的年代，乃至上世紀八十年代，計算機的存儲都是以kb為機關的，哪會像現在這樣動辄以TB計算，像C語言這種面向底層的進階語言都不是很流行，彙編語言才是最流行的。是以為了避免空間的浪費，我們提出了資料壓縮。

其實放到現在也一樣，壓縮檔案可以節省不少的空間。

解決資料壓縮問題，一般都是采用不等長的二進制編碼，因為這種編碼形式，靈活可變，相比如固定長度的編碼存儲不會浪費太多空間，保證每一個字元都能以最小的二級制數來存儲。

我們知道，在一個檔案中，如txt檔案，其中存儲的字元并不是全部都不同的，至少我們可以在平時寫的文檔中找到一個出現過兩次的字元，而且常用的字元占所有字元的少數，你說6763個漢字，常用的也不過一半而已，如果使用定長的編碼格式，那麼考慮到非常用字，那麼一個檔案就會出現空間浪費，如果隻對常用字進行編碼，那麼其編碼長度就變小了，而且節省了存儲空間。

但是為了防止不定長的編碼出現相同的情況（這種情況我們稱為編碼的多義性），我們增加了字首碼來進行區分。

4.1 哈夫曼算法

哈夫曼算法其實就是求一個最優二叉樹的算法。

擴充：

最優二叉樹是以擴充二叉樹為基礎的，而擴充二叉樹簡單來說，就是為一個普通二叉樹所有結點（内結點）出現的空子樹（如果該結點的左右子樹都存在，則跳過）補充成一個葉結點（外結點）。如圖：

其中的方塊表示擴充的葉結點（即外結點）。

我們定義：外通路長度為，從根結點到每個外結點的路徑長度之和，内通路長度為，從根結點到每個内結點的路徑長度之和。

根據上圖，我們可以計算出外通路長度為2+2+3+3+2=12，内通路長度為1+0+1+2=4。

最優二叉樹則是為擴充二叉樹中擴充出來的葉結點指派（為權值），然後找到權重外通路長度最小的擴充二叉樹。

如圖則是一種最優二叉樹：

隻要找到每一個外結點對應的外通路，這兩者之和最小即可。

關于哈夫曼樹，我們針對一個具體問題來進行分析：

假設現在有7個節點，我們将每一個結點視為一顆二叉樹的根結點，由此組成一個森林，把結點在檔案中出現的次數定義為該結點的權值。

如此，我們可以進行合并，具體如下：

1. 在森林中取權值最小的兩個根結點s和n，合并成一棵二叉樹，并生成一個新結點T1，作為其二者的父結點，T1的權值是其兩個子結點的權值之和，森林中減少一棵樹。
2. 重複上述操作，直到森林中隻剩一棵樹，算法結束。

上圖就是問題所對應的哈夫曼樹了。

5. 總結

二叉樹隻是樹的一種特殊結構，且其應用是非常廣泛的，樹可以和二叉樹進行轉換，二叉樹也可以轉換成對應的樹，樹的存儲和二叉樹的存儲方式相同，隻是由于其結點可能不止左右兩個孩子，是以其存儲結構又不同，但是我們也有對應的方法去解決，如Father數組，孩子連結清單，左孩子右兄弟的連結清單結構（其實是轉化為二叉樹進行存儲的）。

至于紅黑樹，二叉查找樹這些，以後再慢慢講吧。