二叉樹每個結點最多有兩個孩子，其餘結構和樹的結構一樣。 1. 二叉樹特點二叉樹的特點有：每個結點最多有兩棵子樹，所以二叉樹中不存在度大於2的結點。左子樹和右子樹是有順序的，次序不能任意顛倒。即使樹中某結點只有一棵子樹，也要區分它是左子樹還是右子樹。二叉樹有五種基本形態：空二叉樹；只有 ...

二叉樹

每個結點最多有兩個孩子，其餘結構和樹的結構一樣。

1. 二叉樹特點

二叉樹的特點有：

每個結點最多有兩棵子樹，所以二叉樹中不存在度大於2的結點。
左子樹和右子樹是有順序的，次序不能任意顛倒。
即使樹中某結點只有一棵子樹，也要區分它是左子樹還是右子樹。

二叉樹有五種基本形態：

空二叉樹；
只有一個根節點；
根節點只有左子樹；
根節點只有右子樹；
根節點既有左子樹又有右子樹。

2. 特殊二叉樹

斜樹。所有結點只有左子樹（或右子樹）的二叉樹稱為左斜樹（右斜樹）。
滿二叉樹。所有結點（除了葉子結點）都存在左子樹和右子樹，且所有葉子結點均在同一層上。

滿二叉樹的特點有：
- 葉子只能出現在最下一層；
- 非葉子結點的度一定為2；
- 在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子數最多。
完全二叉樹。對一棵具有n個結點的二叉樹按層序編號，如果編號為i(1≤i≤n)的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中位置完全相同，這個二叉樹為完全二叉樹。

圖

完全二叉樹的特點：
- 葉子結點只能出現最下兩層；
- 最下層的葉子一定集中在左部連續位置；
- 倒數二層，若有葉子結點，一定都在右部連續位置；
- 如果結點度為1，則該結點只有左孩子，即不存在只有右子樹的情況；
- 同樣結點數的二叉樹，完全二叉樹的深度最小。

2. 二叉樹的性質

在二叉樹的第i層上至多有\(2^{i-1} (i≥1)\)個結點。
深度為k的二叉樹至多有\(2^k-1 (k≥1)\)個結點。
對任何一棵二叉樹T，如果其終端結點數為\(n_0\)，度為2的結點數為\(n_2\)，則\(n_0=n_2+1\)。
具有n個結點的完全二叉樹的深度為\([log_2n]+1\)([x]表示不大於x的最大整數)。
對於具有n個結點的完全二叉樹，其結點按照層序編號，對任意結點\(i (1≤i≤n)\)有：
- 如果\(i=1\)，則結點i是二叉樹的根，無雙親；如果\(i≥1\)，則其雙親結點為\([i/2]\)。
- 如果\(2i>n\)，則結點i無左孩子（結點i為葉子結點）；否則其左孩子是結點2i。
- 如果\(2i+1>n\)，則結點i無右孩子；否則其右孩子是結點\(2i+1\)。

3.二叉樹遍歷

遍歷二叉樹的方法：

先序遍歷
- 首先對根節點進行訪問
- 然後訪問左子樹
- 最後訪問右子樹 DLR模式
2.中序遍歷
- 首先訪問左子樹
- 後訪問根節點
- 最後訪問右子樹 LDR模式
後序遍歷
- 首先訪問左子樹
- 然後訪問右子樹
- 最後訪問根節點 LRD模式

    //先序遍歷DLR
    void PreorderTraverse(BTNode<T> *p) //p為二叉樹的根節點,以下同是
    {
        if (p != NULL)
        {
            this->Visit(p);
            this->PreorderTraverse(p->lchild);
            this->PreorderTraverse(p->rchild);
        }
    }
    //中序遍歷LDR
    void InorderTraverse(BTNode<T> *p)
    {
        if (p != NULL)
        {
            this->InorderTraverse(p->lchild);
            this->Visit(p);
            this->InorderTraverse(p->rchild);
        }
    }
    //後序遍歷LRD
    void Postordertraverse(BTNode<T> *p)
    {
        if (p != NULL)
        {
            this->Postordertraverse(p->lchild);
            this->Postordertraverse(p->rchild);
            this->Visit();
        }
    }

4. 二叉樹遍歷的應用

    //統計葉子結點的數目
    int GetNumOfLeaf(BTNode<T> *p)
    {
        int number = 0;
        if (p == NULL)
            number = 0;
        else if (p->lchild == NULL && p->rchild == NULL)
            number = 1;
        else
            number = this->GetNumOfLeaf(p->lchild) + this->GetNumOfLeaf(p->rchild);
        return number;
    }
    //計算二叉樹的高度
    int GetHeight(BTNode<T> *p)
    {
        int height = 0;
        if (p == NULL)
            height = 0;
        else if (p->lchild == NULL && p->rchild == NULL)
            height = 1;
        else
        {
            int lheight = this->GetHeight(p->lchild) + 1;
            int rheight = this->GetHeight(p->rchild) + 1;
            height = lheight > rheight ? lheight : rheight;
        }
        return height;
    }

5. 中序線索化二叉樹

原理：

為了節省資源空間，將空閑的指針域給利用起來，將此指針域設為該結點的前驅或後繼指針

如果該結點的左指針域為空，則將此指針域指向該結點的前驅；
如果該結點的右指針域為空，則將此指針域指向該結點的後繼；
為了辨別該結點的左右指針域的指向，需要在結點中加入兩個布爾變數Ltag和Rtag。如果Ltag=0或Rtag=0則表明該結點的左或右孩子存在；否則，指向前驅或後繼指針。

實現：

首先遍歷整個二叉樹BinTree，先序，中序，後序都可

if(BinTree!=NULL)
{
    Inordertraverse(BinTree->lchild);
    dosomething;
    Inordertraverse(BinTree->rchild);
}

判斷當前結點的左孩子是否存在，若存在則讓BinTree->Ltag=0；

否則BinTree->Ltag=1;BinTree->lchild=pre;(pre為當前結點的前驅結點，就是遍歷的上一個結點)

3. 判斷前驅結點pre的右孩子是否存在，若存在則讓BinTree->Rtag=0;

否則pre->Rtag=1;pre->rchild=BinTree;

4. 令前驅結點pre始終保持在當前結點的上一個結點，即:pre=BinTree;

代碼實現：

if(BinTree->lchild==NULL)
{
    BinTree->Ltag=1;
    BinTree->lchild=pre;
}
if(pre!=NULL&&pre->rchild==NULL)
{
    pre->Rtag=1;
    pre->rchild=BinTree;
}
pre=BinTree;

中序線索二叉樹查找某個結點p的前驅結點pre

根據中序遍歷方法LDR可知，結點p的前驅結點應是p的左子樹；
如果該結點的左孩子標誌點p->Ltag=1;則該結點的前驅為pre=p->lchild;
如果該結點的左孩子存在即p->Ltag=0;

根據中序遍歷的定義可知，結點p的前驅結點應是p的左子樹的“最下右孩子”;

用代碼可表示為：

q=p->lchild;
while(q->Rtag==0)
{
    q=q->rchild;
}
pre=q;

中序線索二叉樹查找某個結點p的後繼結點next，方法原理同上。

中序線索二叉樹的插入和刪除操作

插入操作：

向二叉樹中結點p的右孩子插入結點r，即p->rchild=r;

1. 首先遍歷二叉樹，找到結點p

- 如果結點p的右孩子不存在，即p->Rtag=1;
- 則p的後繼變為r，r的後繼變為p原來的後繼p->rchild，r的前驅為p
- 即：r->Ltag=1;r->lchild=p;r->Rtag=1;r->rchild=p->rchild;p->rchild=r;註意順序不能變
- 如果結點p的右孩子存在，即p->Rtag=0;
- 則將結點r變為p結點的右孩子，原來p的右孩子變為r的右孩子
- 則p的後繼將變為r，p為r的前驅
- r的後繼變為右子樹“最下端左孩子”

代碼實現：

if(p->Rtag==1)
{
    BTNode<T> *r=new BTNode<T>(Data:data,Ltag:1,Rtag:1,lchild:p,rchild:p->rchild);
    p->rchild=r;
    p->Rtag=0;
}
else
{
    BTNode<T> *r=new BTNode<T>(Data:data,Ltag:1,Rtag:0,lchild:p,rchild:p->rchild);
    p->rchild=r;
    BTNode<T> *q=r->rchild;
    while(q->Ltag==0)
    {
        q=q->lchild;
    }
    q->lchild=r;
}

刪除操作和插入操作類似相同，方法和原理同上。

6. 哈夫曼樹

哈夫曼樹是指帶權路徑最小的二叉樹。

給定一定的帶權葉子結點，構造哈夫曼樹：

1. 在這些結點中尋找兩個權最小的葉子結點，這兩個結點與\(N_1\)結點組成一棵樹，\(N_1\)結點的權變為兩個結點的和；

2. 將\(N_1\)結點和其它葉子結點放在一起，在其中找到兩個權最小的樹，組成一棵新樹；

3. 註意在組成新樹時，將權相對較小的值作為左孩子；

4. 以此類推，重覆上述的步驟，最終將得到哈夫曼樹。

根據以上的構造可以得到，哈夫曼樹只有度為2的結點和葉子結點，故當哈夫曼樹有n個葉子結點時，其總結點數為2n-1。

哈夫曼樹存儲結構：

權重雙親左孩子右孩子

葉子結點的左孩子和右孩子均為空。

哈夫曼樹的應用：

哈夫曼編碼：首碼編碼，首碼編碼容易區分，不易相重；縮短編碼長度，便於傳輸常用於壓縮文件編碼