树在编码中的应用

树在编码中的应用树的术语起源于植物学和家谱学，早在1857年，英国数学家Arthur Cay ley就发现了树。

树形结构作为一种相当重要的非线性结构，具有非常广泛的应用，特别是计算机科学和管理科学中。

例如，用树构造存储和传输数据的有效编码，用树构造最便宜的电话线连分布式计算机网络，用树模拟一系列决策完成的过程等。

本文就树在编码中的应用作简要论述，首先给出有关树的一些基础知识。

1、树的概述（1）树的定义树是无圈连通无向图。

对于一个有向图，若其基础图是树，则该有向图成为有向树。

总的来说，树是由一个集合以及在该集合上定义的一种关系构成的。

集合中的元素称为树的结点，所定义的关系称为父子关系。

父子关系在树的结点之间建立了一个层次结构。

在这种层次结构中有一个结点具有特殊的地位,这个结点称为该树的根结点,或简称为树根。

（2）树的相关概念结点的度：一个结点的儿子结点的个数称为该结点的度.一棵树的度是指该树中结点的最大度数。

叶结点：树中度为零的结点称为叶结点或终端结点。

分枝结点：树中度不为零的结点称为分枝结点或非终端结点。

内部结点：除根结点外的分枝结点统称为内部结点。

路径：如果存在树中的一个结点序列K1 , K2,…, K j ,使得结点K i是结点K i+1的父结点(1 ≤ i ≤ j ) ,则称该结点序列是树中从结点K i到结点K j的一条路径或道路.我们称这条路径的长度为 j-1 ,它是该路径所经过的边(即连接两个结点的线段)的数目.树中任一结点有一条到其自身的长度为零的路径。

祖先：如果在树中存在一条从结点K到结点M的路径,则称结点 K 是结点 M 的祖先, 也称结点M是结点K的子孙。

结点高度：树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度.树的高度是指根结点的高度。

结点的深度或层数：从树根到任一结点n有唯一的一条路径,我们称这条路径的长度为结点n的深度或层数。

根结点的深度为0,其余结点的深度为其父结点的深度加1。

深度相同的结点属于同一层。

有序树、左儿子、右兄弟：树的定义在某些结点之间确定了父子关系,我们又将这种关系延拓为祖先子孙关系。

但是树中的许多结点之间仍然没有这种关系。

例如兄弟结点之间就没有祖先子孙关系。

如果我们在树的每一组兄弟结点之间定义一个从左到右的次序,则得到一棵有序树；否则称为无序树。

设结点n的所有儿子按其从左到右的次序排列为n1, n2,…, n k ,则我们称n1是n的左儿子,并称n i是n i−1的右兄弟( i = 2,3,…,k)。

森林：森林是m(m>0)棵互不相交的树的集合。

如果我们删去一棵树的树根,留下的子树就构成了一个森林。

当我们删去的是一棵有序树的树根时,留下的子树也是有序的,这些树组成一个树表。

在这种情况下,称这些树组成的森林为有序森林。

（3）二叉树二叉树是一类非常重要的树形结构,它可以递归地定义如下：二叉树 T 是有限个结点的集合,它或者是空集,或者由一个根结点 u 以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。

若用 n , n1和n2分别表示 T , u(1)和u(2)的结点数,则有 n = 1 + n1 + n2。

u(1)和u(2)有时分别称为 T 的第一和第二子树。

因此,二叉树的根可以有空的左子树或空的右子树,或者左、右子树均为空。

二叉树有 5 种基本形态,如下图所示(其中□表示空)：在二叉树中,每个结点至多有两个儿子,并且有左、右之分。

因此任一结点的儿子只有4 种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子。

二叉树与度数不超过 2 的树不同,与度数不超过 2 的有序树也不同。

在有序树中,虽然一个结点的儿子之间是有左右次序的,但若该结点只有一个儿子时,就无须区分其左右次序。

而在二叉树中,即使是一个儿子也有左右之分。

由此可见,尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形.2、树在编码中的应用（1）哈夫曼编码问题在电报通讯中,电文是以二进制的 0，1 序列传送的。

在发送段,需要将电文中的字符转换成二进制的 0，1 序列(编码)，在接受端则要将收到的 0，1 串转化为对应的字符序列 (译码)。

最简单的编码方法是等长编码，例如，若电文是英文,则电文的字符串仅由 26 个英文字母组成，需要编码的字符集合(A，B,…，Z ) ，采用等长编码时,每个字符用 5 位二进制位串表示即可(25>26)。

在接收端,只要按 5 位分割进行译码就可得到对应的文字。

众所周知，字符集中的字符被使用的频率是非均匀的，例如，英文中E和T的使用较Q和Z 要频繁得多。

因此，若让使用频率高的字符的编码尽可能短，则可使传送的电文总长缩短.然而采用这种不等长编码可能使译码长生多意性的电文，例如，假设用 00 表示 E ,用 01 表示 T ,用 0001 表示 W ,则当接收到信息串 0001 时,无法确定原电文是ET还是W，产生该问题的原因是E的编码与W的编码的开始部分(前缀)相同。

因此，若对某字符集进行不等长编码，则要求字符集中任何一字符的编码都不是其他字符的编码的前缀, 这种编码叫做前缀(编)码。

显然，等长编码是前缀码。

什么样的前缀码才能使得电文总长最短呢？这就是哈夫曼树在编码中的应用(哈夫曼编码)。

（2）哈夫曼树的定义①在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。

通路中分支的数目称为路径长度。

若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L -1。

结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为 WPL。

②哈夫曼树的定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。

（3）哈夫曼树的构造假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。

n 个权值分别设为w1，w2，…，w n，则哈夫曼树的构造规则为：Ⅰ）将w1，w2，…，w n看成是有 n 棵树的森林(每棵树仅有一个结点)；Ⅱ）在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树, 且新树的根结点权值为其左、右子树根结点权值之和；Ⅲ）从森林中删除选取的两棵树,并将新树加入森林；Ⅳ）重复Ⅱ）、Ⅲ）步,直到森林中只剩一棵树为止,该树即为我们所求得的哈夫曼树。

下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为 1，5，7，3，则构造哈夫曼树过程如下图所示：从上图可知，n 个权值构造哈夫曼树需n-1次合并，每次合并，森林中的树数目减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。

（4）哈夫曼树的应用①哈夫曼编码通信中，可以采用 0，1 的不同排列来表示不同的字符，称为二进制编码。

而哈夫曼树在数据编码中的应用，是数据的最小冗余编码问题,它是数据压缩学的基础。

若每个字符出现的频率相同，则可以采用等长的二进制编码，若频率不同，则可以采用不等长的二进制编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小冗余编码的问题。

而哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。

例如，给定权{1，5，7，3}，得到的哈夫曼树及编码见下图(假定权值就代表该字符名字)。

②哈夫曼译码在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。

（5）应用实例以下给出一个实例来对哈夫曼编码和译码进行具体说明：①基本要求程序要求实现以下功能：1）统计文本文件中各字符的出现次数（涉及读文件，统计字符个数）；2）对文件中的字符进行哈夫曼编码，并存储入字符编码文件；3）根据字符编码文件对文本文件内容进行编码；4）根据字符编码文件和已编码文件的内容进行译码；5）能够输出原文、编码表、文本文件编码、译文。

②源程序及简要分析//Huffman.cpp 源代码如下：#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_C 256 //定义最大字符数#define MAX_N 512 //定义最大 Huffman 节点个数#define N 50/*哈夫曼树的存储结构*/typedef struct {char ch; //字符int weight; //字符权重int lchild; //左子int rchild; //右子int parent; //双亲} THNODE;typedef THNODE HuffmanT[MAX_N];/******哈夫曼编码表的存储结构*****/typedef struct {char ch; //存储字符char bits[MAX_C + 1]; //字符编码位串} CodeNode;typedef CodeNode HuffmanCode[MAX_C];HuffmanCode H;/*********全局变量**********/int n; //指示待编译文件的字长char filename[20];/*初始化 Huffman 树*/void InitHT(HuffmanT T){ int i;for (i = 0; i < MAX_N; i++){ T[i].ch = '\0';T[i].weight = 0;T[i].lchild = -1;T[i].rchild = -1;T[i].parent = -1;}}/*找到权重最小的叶子*/void SelectMin(HuffmanT T, int n, int &p1, int &p2) { int i;int j;for (i = 0; i < 2 * n -1; i++){ if (T[i].parent == -1 && T[i].weight > 0){ p1 = i;break;}}for (j = i + 1; j < 2 * n - 1; j++){ if (T[j].parent == -1 && T[j].weight > 0){ p2 = j;break;}for (i = 0; i < 2 * n - 1; i++){ if ((T[p1].weight > T[i].weight) && (T[i].parent == -1) && (p2 != i) && (T[i].weight > 0))p1 = i;}for (j = 0; j < 2 * n - 1; j++){ if ((T[p2].weight > T[j].weight) && (T[j].parent == -1) && (p1 != j) && (T[j].weight > 0))p2 = j;}}/*******加载文件*******/void LoadHuffmanFile(HuffmanT T){ unsigned int i;int j = 0;char c;int a[MAX_C];FILE *fp;printf("Input file name: ");scanf("%s", filename);if ((fp = fopen(filename, "rb")) == NULL){ printf("Can't open %s\n", filename);exit( 0 );}for (i = 0; i < MAX_C; i++)a[i] = 0;fseek(fp, 0, SEEK_SET);while ( 1 ) //( !feof(fp) ){ fread(&c, sizeof(unsigned char), 1, fp);if (feof(fp)) break;a[(unsigned int)c]++;}fclose(fp);/*统计输入文件的字符及其权重并存放到树 T[]*/for (i = 0; i < MAX_C; i++){ if (a[i] != 0){ T[j].ch = (unsigned char)i;T[j++].weight = (unsigned int)a[i];}n = j;}/*******构造 huffam 树，T[2 * n - 1]为其根********/void CreatHT(HuffmanT T){ int i,p1,p2;LoadHuffmanFile(T); //加载被编码文件for (i = n; i < 2 * n - 1; i++){ SelectMin(T, i - 1, p1, p2);T[p1].parent = T[p2].parent = i;T[i].lchild = p1;T[i].rchild = p2;T[i].weight = T[p1].weight + T[p2 ].weight;}}/*根据 Huffman T 求 Huffman 编码表 H*/void CharSetHuffmanEncoding(HuffmanT T, HuffmanCode H){ int c; //指示 T 中孩子的位置int p; //指示 T 中双亲的位置int i; int start; //指示编码在 cd 中的位置char cd[N]; //临时存放编码for (i = 0; i < n; i++) //依次求叶子的编码{ H[i].ch = T[i].ch; //读入叶子 T[i]对应的字符if (i==0 || i==1) start=n;else start=n-i+1;cd[--start]='\0'; //编码起始位置的初值c = i; //从叶子 T[i]开始回溯while ((p = T[c].parent) >= 0) //直到回溯到 T[c]是树根位置{ cd[--start] = (T[p].lchild == c) ? '0' : '1';c = p;}strcpy(H[i].bits, &cd[start]); //复制临时编码到编码表中}}/*对文件编码，将结果保存到 codefile.txt 中*/void EncodingHuffmanT(HuffmanT T, HuffmanCode H){ char c; FILE *in,*fp;int j,l;char encodefile[20],temp[MAX_C];if ((in = fopen(filename, "rb")) == NULL){ printf("Read %s fail!\n", encodefile);exit(1);}CharSetHuffmanEncoding(T, H);printf("Input encode file name: ");gets( encodefile );if ((fp = fopen(encodefile, "wb")) == NULL){ printf("Write %s fail!\n", encodefile); exit(1);}fread(&c, sizeof(unsigned char), 1, in);fwrite(&c, sizeof(unsigned char), 1, fp);fseek(in, 0, SEEK_SET);fseek(fp, 0, SEEK_SET);while ( 1 )//( !feof( in )){ fread(&c, sizeof(unsigned char), 1, in);if (feof(in)) break;for (j = 0; j < n; j++){if (c == H[j].ch){ l = 0;while (H[j].bits[l] != '\0'){ temp[l] = H[j].bits[l]; l++;}int m = 0;while ( l-- ){fwrite(&temp[m++], sizeof(unsigned char), 1, fp);}} } }fclose(fp);printf("Encoding file has saved into %s!\n", encodefile); }/*根据 Huffman 编码、译码*/void DecodingHuffmanT(HuffmanT T, HuffmanCode H){ int i; //指示 Huffman tree 叶子个数FILE *fp,*fp1; char ch,ch1[20],ch2[20];printf("Input encode file name: ");scanf("%s", ch1);printf("Input decode file name: ");scanf("%s", ch2);fp = fopen(ch1, "rb");fp1 = fopen(ch2, "wb");//根据 Huffman 树对 Huffman 编码译码i = 2 * n - 2;fseek(fp, 0L, SEEK_SET);fseek(fp1, 0L, SEEK_SET);while (!feof(fp)){ fread(&ch, sizeof(unsigned char), 1, fp);if (ch == '0') //若编码为 o，则找此结点的左子树；i = T[i].lchild;if (ch == '1') //若编码为１，则找此结点的右子树；i = T[i].rchild;if (i < n) { fwrite(&T[i].ch, sizeof(unsigned char), 1, fp1); i = 2 * n - 2; } }fclose(fp);fclose(fp1);printf("Decoding accomplished!\nThe result has save input %s.\n",ch2); getchar();}/*打印 Huffman 权重表*/void PrintHuffmanT(HuffmanT T){ int i;FILE *fp;if ((fp = fopen("treeprint.txt", "wb")) == NULL){ printf("Open treeprint.txt fail!\n"); exit(1); }printf("\nLeaf&weight of the Huffman tree is below:\n");for (i = 0; i < n ; i++){ if (i % 5 == 0 && i > 0)printf("\n");if (T[i].weight > 0){ fprintf(fp, "%c:%d ", T[i].ch, T[i].weight);printf("%c: %d ", T[i].ch, T[i].weight);}}fclose(fp);printf("\nLeaf&weight of the Huffman tree saved in treeprint.txt\n\n");}/*打印 Huffman 编码表*/void PrintHuffmanH(HuffmanT T, HuffmanCode H){ int i;FILE *fp;CharSetHuffmanEncoding(T, H);if ((fp = fopen("codeprint.txt", "wb")) == NULL){printf("Open codeprint.txt fail!\n"); exit(1); }for (i = 0; i < n; i ++){ if (i % 10 == 0 && i > 0)printf("\n");printf("%c: %s\n", T[i].ch, H[i].bits);fprintf(fp, "%c:%s ", T[i].ch, H[i].bits);}fclose(fp);printf("\nHuffman tree code saved in codeprint.txt!\n\n");}/*主菜单（提供相关的操作提示）*/void MainMenue(){ fflush( stdin );printf("\n********************** Main Menue **************************\n"); printf("** **\n"); printf("** 1. Load to be dealt file. **\n"); printf("** 2. Show Huffman code list. **\n"); printf("** 3. Show Huffman weight list. **\n"); printf("** 4. Encoding Huffman file. **\n"); printf("** 5. Decoding Huffman file. **\n"); printf("** 6. Exit. **\n"); printf("** **\n"); printf("************************************************************\n");}/*主函数（用个 while 循环和 switch 选择结构进行进行循环交互性操作）*/int main(){ int flag = 1;char ch[10];HuffmanT T; //定义 Huffman 树HuffmanCode H; //定义 Huffman 编码表InitHT(T); //初始化 Huffman 树while ( flag ){ MainMenue();printf("Please input your choice(1~6): ");gets( ch );switch ( ch[0] ){ case '1': CreatHT(T); break;case '2': PrintHuffmanH(T, H); break;case '3': PrintHuffmanT(T); break;case '4': EncodingHuffmanT(T, H); break;case '5': DecodingHuffmanT(T, H); break;case '6': exit(1);default: printf("Input error!\n"); break;}}return 0;}。