資料結構基礎—樹與二叉樹(2)-有解無憂

五、線索二叉樹

1.什么是線索二叉樹

遍歷二叉樹的結果是，求得結點的一個線性序列，結點中再添加兩個標記“LTag和RTag”,來判斷當前結點是否有孩子

若左子樹不空，則，將lchild指向其左子樹，且左標志域的值為“Link”;否則(空)，lchild指向前驅，且左標志的值為“Thread”
若右子樹不空，則，將lchild指向其右子樹，且右志域的值為“Link”;否則(空)，lchild指向后繼，且右標志的值為“Thread”

總之，不空正常指向，空，左：指向前驅；右：指向后繼(若無頭針，則可能有空懸)

型別描述如下

typedef struct BiNode {
	Datatype data;//資料內容
	struct BiNode  *Lchild;//指向左孩子結點
	struct BiNode  *rchild;//指向右孩子結點
	int Ltag;//值為0，則Lchild指向該結點的左孩子；值為1.指向該結點的前驅結點
	int rtag;//值為0，則rchild指向該結點的右孩子；值為1.指向該結點的后繼結點
} BiNode ;

三種遍歷

先序

中序

后序

要會自己劃線，實線是指標，虛線是線索

2.建立(線索化)線索二叉樹

才用遞回的方法，以中序為例，先處理左子，再處理當前結點，最后處理右子即可

需要添加輔助指標pre:指向當前訪問的指標p的前驅（邏輯前驅）

//不帶頭結點
void inThreading(p){
    if(p){//p就是根結點，不空
        inThreading(p->lchild);//處理左子
        //處理當前結點
        if(左子空){
            p->LTag = Thread;
            p->lchild = pre;//前驅
        }
        if(右子空){
            p->RTag =Thread;//標記為無右孩子
        }
        if(pre&&pre->RTag == Thread){pre不空且沒有右孩子(pre是當前的前驅)
            pre->rchild = p;
        }
        pre = p;//我自己就是自己的前驅
        inThreading(p->rchild);//處理右子
    }
}

3.遍歷線索二叉樹

中序不需要堆疊，先序和后序需要堆疊

以中序為例，先找到第一個結點，然后判斷其是否有右子樹，若無，則訪問其線索指向的地址(當前的后繼)，如果有右子樹，則讓p = p->rchild繼續按中序遍歷

//有頭結點
while(樹不空){
    while(左有子樹){
        p = p->lchild;//一直沿著左鏈走，找到第一個沒有左子的結點p
        訪問一下p 
        while(p->rchild == Thread&& != T) p = p->rchild并訪問p的后繼結點
        否則(p有右子樹)：p = p->rchild;//成為新的根結點
    }
}

六、樹和森林的表示方法

1.雙親表示法

typedef struct PTNode{
    Elem data;
    int parent;//雙親位置域，-1則為根
}PTNode;

2.孩子鏈表法

在雙親鏈表的基礎上，增加一個指標域，來依次存放該結點的孩子結點(深度為一)

3.左孩子右兄弟表示法

firstchild:存放其左邊的結點
nextsibling：同級左結點的全部兄弟結點

typedef struct CSNode{
    Elem data;
    struct CSNode *firstchild.*nextsibling;
}CSNode.*CSTree;

4.樹、森嶺與二叉樹的轉化

a.數和二叉樹

樹和轉化為二叉樹

在樹的每層從左至右在兄弟結點之間添加虛線
除左第一個結點，父結點與所有的子結點的連線去掉
將原來的實，線左移；將后添的虛線便實線，右移

變化之后的二叉樹的根結點沒有右子樹，左結點還是原來的左結點，所有沿右鏈往下的結點均是該解結點的兄弟結點

二叉樹還原回樹

將父結點與該左結點的右鏈間全部添加虛線
將所有的右分支的連線全部去掉
將虛線相連的結點上移

b.森林與二叉樹

森林轉化為二叉樹

先將森林中的每一棵樹化為二叉樹
從最后一顆二叉樹開始，每一顆二叉樹的根作為前一顆二叉樹根的右子

二叉樹還原為森林

將二叉樹的根右子依次去掉
在每一顆二叉樹還原回樹

七、樹和森嶺的遍歷

1.樹的遍歷

總體分為先根、后根、和層次遍歷

先根：先訪問根結點，在訪問葉子結點；后根：先訪問葉子，再訪問根

樹的先根遍歷等價于二叉樹的先序遍歷
樹的后根遍歷等價于二叉樹的中序遍歷

森林的遍歷

總體分為先序、中序和后序

森林的先序 = 二叉的先序
森林的中序 = 二叉的中序
森林的后序 = 二叉的后序

3.應用

假設存盤結構式孩子兄弟鏈表，來存盤一般的樹

typedef struct CSNode{
    Elem data;
    struct CSNode *firstchild.*nextsibling;
}CSNode.*CSTree;

a.求樹的深度

int TreeDepth(CSTree T){
    if(!T) return 0;
    else{
        h1 = TreeDepth(T->firstchild);
        h2 = TreeDepth(T->nextsibling);
        return (max(h1+1,h2));
    }
}

b.輸出樹中所有從根到葉子的路徑

基本原理：

若不空：一直沿著左鏈走進堆疊，直到左子是空，判斷有沒有右

左空：代表是葉子結點，列印路徑，并出堆疊

左空，沒有右子樹：退回到上一結點

左空，有右子樹：將右子樹入堆疊，再判斷

//使用堆疊
void ALLPath(Bitree T,stack &S){
    if(T){
        //進堆疊；
        if(!T->lchild) //列印堆疊的元素(堆疊底到堆疊頂)
        else{
            ALLPath(T->lchild,S);
            ALLPath(T->rchild,S);
        }
        //出堆疊
    }
}

八、哈夫曼樹

1.相關概念

結點路徑：樹中一個結點到另一個結點之間的分支構成的路徑eg:AEF
路徑長度：結點路徑上的分支樹
樹的路徑長度：根結點到每一個葉子的路徑長度的和
結點的帶權路徑長度：根結點到結點之間的路勁長度于結點權值的乘積
樹的帶權路徑長度：根到每一個葉子的帶權路徑長度的和

哈夫曼(Huffman)樹,一顆帶權路徑長度最小的二叉樹(最優樹)，沒有度為1的結點

2.哈夫曼樹的構造

簡單的幾個規定：權小左，權大右，權值相等淺為左

n個葉子，總結點 2n - 1(n + (n - 1))個

構造方法

從n個里面找最小的兩個，合并成一顆二叉樹，
其根結點的權值 = 兩個小葉子權值的和
去除這兩個小結點
新根作為新結點
直到只剩下一個結點

推薦使用靜態鏈表來實作

靜態鏈表

//獲取兩個最小值
int *Select(HuffmanTree HT,int n){
	int s1,s2;////最小值與極小值 
	int mmin =  Max_S;//先等于無窮大 
	int min = Max_S;
    for(int i = 1;i <= n;i++){
        if(HT[i].parent != 0) continue;//雙親不為零代表已經構成新樹，應去除
        else{
            if(mmin >= HT[i].weight){//最小的
                min = mmin ;
                s2 = s1;
                mmin = HT[i].weight;
                s1 = i;
            }else if(min >= HT[i].weight){//次小的 
                min = HT[i].weight;
                s2 = i; 
            }
        }
    }
    //若最小值相等，則淺(先遍歷的)樹的序號在前 
    int S1 = qiushendu(HT,s1);
    int S2 = qiushendu(HT,s2);
    if(S1 >= S2){
    	int temp;
    	temp = s1; s1 = s2; s2 = temp;//交換順序 
	}
	//用陣列存放最小值和次小值 
    int a[3] = {0,s1,s2};
    return a;
}

//構建哈夫曼樹 
void CreatHuffmanTree(HuffmanTree &HT,char *huf,int *wei,int n){
    int s1,s2;//最小值與極小值 
    if(n <= 1){
        cout << "抱歉，您輸入的結點數不符合邏輯";
        return;
    }
    int m = 2*n-1;//總結點樹
    HT = new HTNode[m+1];//放棄下標為零的陣列
    //先遍歷前n個數,初始化
    for(int i = 1;i <= m;i++){//全部初始化為零
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
  
	//賦結點、權值 
    for(int i;i <= n;i++){
    	HT[i].data = https://www.cnblogs.com/wht-de-bk/p/huf[i];//結點 
    	HT[i].weight = wei[(int)huf[i]];//權值 
    
	}
    //遍歷后n+1個，新根
    for(int i = n+1;i <= m;i++){
        //找出最小額兩個結點
        int *a;//獲取s1和s2 
		a = Select(HT,i-1);//在n個數中找
		s1 = a[1]; s2 = a[2];
        //更新各個數值
        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;  
    }

3.哈夫曼編碼

1.引入

為提高傳輸速度，要求編碼盡可能短，還要保證任意字符的編碼都不是另一個字符編碼的前綴，即前綴編碼，Huffman樹可以用來構造長度不等且不產生二義性的編碼，

那該怎么決議(譯碼)呢？

從根結點出發走一條從跟到葉子的路徑程序(遇0向左，遇1向右)，達到葉子結點就譯出一個字符，直至譯碼完成

2.哈夫曼的構造

基本思想：概率大的字符用短碼，小的用長碼，構造哈夫曼樹，像下圖那樣(權值即頻率)

3.相關結論

哈夫曼編碼是不等長的編碼
哈夫曼樹，沒有度為一的結點
發送：根據哈夫曼樹得到的編碼表送出字符資料
接收：按左0右1的規定，從根到葉子的遍歷

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538037.html

標籤：其他

上一篇：基于Spring-AOP的自定義分片工具

下一篇：ADPCM(自適應差分脈沖編碼調制)的原理和計算