最优二叉树(哈夫曼树)

出处：最优二叉树

最优二叉树(哈夫曼树)

哈夫曼树相关的几个名词

路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。

路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i – 1 。图 1 中从根结点到结点 c 的路径长度为 3。

结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。

结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

哈夫曼树的介绍

当建立好哈夫曼树，我们要将其进行编码，要将权值表示改为0,1表示，叶子节点的左边改为0，右边改为1

这样子比较方便在网络上传输，因为哈夫曼树的研究目的就是为了解决早期远距离通信(电报)的数据传输的优化问题。

接下来我们来分析一下，这样做对数据的优化体现在哪里？
例如，如下图。

假如们要传输一端报文：BADCADFEED,那么我们可以用相应的二进制表示
字母 a b c d e f
二进制字符 000 001 010 011 100 101

0和1是比较容易混淆的，为了设计出来长度不相等的编码，我们就必须有一种规定，就是任一字符的编码都不是另一个字符的编码的前缀，这种编码被称为前缀编码。

我们可以发现通过哈夫曼编码形成的每个节点的编码例如：1000,1000混淆的10,100的类似的编码了。

哈夫曼树的节点存储结构

//哈夫曼树结构 typedef struct { 
    unsigned int weight; //权重 unsigned int parent, lchild, rchild; //树的双亲节点，和左右孩子 }HTNode, *HuffmanTree; typedef char** HuffmanCode;

1、建树，根据节点的权重建立，每次从的序列中比较出两个最小的权重，建立出一颗树，然后再从剩余的节点中继续抽取节点权重最小的节点，继续建树，这边我采用的是迭代方式；

2、解码输出，采用的是叶子节点逆序遍历到根节点，将0,1存储到字符数组里面，然后再将数组输出。

里面是具体实现的代码，里面也有注释

//函数声明 int Min(HuffmanTree T, int i); //求i个节点中的最小权重的序列号，并返回 void Select(HuffmanTree T, int i, int& s1, int& s2); //从两个最小权重中选取最小的(左边)给s1，右边的给s2 void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n);//哈夫曼编码与解码

函数的具体实现算法(Min和Select)：

//返回i个节点中权值最小的树的根节点的序号，供select()调用 int Min(HuffmanTree T, int i) { 
    int j, flag; unsigned int k = UINT_MAX; //%d-->UINT_MAX = -1,%u--->非常大的数 for (j = 1; j <= i; j++) if (T[j].weight < k && T[j].parent == 0) k = T[j].weight, flag = j; // T[flag].parent = 1; //将parent标志为1避免二次查找 return flag; //返回节点的下标 } void Select(HuffmanTree T, int i,int& s1,int& s2) { 
    //在i个节点中选取2个权值最小的树的根节点序号，s1为序号较小的那个 int j; s1 = Min(T,i); s2 = Min(T,i); if (s1 > s2) { 
    j = s1; s1 = s2; s2 = j; } }

解码算法1(从根节点遍历赫夫曼树逆序输出)：

//HuffmanCode代表的树解码二进制值 void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n) { 
    //w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC int m, i, s1, s2, start; unsigned c, f; char* cd; //分配存储空间 HuffmanTree p; if (n <= 1) return; //n个字符(叶子节点)有2n-1个树节点，所以树节点m m = 2 * n - 1; HT = (HuffmanTree)malloc((m + 1)*sizeof(HTNode)); //0号元素未用 //这一步是给哈夫曼树的叶子节点初始化 for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w) { 
    (*p).weight = *w; (*p).lchild = 0; (*p).rchild = 0; (*p).parent = 0; } //这一步是给哈夫曼树的非叶子节点初始化 for (; i <= m; ++i, ++p) (*p).parent = 0; // /* 做完准备工作后 ，开始建立哈夫曼树 // for (i = n + 1; i <= m; i++) { 
    //在HT[1~i-1]中选择parent=0且weigh最小的节点，其序号分别s1,s2 Select(HT, i - 1, s1, s2); //传引用 HT[s1].parent = HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } // /* 从叶子到根逆求每个叶子节点的哈夫曼编码 */ // //分配n个字符编码的头指针向量，（[0]不用） HC = (HuffmanCode)malloc((n + 1)*sizeof(char*)); cd = (char*)malloc(n*sizeof(char)); //分配求编码的工作空间 cd[n - 1] = '\0'; //结束符 for (i = 1; i <= n; i++) //每个节点的遍历 { 
    start = n - 1; c = i; f = HT[i].parent; //c表示当前节点的下标 while (f != 0) { 
    //父节点不为0，即不为根节点 --start; if (HT[i].lchild == c)cd[start] = '0'; else cd[start] = '1'; c = f; f = HT[f].parent; //迭代向上回溯 } HC[i] = (char*)malloc((n - start)*sizeof(char)); //生成一个块内存存储字符 //为第i个字符编码分配空间 strcpy(HC[i], &cd[start]); //从cd赋值字符串到cd } free(cd); //释放资源 }

解码算法2(从根节点正序遍历赫夫曼树输出)：

//利用无栈递归的思想 void HuffmanCoding2(HuffmanTree &HT, HuffmanCode &HC, int* weight, int n){ 
    int m, i, s1, s2; unsigned c, cdlen; HuffmanTree p; char* cd; //编码空间 if (n <= 1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m + 1)*sizeof(HTNode)); //1开始到m+1//总共2n-1 for (p = HT + 1, i = 1; i <= n; ++i, ++weight, ++p) { 
    // HT[i].weight = *weight; // HT[i].parent = 0; // HT[i].lchild = 0; // HT[i].rchild = 0; (*p).weight = *weight; (*p).parent = 0; (*p).lchild = 0; (*p).rchild = 0; } for (; i <= m; ++i,++p) (*p).parent = 0; // /* 将树的叶子节点和即将存储的双亲节点初始化后，开始建立赫夫曼树 */ // for (i = n + 1; i <= m; ++i) //i++ --->++i { 
    Select(HT, i - 1, s1, s2); HT[s1].parent = HT[s2].parent=i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } c = m; //c = 2*n-1 HC = (HuffmanCode)malloc((n + 1)*sizeof(char*)); cd = (char*)malloc(n*sizeof(char)); cdlen = 0; for (i = 1; i <= m; i++) HT[i].weight = 0; //将所有的权重置0 //这是一个迭代的过程 while (c){ 
    if (HT[c].weight == 0){ 
    //向左 HT[c].weight = 1; if (HT[c].lchild != 0){ 
    c = HT[c].lchild; cd[cdlen++] = '0'; } else if (HT[c].rchild == 0) { 
    cd[cdlen] = '\0'; HC[c] = (char*)malloc(sizeof(char)*(cdlen + 1)); strcpy(HC[c], cd); //复制编码串  } } else if (HT[c].weight == 1) { 
    //向右遍历 HT[c].weight = 2; if (HT[c].rchild != 0){ 
    //存在右孩子 c = HT[c].rchild; cd[cdlen++] = '1'; } } else{ 
    //当HT[c].weight = 2; HT[c].weight = 0; c = HT[c].parent; //退回到父节点 cdlen--; //编码的长度-1 } } }

主函数具体实现：

int main() { 
    HuffmanTree HT; HuffmanCode HC; int *w, n, i; printf("请输入权值的个数(>1):"); scanf_s("%d",&n); w = (int*)malloc(n*sizeof(int)); printf("请依次输入%d个权值(整形):\n",n); for (i = 0; i <= n - 1;i++) scanf_s("%d",w+i); HuffmanCoding(HT, HC, w, n); 　　　　 for (i = 1; i <= n;i++) puts(HC[i]); return 0; }