二叉樹的應用詳解 – 數據結構

概述：

平衡樹——特點：所有結點左右子樹深度差≤1

排序樹——特點：所有結點“左小右大
字典樹——由字符串構成的二叉排序樹
判定樹——特點：分支查找樹（例如12個球如何只稱3次便分出輕重）
帶權樹——特點：路徑帶權值（例如長度）

最優樹——是帶權路徑長度最短的樹，又稱 Huffman樹，用途之一是通信中的壓縮編碼。

1. 二叉排序樹（二叉查找樹 Binary Search Tree）：

1.1 二叉排序樹：

或是一棵空樹；或者是具有如下性質的非空二叉樹：

 （1）若左子樹不為空，左子樹的所有結點的值均小于根的值；

 （2）若右子樹不為空，右子樹的所有結點均大于根的值；

 （3）它的左右子樹也分別為二叉排序樹。

例：二叉排序樹 如圖9.7：

      二叉排序樹的查找過程和次優二叉樹類似，通常采取二叉鏈表作為二叉排序樹的存儲結構。中序遍歷二叉排序樹可得到一個關鍵字的有序序列，一個無序序列可以通過構造一棵二叉排序樹變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。每次插入的新的結點都是二叉排序樹上新的葉子結點，在進行插入操作時，不必移動其它結點，只需改動某個結點的指針，由空變為非空即可。搜索,插入,刪除的復雜度等于樹高，期望O(logn),最壞O(n)(數列有序,樹退化成線性表).
雖然二叉排序樹的最壞效率是O(n),但它支持動態查詢,且有很多改進版的二叉排序樹可以使樹高為O(logn),如SBT,AVL,紅黑樹等.故不失為一種好的動態排序方法.

2.2 二叉排序樹b中查找

在二叉排序樹b中查找x的過程為：

1. 若b是空樹，則搜索失敗，否則：

2. 若x等于b的根節點的數據域之值，則查找成功；否則：

3. 若x小于b的根節點的數據域之值，則搜索左子樹；否則：

4. 查找右子樹。

2.3 在二叉排序樹插入結點的算法

向一個二叉排序樹b中插入一個結點s的算法，過程為：

1. 若b是空樹，則將s所指結點作為根結點插入，否則：

2. 若s->data等于b的根結點的數據域之值，則返回，否則：

3. 若s->data小于b的根結點的數據域之值，則把s所指結點插入到左子樹中，否則：

4. 把s所指結點插入到右子樹中。

2. /*當二叉排序樹T中不存在關鍵字等于e.key的數據元素時，插入e并返回TRUE，否則返回FALSE*/    
   Status InsertBST(BiTree &T, ElemType e){    
       if(!SearchBST(T, e.key, NULL,p){    
           s=(BiTree)malloc(sizeof(BiTNode));    
           s->data = e; s->lchild = s->rchild = NULL;    
           if(!p)  T-s;    //被插結點*s為新的根結點    
           else if LT(e.key, p->data.key) p->lchld = s;  //被子插結點*s為左孩子    
           else p->rchild = s;  //被插結點*s為右孩子    
           return TRUE;    
       }    
       else return FALSE;  //樹中已有關鍵字相同的結點，不再插入    
   }

2.4 在二叉排序樹刪除結點的算法

在二叉排序樹刪去一個結點，分三種情況討論：

1. 若*p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由于刪去葉子結點不破壞整棵樹的結構，則只需修改其雙親結點的指針即可。

2. 若*p結點只有左子樹PL或右子樹PR，此時只要令PL或PR直接成為其雙親結點*f的左子樹即可，作此修改也不破壞二叉排序樹的特性。

3. 若*p結點的左子樹和右子樹均不空。在刪去*p之后，為保持其它元素之間的相對位置不變，可按中序遍歷保持有序進行調整，可以有兩種做法：其一是令*p的左子樹為*f的左子樹，*s為*f左子樹的最右下的結點，而*p的右子樹為*s的右子樹；其二是令*p的直接前驅（或直接后繼）替代*p，然后再從二叉排序樹中刪去它的直接前驅（或直接后繼）。在二叉排序樹上刪除一個結點的算法如下：

Status DeleteBST(BiTree &T, KeyType key){  
    //若二叉排序樹T中存在關鍵字等于key的數據元素時，則刪除該數據元素，并返回  
    //TRUE；否則返回FALSE  
    if(!T) return FALSE;    //不存在關鍵字等于key的數據元素  
    else{  
        if(EQ(key, T->data.key)) {return Delete(T)};     找到關鍵字等于key的數據元素  
        else if(LT(key, T->data.key))    return DeleteBST(T->lchild, key);  
        else return DeleteBST(T->rchild, key);  
    }  
}  
Status Delete(BiTree &p){  
    //從二叉排序樹中刪除結點p，并重接它的左或右子樹  
    if(!p->rchild){  //右子樹空則只需重接它的左子樹  
        q=p; p=p->lchild;    free(q);  
    }  
    else if(!p->lchild){ //左子樹空只需重接它的右子樹  
        q=p; p=p->rchild; free(q);  
    }  
    else{   //左右子樹均不空  
        q=p;   
                s=p->lchild;  
        while(s->rchild){   
                       q=s;   
                       s=s->rchild  
                }   //轉左，然后向右到盡頭  
        p->data = s->data;    //s指向被刪結點的“前驅”  
        if(q!=p)      
                       q->rchild = s->lchild; //重接*q的右子樹  
        else   
                        q->lchild = s->lchild;    //重接*q的左子樹  
        free(s);  
    }  
    return TRUE;  
}

2. 5二叉排序樹性能分析

每個結點的C_i為該結點的層次數。最壞情況下，當先后插入的關鍵字有序時，構成的二叉排序樹蛻變為單支樹，樹的深度為n，其平均查找長度為 （和順序查找相同），最好的情況是二叉排序樹的形態和折半查找的判定樹相同，其平均查找長度和log₂(n)成正比 （O(log₂(n))）。

2.6 二叉排序樹的優化

    Size Balanced Tree(SBT)
    AVL樹
    紅黑樹
    Treap(Tree+Heap)
這些均可以使查找樹的高度為O(logn)

2. 平衡樹二叉樹）（又稱AVL 樹）：

1. 1 平衡二叉樹（Balanced Binary Tree）

性質：  左右子樹都是平衡二叉樹且所有結點左、右子樹深度之差的絕對值 ≤ 1。

若定義結點的“平衡因子”  BF（Balance Factor） = 左子樹深度 –右子樹深度 則：平衡二叉樹中所有結點的BF ∈[ -1, 0, 1 ]

例：判斷下列二叉樹是否AVL樹？

常用算法有紅黑樹、AVL、Treap、伸展樹等。在平衡二叉搜索樹中，我們可以看到，其高度一般都良好地維持在O（log2n），大大降低了操作的時間復雜度。

平衡二叉樹是二叉排序樹的另一種形式。

我們希望由任何初始序列構成的二叉排序樹都是平衡二叉樹。因為平衡二叉樹上任何結點的左右子樹的深度之差都不超過1，則可以證明它的深度和logN是同數量級的（其中N是結點的個數）。由此，它的平均查找長度也和logN同數量級。

C語言描述:

typedef struct  BSTNode {    
    ElemType    data;    
    int     bf;     //結點的平衡因子    
    struct BSTNode  *lchild, *rchild;       
    //左、右孩子指針    
} BSTNode, * BSTree;    
typedef struct  BSTNode {  
        ElemType    data;  
        int     bf;     //結點的平衡因子  
        struct BSTNode  *lchild, *rchild;     
                        //左、右孩子指針  
    } BSTNode, * BSTree;

構造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉技術。

插入算法 :

算法思想：

在平衡二叉排序樹BBST上插入一個新的數據元素e的遞歸算法可描述如下：

1．若BBST為空樹，則插入一個數據元素為e的新結點作為BBST的根結      點，樹的深度增1； 

2．若e的關鍵字和BBST的根結點的關鍵字相等，則不進行插入； 

3．若e的關鍵字小于BBST的根結點的關鍵字，而且在BBST的左子樹中不存在和e有相同關鍵字的結點，則將e插入在BBST的左子樹上，并且當插入之后的左子樹深度增加（＋1）時，分別就下列不同情況處理之：

    i．BBST的根結點的平衡因子為－1（右子樹的深度大于左子樹的深度）：則將根結點的平衡因子更改為0，BBST的深度不變；

    ii．BBST的根結點的平衡因子為0（左、右子樹的深度相等）：則將根結點的平衡因子更改為1，BBST的深度增1； 

    iii．BBST的根結點的平衡因子為1（左子樹的深度大于右子樹的深度）：

         a. 若BBST的左子樹根結點的平衡因子為1，則需進行單向右旋平衡處理，并且在右旋處理之后，將根結點和其右子樹根結點的平衡因子更改為0，樹的深度不變；

         b. 若BBST的左子樹根結點的平衡因子為－1，則需進行先向左、后向右的雙向旋轉平衡處理，并且在旋轉處理之后，修改根結點和其左、右子樹根結點的平衡因子，樹的                深度不變。

4．若e的關鍵字大于BBST的根結點的關鍵字，而且在BBST的右子樹中不存在和e有相同關鍵字的結點，則將e插入在BBST的右子樹上，并且當插入之后的右子樹深度增加（＋1）時，分別就不同情況處理之。其處理操作和上述3．中描述相對稱。

3. 判定樹（決策樹）：

      二分查找過程可用二叉樹來描述：把當前查找區間的中間位置上的結點作為根，左子表和右子表中的結點分別作為根的左子樹和右子樹。由此得到的二叉樹，稱為描述二分查找的判定樹(Decision Tree 決策樹)或比較樹(Comparison Tree)。

注意：
    　判定樹的形態只與表結點個數n相關，而與輸入實例中R[1..n].keys的取值無關。【例】具有11個結點的有序表可用下圖所示的判定樹來表示。

舉例：12個球如何用天平只稱3次便分出輕重？

分析：12個球中必有一個非輕即重，即共有24種“次品”的可能性。每次天平稱重的結果有3種，連稱3次應該得到的結果有33=27種。說明僅用3次就能找出次品的可能性是存在的。

思路：首先，將12個球分三組，每組4個，任意取兩組稱。會有兩種情況：平衡，或不平衡。其次，一定要利用已經稱過的那些結論；即充分利用“舊球”的標準性作為參考。

二分查找判定樹的查找
二分查找就是將給定值K與二分查找判定樹的根結點的關鍵字進行比較。若相等，成功。否則若小于根結點的關鍵字，到左子樹中查找。若大于根結點的關鍵字，則到右子樹中查找。
　　【例】對于有11個結點的表，若查找的結點是表中第6個結點，則只需進行一次比較；若查找的結點是表中第3或第9個結點，則需進行二次比較；找第1，4，7，10個結點需要比較三次；找到第2，5，8，11個結點需要比較四次。
    　由此可見，成功的二分查找過程恰好是走了一條從判定樹的根到被查結點的路徑，經歷比較的關鍵字次數恰為該結點在樹中的層數。若查找失敗，則其比較過程是經歷了一條從判定樹根到某個外部結點的路徑，所需的關鍵字比較次數是該路徑上內部結點的總數。
    【例】待查表的關鍵字序列為：(05，13，19，21，37，56，64，75，80，88，92)，若要查找K=85的記錄，所經過的內部結點為6、9、10，最后到達方形結點"9-10"，其比較次數為3。
    　實際上方形結點中"i-i+1"的含意為被查找值K是介于R[i].key和R[i+1].key之間的，即R[i].key<K<R[i+1].key。二分查找的平均查找長度
     　設內部結點的總數為n=2^h-1，則判定樹是深度為h=lg(n+1)的滿二叉樹(深度h不計外部結點)。樹中第k層上的結點個數為2^k-1，查找它們所需的比較次數是k。因此在等概率假設下，二分查找成功時的平均查找長度為：
           ASL_bn≈lg(n+1)-1
　　二分查找在查找失敗時所需比較的關鍵字個數不超過判定樹的深度，在最壞情況下查找成功的比較次數也不超過判定樹的深度。即為：
           
　　二分查找的最壞性能和平均性能相當接近。

二分查找的優點和缺點
　　雖然二分查找的效率高，但是要將表按關鍵字排序。而排序本身是一種很費時的運算。既使采用高效率的排序方法也要花費O(nlgn)的時間。
　　二分查找只適用順序存儲結構。為保持表的有序性，在順序結構里插入和刪除都必須移動大量的結點。因此，二分查找特別適用于那種一經建立就很少改動、而又經常需要查找的線性表。
　　對那些查找少而又經常需要改動的線性表，可采用鏈表作存儲結構，進行順序查找。鏈表上無法實現二分查找。

5. 帶權樹：

即路徑帶有權值。例如：

6. 最優樹（赫夫曼樹）：

赫夫曼樹：給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為赫夫曼樹(Huffman tree)。即帶權路徑長度最短的樹。赫夫曼樹構造算法：假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為{ w1、w2、…、wn}，則哈夫曼樹的構造規則為：　　(1) 將{w1、w2、…，wn}看成是有n 棵樹的森林(每棵樹僅有一個結點)；　　(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；　　(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；　　(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。赫夫曼編碼：是通信中最經典的壓縮編碼.
其算法：stdafx.h文件：

// stdafx.h : include file for standard system include files,  
// or project specific include files that are used frequently, but  
// are changed infrequently  
//  
  
#pragma once  
  
#include <stdio.h>    
#include "stdlib.h"  
#include <iostream>  
using namespace std;  
  
  
//宏定義      
#define TRUE   1      
#define FALSE   0      
#define OK    1      
#define ERROR   0    
#define INFEASIBLE -1      
#define OVERFLOW -2    
#define STACKEMPTY -3   
#define QUEUEEMPTY  -3      
  
#define MAX 10 // MAXIMUM STACK CONTENT    
#define MAX_QUEUE 10 // MAXIMUM QUEUE CONTENT    
  
typedef int Status;      
typedef int ElemType;    
  
typedef struct{  
    unsigned int weight;  
    unsigned int parent, lchild,rchild;  
}HTNode, *HuffmanTree;  //動態分配數組存儲赫夫曼樹  
  
typedef char * * HuffmanCode;//動態分配數組存儲赫夫曼編碼表

test.cpp文件：

// Test.cpp : Defines the entry point for the console application.    
//    
#include "stdafx.h"    
  
  
  
/************************************************************************/  
/* 算法： 
*/  
/************************************************************************/  
  
void select(HuffmanTree &HT,int n,int &h1,int &h2)  
{  
    int i ,j;  
  
    for(i=1;i<=n;i++)  
        if(!HT[i].parent)  //一旦找到父結點不為0的結點就停止  
        {  
            h1=i;       
            break;  
        }  
        for(j=i+1;j<=n;j++)  
            if(!HT[j].parent)  
            {  
                h2=j;  
                break;  
            }  
            for(i=1;i<=n;i++)  
                if(HT[h1].weight>HT[i].weight&&!HT[i].parent&&(h2!=i))  
                    h1=i;   //進行比較，找權值最小，和h2不同的結點  
            for(j=1;j<=n;j++)  
                if(HT[h2].weight>HT[j].weight&&!HT[j].parent&&(h1!=j))  
                    h2=j;   //進行比較，找權值最小，和h1不同的結點  
            if(h1>h2)  
            {  
                int temp;    //將權值最小的結點賦給h1  
                temp=h1;  
                h1=h2;  
                h2=temp;  
            }  
}  
/************************************************************************/  
/* 
w存放n 個字符的權值（均>0),構造赫夫曼樹HT，并求出n 個字符的赫夫曼編碼HC。 
*/  
/************************************************************************/  
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w,int n)  
{  
    if(n<=1) return;  
    int m,i;  
    char *cd;  
    int s1, s2;  
    // HuffmanTree p;  
    m = 2*n-1;  
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));  //0號單元未用  
    for (i=1; i<=n; i++) { //初始化,相當： p = HT; p = {*w, 0, 0,0 }， ++p;  
        HT[i].weight=w[i-1];  
        HT[i].parent=0;  
        HT[i].lchild=0;  
        HT[i].rchild=0;  
    }  
    for (i=n+1; i<=m; i++) { //初始化 p = {*w, 0, 0,0 }， ++p;  
        HT[i].weight=0;  
        HT[i].parent=0;  
        HT[i].lchild=0;  
        HT[i].rchild=0;  
    }  
  
    //添加查看便于調試  
    printf("\n-------------------------------------------");  
    printf("\n哈夫曼樹的構造過程如下所示：\n");  
    printf("HT初態:\n");  
    printf(" 結點   weight  parent  lchild  rchild");  
    for (i=1; i<=m; i++)  
        printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild);  
  
    for (i=n+1; i<=m; i++) { // 建哈夫曼樹  
        // 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，  
        // 其序號分別為s1和s2。  
        select(HT, i-1,s1,s2);  
        HT[s1].parent = i; HT[s2].parent = i;  
        HT[i].lchild = s1; HT[i].rchild = s2;  
        HT[i].weight = HT[s1].weight + HT[s2].weight;  
        //添加查看，便于調試  
        printf("\nselect: s1=%d s2=%d\n", s1, s2);  
        printf(" 結點   weight  parent  lchild  rchild");  
        for (int j=1; j<=i; j++)  
            printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,  
            HT[j].parent,HT[j].lchild, HT[j].rchild);  
  
    }  
  
    //---從葉子到根逆向求每個字符的赫夫曼編碼---  
    int start,f;  
    unsigned int c;  
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n個字符編碼的頭指針向量  
    cd=(char *)malloc(n*sizeof(char));     //分配求編碼的工作空間  
    cd[n-1]='';        //編碼結束符  
    for(i=1;i<=n;++i)  
    {  
        //逐個字符求赫夫曼編碼  
        start=n-1;  
        for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼  
            if(HT[f].lchild==c)  
                cd[--start]='0';  
            else  
                cd[--start]='1';  
        HC[i]=(char *)malloc((n-start)*sizeof(char)); //為第i個字符編碼分配空間  
        strcpy(HC[i],&cd[start]);  //從cd復制編碼到HC  
    }  
    free(cd);  //釋放工作區間  
}  
void main()  
{  
    HuffmanTree HT; HuffmanCode HC; int *w,n,i;  
    printf("輸入結點數： ");  
    scanf("%d",&n);  
    HC=(HuffmanCode)malloc(n*sizeof(HuffmanCode));  
    w=(int *)malloc(n*sizeof(int));  
    printf("輸入%d個結點的權值: ",n);  
    for(i=0;i<n;i++)  
        scanf("%d",&w[i]);  
    HuffmanCoding(HT,HC,w,n);  
    printf("\n-------------------------------------------\n");  
    printf("\n各結點的赫夫曼編碼:\n");  
    printf("編號  權值  編碼\n");  
    for(i=1;i<=n;i++)  
        printf("%2d,%6d:%6s\n",i,w[i-1],HC[i]);  
  
}

轉自：http://blog.csdn.net/hguisu/article/details/7686515