1、線索二叉樹
背景
二叉樹的遍歷本質(zhì)上是將一個復(fù)雜的非線性結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，使每個結(jié)點都有了唯一前驅(qū)和后繼（第一個結(jié)點無前驅(qū)，最后一個結(jié)點無后繼）。對于二叉樹的一個結(jié)點，查找其左右子女是方便的，其前驅(qū)后繼只有在遍歷中得到。為了容易找到前驅(qū)和后繼，有兩種方法。一是在結(jié)點結(jié)構(gòu)中增加向前和向后的指針，這種方法增加了存儲開銷，不可取；二是利用二叉樹的空鏈指針。
實施
在二叉樹鏈表結(jié)構(gòu)中的結(jié)點中添加兩個標(biāo)志位，ltag和rtag，當(dāng)ltag和rtag為0時，leftChild和rightChild分別是指向左孩子和右孩子的指針；否則，leftChild是指向結(jié)點前驅(qū)的線索(pre)，rightChild是指向結(jié)點的后繼線索(suc)：
線索二叉樹結(jié)點
而且線索化的二叉樹在進(jìn)行遍歷時，其實就是等價于操作一個
雙向鏈表結(jié)構(gòu)；因為類似雙向鏈表結(jié)構(gòu)，所以我們在二叉樹線索鏈表上添加一個頭結(jié)點。
線索二叉樹
由上圖所示，中序遍歷方式結(jié)果為
HDIBJEAFCG，所有的葉子結(jié)點是沒有子結(jié)點的，所以ltag和rtag都為1，即表示前驅(qū)結(jié)點和后驅(qū)結(jié)點。而ltag和rtag為0時分別表示左右指向的是左右子結(jié)點。
代碼
/* Link==0表示指向左右孩子指針, */
/* Thread==1表示指向前驅(qū)或后繼的線索 */
typedef enum {Link,Thread} PointerTag;
/* 線索二叉樹存儲結(jié)點結(jié)構(gòu)*/
typedef struct BiThrNode{
//數(shù)據(jù)
CElemType data;
//左右孩子指針
struct BiThrNode *lchild,*rchild;
//左右標(biāo)記
PointerTag LTag;
PointerTag RTag;
}BiThrNode,*BiThrTree;
/*
8.1 打印
*/
Status visit(CElemType e)
{
printf("%c ",e);
return OK;
}
/*
8.3 構(gòu)造二叉樹
按照前序輸入線索二叉樹結(jié)點的值,構(gòu)造二叉樹T
*/
Status CreateBiThrTree(BiThrTree *T){
CElemType h;
//scanf("%c",&h);
//獲取字符
h = str[indexs++];
if (h == Nil) {
*T = NULL;
}else{
*T = (BiThrTree)malloc(sizeof(BiThrNode));
if (!*T) {
exit(OVERFLOW);
}
//生成根結(jié)點(前序)
(*T)->data = h;
//遞歸構(gòu)造左子樹
CreateBiThrTree(&(*T)->lchild);
//存在左孩子->將標(biāo)記LTag設(shè)置為Link
if ((*T)->lchild) (*T)->LTag = Link;
//遞歸構(gòu)造右子樹
CreateBiThrTree(&(*T)->rchild);
//存在右孩子->將標(biāo)記RTag設(shè)置為Link
if ((*T)->rchild) (*T)->RTag = Link;
}
return OK;
}
/*
8.3 中序遍歷二叉樹T, 將其中序線索化,Thrt指向頭結(jié)點
*/
BiThrTree pre; /* 全局變量,始終指向剛剛訪問過的結(jié)點 */
/* 中序遍歷進(jìn)行中序線索化*/
void InThreading(BiThrTree p){
if (p) {
visit(p->data);
//遞歸左子樹線索化
InThreading(p->lchild);
//無左孩子
if (!p->lchild) {
//前驅(qū)線索
p->LTag = Thread;
//左孩子指針指向前驅(qū)
p->lchild = pre;
}else
{
p->LTag = Link;
}
//前驅(qū)沒有右孩子
if (!pre->rchild) {
//后繼線索
pre->RTag = Thread;
//前驅(qū)右孩子指針指向后繼(當(dāng)前結(jié)點p)
pre->rchild = p;
}else
{
pre->RTag = Link;
}
//保持pre指向p的前驅(qū)
pre = p;
// visit(pre->data);//
//遞歸右子樹線索化
InThreading(p->rchild);
}
}
/* 中序遍歷二叉樹T,并將其中序線索化,Thrt指向頭結(jié)點 */
Status InOrderThreading(BiThrTree *Thrt , BiThrTree T){
*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if (! *Thrt) {
exit(OVERFLOW);
}
//建立頭結(jié)點;
(*Thrt)->LTag = Link;
(*Thrt)->RTag = Thread;
//右指針回指向
(*Thrt)->rchild = (*Thrt);
/* 若二叉樹空,則左指針回指 */
if (!T) {
(*Thrt)->lchild=*Thrt;
}else{
(*Thrt)->lchild=T;
pre=(*Thrt);
//中序遍歷進(jìn)行中序線索化
InThreading(T);
//最后一個結(jié)點rchil 孩子
pre->rchild = *Thrt;
//最后一個結(jié)點線索化
pre->RTag = Thread;
(*Thrt)->rchild = pre;
}
return OK;
}
/*中序遍歷二叉線索樹T*/
Status InOrderTraverse_Thr(BiThrTree T){
BiThrTree p;
p=T->lchild; /* p指向根結(jié)點 */
while(p!=T)
{ /* 空樹或遍歷結(jié)束時,p==T */
while(p->LTag==Link)
p=p->lchild;
if(!visit(p->data)) /* 訪問其左子樹為空的結(jié)點 */
return ERROR;
while(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data); /* 訪問后繼結(jié)點 */
}
p=p->rchild;
}
return OK;
}
//調(diào)試代碼
BiThrTree H,T;
StrAssign(str,"ABDH##I##EJ###CF##G##");
CreateBiThrTree(&T); /* 按前序產(chǎn)生二叉樹 */
InOrderThreading(&H,T); /* 中序遍歷,并中序線索化二叉樹 */
InOrderTraverse_Thr(H);
2、哈夫曼樹
背景
給定N個權(quán)值作為N個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。
哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度（若根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù)）。樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個權(quán)值Wi（i=1,2,...n）構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為Li（i=1,2,...n）?？梢宰C明哈夫曼樹的WPL是最小的。
例子（一）
成績權(quán)重
上圖中記錄一個班級一門學(xué)科成績的分布比例，想要找出任何一個同學(xué)成績是在哪個范圍的問題，通常會從左往右依次比較大小，那么所對應(yīng)的WPL如下：
常規(guī)算法
如果我們從中間截斷，例如80為分界點，那么如果成績是75，即可只在小于80的范圍內(nèi)查找該屬于那個等級。
最小WPL二叉樹
更換二叉樹結(jié)點位置，即可將WPL減少，那么意味著查找某一個成績所在等級問題的解決過程就更快了。
如果我們根據(jù)成績每個范圍的權(quán)值排序后按照左子結(jié)點小于右子結(jié)點的規(guī)律排列成新二叉樹，那么如下所示：
哈夫曼算法
這種算法是不是WPL就更小了，也就達(dá)到了解決此問題的最優(yōu)解。
例子（二）
例如手機(jī)發(fā)送數(shù)據(jù)中，26個英文字母，每個字母都用二進(jìn)制的方式（從000開始遞增）來表示，如下圖ABCDEF的傳輸內(nèi)容即為000 001 011 100 101這么一個長度為15的數(shù)字串：
而且每個字母出現(xiàn)的概率權(quán)重值不一樣，例如
A --> F權(quán)重值依次為27、8、15、15、30、5，那么我們就可以利用哈夫曼樹的概念對數(shù)據(jù)的大小做一個優(yōu)化。畢竟用戶量大的時候網(wǎng)絡(luò)吃緊，這種優(yōu)化還是很有作用的。首先需要將權(quán)重值從小到大排序，然后根據(jù)左子結(jié)點權(quán)重值小于右子結(jié)點權(quán)重值的規(guī)律，排列為最優(yōu)的哈夫曼樹：
那么假設(shè)雙親結(jié)點到左孩子的連線用數(shù)字0表示，到右孩子的連線用1表示，那么就得到如下結(jié)果：
那么相同的一串字母數(shù)據(jù)BADCADFEED，原方式下的數(shù)據(jù)長度為30（001 000 011 010 000 011 101 100 100 011），利用上圖中得到的字母相應(yīng)數(shù)字串，重新組合，長度則成了25（1001 01 00 101 01 00 1001 11 11 00），從而減少數(shù)據(jù)的傳輸量。
思路
哈夫曼樹的思路：
- 初始化哈夫曼?叉樹。
- 循環(huán)不斷找到結(jié)點中,最?的2個結(jié)點值. 加?到哈夫曼樹中.
哈夫曼編碼的思路：
- 根據(jù)權(quán)值構(gòu)建哈夫曼樹。
- 循環(huán)遍歷[0,n]個結(jié)點。
- 創(chuàng)建臨時結(jié)點cd，從根節(jié)點開始對其進(jìn)行編碼，左孩子為0，右孩子為1。
- 將編碼后的結(jié)點存儲haffCode[i]。
- 設(shè)置HaffCode[i]的開始位置以及權(quán)值。
代碼
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
const int MaxValue = 10000;//初始設(shè)定的權(quán)值最大值
const int MaxBit = 4;//初始設(shè)定的最大編碼位數(shù)
const int MaxN = 10;//初始設(shè)定的最大結(jié)點個數(shù)
typedef struct HaffNode{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;
typedef struct Code//存放哈夫曼編碼的數(shù)據(jù)元素結(jié)構(gòu)
{
int bit[MaxBit];//數(shù)組
int start; //編碼的起始下標(biāo)
int weight;//字符的權(quán)值
}Code;
//1.
//根據(jù)權(quán)重值,構(gòu)建哈夫曼樹;
//{2,4,5,7}
//n = 4;
void Haffman(int weight[],int n,HaffNode *haffTree){
int j,m1,m2,x1,x2;
//1.哈夫曼樹初始化
//n個葉子結(jié)點. 2n-1
for(int i = 0; i < 2*n-1;i++){
if(i<n)
haffTree[i].weight = weight[i];
else
haffTree[i].weight = 0;
haffTree[i].parent = 0;
haffTree[i].flag = 0;
haffTree[i].leftChild = -1;
haffTree[i].rightChild = -1;
}
//2.構(gòu)造哈夫曼樹haffTree的n-1個非葉結(jié)點
for (int i = 0; i< n - 1; i++){
m1 = m2 = MaxValue;
x1 = x2 = 0;
//2,4,5,7
for (j = 0; j< n + i; j++)//循環(huán)找出所有權(quán)重中，最小的二個值--morgan
{
if (haffTree[j].weight < m1 && haffTree[j].flag == 0)
{
m2 = m1;
x2 = x1;
m1 = haffTree[j].weight;
x1 = j;
} else if(haffTree[j].weight<m2 && haffTree[j].flag == 0)
{
m2 = haffTree[j].weight;
x2 = j;
}
}
//3.將找出的兩棵權(quán)值最小的子樹合并為一棵子樹
haffTree[x1].parent = n + i;
haffTree[x2].parent = n + i;
//將2個結(jié)點的flag 標(biāo)記為1,表示已經(jīng)加入到哈夫曼樹中
haffTree[x1].flag = 1;
haffTree[x2].flag = 1;
//修改n+i結(jié)點的權(quán)值
haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
//修改n+i的左右孩子的值
haffTree[n + i].leftChild = x1;
haffTree[n + i].rightChild = x2;
}
}
/*
9.2 哈夫曼編碼
由n個結(jié)點的哈夫曼樹haffTree構(gòu)造哈夫曼編碼haffCode
//{2,4,5,7}
*/
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
{
//1.創(chuàng)建一個結(jié)點cd
Code *cd = (Code * )malloc(sizeof(Code));
int child, parent;
//2.求n個葉結(jié)點的哈夫曼編碼
for (int i = 0; i<n; i++)
{
//從0開始計數(shù)
cd->start = 0;
//取得編碼對應(yīng)權(quán)值的字符
cd->weight = haffTree[i].weight;
//當(dāng)葉子結(jié)點i 為孩子結(jié)點.
child = i;
//找到child 的雙親結(jié)點;
parent = haffTree[child].parent;
//由葉結(jié)點向上直到根結(jié)點
while (parent != 0)
{
if (haffTree[parent].leftChild == child)
cd->bit[cd->start] = 0;//左孩子結(jié)點編碼0
else
cd->bit[cd->start] = 1;//右孩子結(jié)點編碼1
//編碼自增
cd->start++;
//當(dāng)前雙親結(jié)點成為孩子結(jié)點
child = parent;
//找到雙親結(jié)點
parent = haffTree[child].parent;
}
int temp = 0;
for (int j = cd->start - 1; j >= 0; j--){
temp = cd->start-j-1;
haffCode[i].bit[temp] = cd->bit[j];
}
//把cd中的數(shù)據(jù)賦值到haffCode[i]中.
//保存好haffCode 的起始位以及權(quán)值;
haffCode[i].start = cd->start;
//保存編碼對應(yīng)的權(quán)值
haffCode[i].weight = cd->weight;
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 哈夫曼編碼!\n");
int i, j, n = 4, m = 0;
//權(quán)值
int weight[] = {2,4,5,7};
//初始化哈夫曼樹, 哈夫曼編碼
HaffNode *myHaffTree = malloc(sizeof(HaffNode)*2*n-1);
Code *myHaffCode = malloc(sizeof(Code)*n);
//當(dāng)前n > MaxN,表示超界. 無法處理.
if (n>MaxN)
{
printf("定義的n越界，修改MaxN!");
exit(0);
}
//1. 構(gòu)建哈夫曼樹
Haffman(weight, n, myHaffTree);
//2.根據(jù)哈夫曼樹得到哈夫曼編碼
HaffmanCode(myHaffTree, n, myHaffCode);
//3.
for (i = 0; i<n; i++)
{
printf("Weight = %d\n",myHaffCode[i].weight);
for (j = 0; j<myHaffCode[i].start; j++)
printf("%d",myHaffCode[i].bit[j]);
m = m + myHaffCode[i].weight*myHaffCode[i].start;
printf("\n");
}
printf("Huffman's WPS is:%d\n",m);
return 0;
}
