二叉樹

二叉樹是每個節(jié)點最多有兩個子樹的樹結構副砍。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）辕羽。

相關術語：

樹的結點：包含一個數(shù)據(jù)元素及若干指向子樹的分支算吩；

孩子結點：結點的子樹的根稱為該結點的孩子猫十；

雙親結點：B 結點是A 結點的孩子琢锋，則A結點是B 結點的雙親站粟；

兄弟結點：同一雙親的孩子結點搔涝；

堂兄弟結點：同一層上不同雙親的結點厨喂；

祖先結點: 從根到該結點的所經分支上的所有結點

子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫

層：根結點的層定義為1，根的孩子為第二層結點庄呈，依此類推杯聚；

樹的深度：樹中最大的層

結點的度：結點子樹的個數(shù)

樹的度： 樹中最大的結點度。

葉子結點：也叫終端結點抒痒，是度為 0 的結點幌绍；

分枝結點：度不為0的結點；

有序樹：子樹有序的樹故响，如：二叉樹傀广；

無序樹：不考慮子樹的順序；

公式

(1) 在二叉樹中彩届，第i層的結點總數(shù)不超過2^(i-1)伪冰；

(2) 深度為h的二叉樹最多有2^h -1個結點(h>=1)，最少有h個結點樟蠕；

(3) 對于任意一棵二叉樹贮聂，如果其葉結點數(shù)為N0，而度數(shù)為2的結點總數(shù)為N2寨辩，

則N0=N2+1吓懈；

(4) 具有n個結點的完全二叉樹的深度為 log2n下取整 +1

(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關系：

若I為結點編號則 如果I>1靡狞，則其父結點的編號為I/2下取整耻警；

如果2I<=N，則其左兒子的編號為2I甸怕；若2*I>N甘穿，則無左兒子；

如果2I+1<=N梢杭，則其右兒子的結點編號為2I+1温兼；若2*I+1>N，則無右兒子武契。

完全二叉樹

葉節(jié)點只能出現(xiàn)在最下層和次下層募判，并且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹缸榛。

若設二叉樹的深度為h，除第 h 層外兰伤，其它各層 (1～h-1) 的結點數(shù)都達到最大個數(shù)内颗，第 h 層所有的結點都連續(xù)集中在最左邊。

葉子結點只可能在最大的兩層上出現(xiàn),對任意結點敦腔，若其右分支下的子孫最大層次為L均澳，則其左分支下的子孫的最大層次必為L 或 L+1， 即度為1的點只有1個或0個符衔。

滿二叉樹是特殊的完全二叉樹找前，完全二叉樹不一定是滿二叉樹。

滿二叉樹：

除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹判族。

如果一個二叉樹的層數(shù)為K躺盛，且結點總數(shù)是(2^k) -1 ，則它就是滿二叉樹形帮。

平衡二叉樹：

平衡二叉樹又被稱為AVL樹槽惫，它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1辩撑，并且左右兩個子樹都是一棵平衡二叉樹界斜。

遍歷順序：

設L、D合冀、R分別表示遍歷左子樹各薇、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷）君躺，LDR（稱為中根次序遍歷）峭判，LRD （稱為后根次序遍歷）。

• 先序遍歷

首先訪問根棕叫，再先序遍歷左（右）子樹林螃，最后先序遍歷右（左）子樹，C語言代碼如下：

void XXBL( tree* root ){

  輸出節(jié)點;

  if( root->lchild!=NULL )

    XXBL( root->lchild );

  if( root->rchild!=NULL )

    XXBL( root->rchild );

}

• 中序遍歷

遞歸實現(xiàn)
首先中序遍歷左（右）子樹谍珊，再訪問根治宣，最后中序遍歷右（左）子樹急侥，C語言代碼如下

void ZXBL( tree* root )

{

   if( root->lchild!=NULL )

    ZXBL( root->lchild );

   輸出節(jié)點;

  if( root->rchild!=NULL )

    ZXBL( root->rchild );

}

非遞歸實現(xiàn)

根據(jù)中序遍歷的順序砌滞，對于任一結點，優(yōu)先訪問其左孩子坏怪，而左孩子結點又可以看做一根結點贝润，然后繼續(xù)訪問其左孩子結點，直到遇到左孩子結點為空的結點才進行訪問铝宵，然后按相同的規(guī)則訪問其右子樹打掘。因此其處理過程如下：

對于任一結點P华畏，

1)若其左孩子不為空，則將P入棧并將P的左孩子置為當前的P尊蚁，然后對當前結點P再進行相同的處理

2)若其左孩子為空亡笑，則取棧頂元素并進行出棧操作，訪問該棧頂結點横朋，然后將當前的P置為棧頂結點的右孩子

3)直到P為NULL并且棧為空則遍歷結束

void inOrder(BinTree *root) //非遞歸中序遍歷  {
    stack<BinTree*> s;
    BinTree *p=root; while(p!=NULL||!s.empty())
    {
         while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        } 
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<"  ";
            s.pop();
            p=p->rchild;
        }
    }    
}

• 后序遍歷

首先后序遍歷左（右）子樹仑乌，再后序遍歷右（左）子樹，最后訪問根琴锭，C語言代碼如下

void HXBL( tree* root ){

  if( root->lchild!=NULL )

    HXBL( root->lchild );

  if( root->rchild!=NULL )

    HXBL(root->rchild);

   輸出節(jié)點;

}

• 層次遍歷

即按照層次訪問晰甚，通常用隊列來做。訪問根决帖，訪問子女厕九，再訪問子女的子女（越往后的層次越低）（兩個子女的級別相同）

void BiTree::LevelOrder(BiTreeNode *t)
{//用隊列實現(xiàn)
    queue<BiTreeNode*>tq;//創(chuàng)建隊列tq，隊列的每個元素都是結點指針
    BiTreeNode* p=t;
    if(!p==NULL)
    {
        tq.push(p);
    }
    while(!tq.empty())
    {
        p = tq.front();
        cout << p->data;
        tq.pop();
        if(p->LeftChild)
        {tq.push(p->LeftChild);}
        if(p->RightChild)
        {tq.push(p->RightChild);}
    }
}

統(tǒng)計葉子結點數(shù)

int getLeafNode(BiTree T)  
{  
    if(NULL == T)  
        return 0;  
  
    if(NULL == T->leftChild && NULL == T->rightChild)  
        return 1;  
  
    return getLeafNode(T->leftChild) + getLeafNode(T->rightChild);  
}

求結點個數(shù)

int GetNodeCount(BTree* pRoot)  
{  
    if (pRoot == NULL)  
        return 0;  
  
    int LeftNum  =  GetNodeCount(pRoot->m_nLeft);  
    int RightNum =  GetNodeCount(pRoot->m_nRight);  
    int ret = LeftNum+RightNum+1;  
    return ret;  
      
}  

求二叉樹深度

int GetTreeDepth(BTree* pRoot)  
{  
    if (pRoot == NULL)  
        return 0;  
    int LeftDepth  = GetTreeDepth(pRoot->m_nLeft);  
    int RightDepth = GetTreeDepth(pRoot->m_nRight);  
    int ret = max(LeftDepth,RightDepth)+1;  
    return ret;  
}  

線索二叉樹

在結點結構中增加兩個標志域LTag和RTag地回。LTag=0時扁远，lchild域指示結點的左孩子，LTag=1時刻像，lchild域指示結點的前驅穿香；RTag=0時，rchild域指示結點的右孩子绎速，RTag=1時皮获，rchild域指示結點的后繼。

以這種結點結構構成的二叉線索鏈表纹冤，鏈表作為二叉樹的存儲結構洒宝，叫做其中指向結點前驅和后繼的指針叫做線索。對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化萌京。

• 線索二叉樹的存儲結構

在中序線索樹找結點后繼的規(guī)律是：
若其右標志為1雁歌，則右鏈為線索，指示其后繼知残，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其后繼靠瞎；找結點前驅的規(guī)律是：若其左標志為1，則左鏈為線索求妹，指示其前驅乏盐，否則遍歷左子樹時最后訪問的一個結點（左子樹中最右下的結點）為其前驅。

在后序線索樹中找到結點的后繼分三種情況：
若結點是二叉樹的根制恍，則其后繼為空父能；若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹净神，則其后繼即為雙親結點何吝；若結點是其雙親的左孩子溉委，且其雙親有右子樹，則其后繼為雙親右子樹上按后序遍歷列出的第一個結點（最左下角的葉子結點）爱榕。

二叉搜索樹

• 查找從根結點開始瓣喊，如果樹為空，返回NULL
• 若搜索樹非空黔酥，則根結點關鍵字和X進行比較型宝，并進行不同處理：
• 若X小于根結點鍵值，只需在左子樹中繼續(xù)搜索
• 若X大于根結點的鍵值絮爷，在右子樹中繼續(xù)進行搜索
• 若兩者比較結果相等趴酣，搜索完成，返回指向此結點的指針坑夯。

查找

Positon Find(ElementType X, BinTree BST)   
{   
    if(!BST)   
        return NULL; // 查找失敗   
    if(X > BST->Data)   
        return Find(X, BST->Right); // 在右子樹中繼續(xù)查找   
    else if (X < BST->Data)  
        return Find(X, BST->Left); // 在左子樹中繼續(xù)查找   
    else // X == BST->Data   
        return BST; // 查找成功岖寞，返回結點的地址 
  }

插入

BinTree Insert(ElementType X, BinTree BST)   
{   
    if( !BST )   
    {   
        // 若原樹為空，生成并返回一個結點的二叉搜索樹   
        BST = malloc( sizeof( struct TreeNode ) );   
        BST->Data = X;   
        BST->Left = BST->Right = NULL;   
    }   
    else // 開始找要插入元素的位置   
    {   
        if(X < BST->Data)   
            BST->Left = Insert(X, BST->Left); // 遞歸插入左子樹   
        else if(X > BST->Data)   
            BST->Right = Insert(X, BST->Right); // 遞歸插入右子樹   
        // else X已經存在柜蜈，什么都不做   
    }   
    return BST;   
}

刪除

要考慮三種情況
要刪除的是葉節(jié)點：直接刪除仗谆，并再修改其父結點指針，置為NULL
要刪除的結點只有一個孩子結點：將其父結點的指針指向要刪除結點的孩子結點
要刪除的結點有左淑履、右兩顆子樹：用另一結點替代被刪除結點：右子樹的最小元素或者左子樹的最大元素

BinTree Delete(ElementType X, BinTree BST)   
{   
    Position Tmp;   
    if(!BST)   
        printf("要刪除的元素未找到");   
    else if(X < BST->Data)   
        BST->Left = Delete(X, BST->Left); // 左子樹遞歸刪除   
    else if(X > BST->Data)   
        BST->Right = Delete(X, BST->Right); // 右子樹遞歸刪除   
    else // 找到要刪除的結點   
    {   
        if(BST->Left && BST->Right) // 被刪除結點有左右兩個子結點   
        {   
            Tmp = FindMin(BST->Right); // 在右子樹中找最小的元素填充刪除結點   
            BST->Data = Tmp->Data;   
            BST->Right = Delete(BST->Data, BST->Right); // 在刪除結點的右子樹中刪除最小元素   
        }   
        else // 被刪除結點有一個或無子結點   
        {   
            Tmp = BST;   
            if(!BST->Left) // 有右孩子或無子結點   
                BST = BST->Right;   
            else if(!BST->Right) // 有左孩子或無子結點   
                BST = BST->Left;   
            free(Tmp);   
        }   
    }   
    return BST;   
}

哈夫曼樹(Huffman)

哈夫曼樹樹又稱最優(yōu)二叉樹,是指對于一組帶有確定權值的葉子結點所構造的具有帶權路徑長度最短的二叉樹隶垮。
從樹中一個結點到另一個結點之間的分支構成了兩結點之間的路徑，路徑上的分支個數(shù)稱為路徑長度秘噪。
二叉樹的路徑長度是指由根結點到所有葉子結點的路徑長度之和狸吞。如果二叉樹中的葉子結點都有一定的權值，則可將這一概念拓展:設二叉樹具有n個帶權值的葉子結點,則從根結點到每一個葉子結點的路徑長度與該葉子結點權值的乘積之和稱為二叉樹路徑長度,記做：
WPL=W1L1+W2L2+......+WnLn;（n為二叉樹中葉子結點的個數(shù)指煎；Wk為第k個葉子的權值;Lk為第k個葉子結點的路徑長度）

哈夫曼算法：
(1)根據(jù)給定n個權值{w1,w2,....,wn}構成n棵二叉樹的集合F={T1,T2,.....,Tn};其中,每棵二叉樹Ti(1<=i<=n)只有一個帶權值wi的根結點,其左蹋偏、右子樹均為空。

(2)在F中選取兩棵根結點權值最小的二叉樹作為左至壤、右子樹來構造一棵新的二叉樹,且置新的二叉樹根結點權值為其左右子樹根結點的權值之和威始。

(3)在F中刪除這兩棵樹,同時將生成新的二叉樹加入到F中。

(4)重復(2)(3)像街，直到F中只剩下一棵二叉樹加入到F中黎棠。

要進行n-1次合并才能使初始化的n棵二叉樹最終合并為一棵二叉樹,因此n-1次合并共產生了n-1個新結點,即最終生成的哈夫曼樹共有2n-1個結點。

由于每次都是將兩棵權值最小的二叉樹合并生成一棵新二叉樹,所以生成的哈夫曼樹中沒有度為1的結點镰绎。

兩棵權值最小的二叉樹那棵作為作為左子樹脓斩、那棵作為右子樹，哈夫曼算法并沒有要求,故最終構造出來的哈夫曼樹并不唯一跟狱，但是最小的WPL值是唯一的俭厚。

所以，哈夫曼具有如下幾個特點：
(1)對給定的權值驶臊，所構造的二叉樹具有的最小WPL;
(2)權值大的結點離根近挪挤，權值小的結點離根遠;
(3)所生成的二叉樹不唯一
(4)沒有度為1的結點