哈夫曼树的创建和编码浅析
哈夫曼树的创建和编码
项目忙的要死，博客停了两天，做外包的真不好受，还是做产品的强。软件最后最值钱的不是代码，而是相关的文档，文档清楚，依葫芦画瓢照做出来应该不难。项目结束了至少要整理出需求规格说明书，设计文档，用户使用说明书，开发进度表，投标书，工作说明书等文档。
本文根据《数据结构与算法》(C语言版)(第三版) 整理。
本博文作为学习资料，源代码是VC++ 6.0上可执行程序，我挪到了VS2010中执行。
1.哈夫曼树又称最优二叉树，是一类带权路径长度最短的树。
对于最优二叉树，权值越大的结点越接近树的根结点，权值越小的结点越远离树的根结点。
最优二叉树的构造算法步骤：
(1)根据给定的n个权值w1,w2,...,wn构成n棵二叉树森林F={T1,T2,...,Tn}，其中每一棵二叉树Ti中都只有一个权为wi的根结点，其左、右子树为空。
(2)在森林F中选出两棵根结点权值最小的树作为一棵新二叉树的左、右子树，新二叉树的根结点的权值为其左、右子树根结点的权值之和。
(3)从F中删除这两棵二叉树，同时把新二叉树加入到F中。
(4)重复步骤(2)、(3),直到F中只含有一棵树为止，此树便为最优二叉树。
哈夫曼树的结点类型声明：
struct TreeNode
typedef struct TreeNode HFTreeN
typedef HFTreeNode HuffmanT
哈夫曼树的构造算法：
#define MaxSize 1000
//叶子数目
void Select(HuffmanTree *HT, int g, int &s1, int &s2);
void CreateHuffmanTree(HuffmanTree T[MaxSize], int n)
int i,p1,p2;
//计算哈夫曼树的结点大小
for(i=1; i&&
2.哈夫曼编码
哈夫曼编码是一种变长编码。其定义如下：
对于给定的字符集D={d1,d2,...,dn}及其频率分布F={w1,w2,...,wn}，用d1,d2,...,dn作为叶结点，w1,w2,...,wn作为结点的权，利用哈夫曼算法构造一棵最优二叉树，将树中每个分支结点的左分支标上&0&；右分支标上&1&，把从根到每个叶子的路径符号(&0&或&1&)连接起来，作为该叶子的编码。
哈夫曼编码是在哈夫曼树的基础上求出来的，其基本思想是：从叶子结点di(0&=i<n)出发，向上回溯至根结点，依次求出每个字符的编码。
哈夫曼编码的回溯步骤如下：
(1)选出哈夫曼树的某一个叶子结点。
(2)利用其双亲指针parent找到其双亲结点。
(3)利用找到的双亲结点的指针域中的lchild和rchild，判断该结点是双亲的左孩子还是右孩子。若该结点是其双亲结点的左孩子，则生成代码0；若该结点是其双亲结点的右孩子，则生成代码1。
(4)由于生成的编码与要求的编码反序，将所生成的编码反序。
(5)重复步骤(1)~(4)，直到所有结点都回溯完。
反序方法：首先将生成的编码从后向前依次存放在一个临时的一维数组中，并设一个指针start指示编码在该一维数组中的起始位置。当某个叶子结点的编码完成时，从临时的一维数组的start处将编码复制到该字符对应的bits中即可。
哈夫曼编码的存储结构：&
struct CodeNode
//存储字符
char bits[n+1];
//存放编码位串
typedef struct CodeNode CodeN
typedef CodeNoe HUffmanCode[n];
哈夫曼编码的算法：
void CharSetHuffmanEncoding(HuffmanTree T, HuffmanCode H)
//根据哈夫曼树T求哈夫曼编码表H
char cd[n+1];
cd[n]=&#39;\0&#39;;
for(i=0; i0)
if(T[p].lchild==c)
cd[--start]=&#39;0&#39;;
cd[--start]=&#39;1&#39;;
//继续上溯
strcpy(H[i].bits, &cd[start]);
//复制编码位串
3.哈夫曼解码
哈夫曼解码过程:从哈夫曼树的根结点出发，依次识别电文的中的二进制编码，如果为0，则走向左孩子，否则走向右孩子，走到叶结点时，就可以得到相应的解码字符。
算法如下：
void CharSetHuffmanDecoding(HuffmanTree T, char* cd, int n)
int p=2*n-2;
//从根结点开始
//当要解码的字符串没有结束时
while(cd[i]!=&#39;/0&#39;)
//当还没有到达哈夫曼树的叶子并且要解码的字符串没有结束时
while((T[p].lchild!=0 && T[p].rchild != 0) && cd[i] != &#39;\0&#39;)
if(cd[i] == &#39;0&#39;)
//如果是0，则叶子在左子树
//如果是1，则叶子在左子树
//如果到达哈夫曼树的叶子时
if(T[p].lchild == 0 && T[p].rchild == 0)
printf(&%c&, T[p].ch);
p = 2*n-1;
//如果编号为p的结点不是叶子，那么编码有错
printf(&\n解码出错! \n&);
printf(&\n&);
4.哈夫曼树的创建和哈夫曼编码程序：
在VS2010中新建Win32 控制台应用程序的项目：HuffmanTree，创建结果如下图：
// HuffmanTree.cpp : 定义控制台应用程序的入口点。
#include &stdafx.h&
typedef struct HuffmanTree
int parent, lchild,
} HuffmanT
typedef struct CodeNode
char bits[4+1];
void SelectMin(HuffmanTree tree[], int len, int * pos1, int* pos2)
int min=255;
for(i=0; itree[i].weight)
min=tree[i].
for(j=0; jtree[j].weight)
min=tree[j].
void CreateHuffmanTree(HuffmanTree tree[], int n)
int m=2*n;
for(i=n; i
Ctrl+F5执行HuffmanTree.cpp结果如下图：
</n)出发，向上回溯至根结点，依次求出每个字符的编码。数据结构-结构体的声明
一般来说，知道了各种存储结构的结构体，或者各种算法(其实算法是在各种特定的存储结构下实现)所需的结构体，所以我觉得记住或者牢记各种场合，各种情形下所需要的存储结构的结构体，对算法的创建和表达就会轻松和容易许多。
一、顺序存储
& &1、 顺序表
&&&&&&&&#define
MAXSIZE 100
typedef struct
datatype a[MAXSIZE];
}sequence_
2、栈（顺序栈）
&&&&&&&&#define
MAXSIZE 100
typedef struct
datatype a[MAXSIZE];
}sequence_
3、队列（顺序队列，顺序循环队列）
&&&&&&&&#define
MAXSIZE 100
typedef struct
datatype a[MAXSIZE];
&&&&&&&&&&int
}sequence_
&其中循环队列判满条件：(rear+1)%MAXSIZE=front；判空条件：rear=front
二、链式存储
单链表（带头结点的单链表，循环单链表）
typedef struct link_node
struct link_node *
typedef struct dlink_node
struct link_node *llink,*
typedef struct link_node
struct link_node *
4、链式队列
typedef struct link_node
struct link_node *
typedef struct
node *front,*
三、字符串
1、顺序串：模式匹配（朴素的模式匹配算法，KMP算法）
&&&&&&&&#define
MAXSIZE 100
typedef struct
&&&&&&&&{&char
str[MAXSIZE];
typedef struct node
struct node *
typedef linkstrnode *
3、N维数组：行优先存储，列优先存储
(三维数组)
typdef struct
datatype *//数组存储区的首地址指针
int index[3];//存放三维数组各维的长度
int c[3]; //存放三维数组各维的ci值
1、双亲表示法
&&&&&&&&#define
MAXSIZE 100
typedef&//节点值的类型
typedef struct node//结点类型
//结点双亲的下标
typedef struct tree
{& node treelist[MAXSIZE];//存放结点的数组
&&&&&&&&&&
int length,//树中实际所含结点的个数，根节点的位置
&&&&&&&&}//树的类型
2、孩子表示法（指针方式）
&&&&&&&&#define
m 3//树的度数
typedef&//节点值的类型
typedef struct node
struct node *child[m];//指向子女的指针数组
3、孩子表示法（数组方式）
&&&&&&&&#define
m 3//树的度数
#define MAXSIZE 20//存放树结点的数组大小
typedef&//结点值的类型
typedef struct node//结点类型
int child[m];
treenode tree[MAXSIZE];//存储树结点的数组
//根节点的下标
//树中实际所含结点的个数
4、孩子表示法（链式方式）
#define MAXSIZE 50
typedef&//结点值的类型
typedef struct chnode//孩子结点的类型
struct chnode *
typedef struct//树中每个结点的类型
&&&&&&&&&&chpoint
//指向第一个子女结点的指针
typedef struct//树的类型
{ node treelist[MAXSIZE];
int length,//树中实际所含结点的个数，根结点的位置
5、孩子兄弟表示法
typedef&//结点值的类型
typedef struct node//孩子结点的类型
struct node *firstchild,*
6、树的括号表示
7、树的层号表示
五、二叉树
1、完全二叉树
#define MAXSIZE 20
typedef&//结点值的类型
datatype tree[MAXSIZE];
//树中实际所含结点的个数
2、一般二叉树（顺序存储）
#define MAXSIZE 20
typedef&//结点值的类型
typedef struct
int lchild,//存放左，右子女的下标
//存放双亲结点的下标（当需要带双亲指示时声明）
node tree[MAXSIZE];
&&&&&&&&int
n;//树中实际所含结点的个数
&&&&&&&&int
//存放根结点的下标
3、链式存储
typedef&//结点值的类型
typedef struct node
&&&&&&&&&&struct
node&*lchild,*//存放左，右子女的下标
int *//指向双亲结点的指针（当需要带双亲指示时声明）
typedef bintnode *
//指向二叉树根节点的指针
1、邻接矩阵类型定义
#define FINITY 5000//用5000表示无穷大
#define M 20//最大顶点数
typedef&//顶点值的类型
//权值类型
typedef struct
vertextype vex[M];//顶点信息域
edgetype deges[M][M];//邻接矩阵
int n,e;//图中顶点总数，边数
2、邻接表类型定义
#define M 20//最大顶点数
typedef&//顶点信息数据类型
typedef struct node//边表结点
struct node *
typedef struct vnode//头结点类型
//顶点信息
edgenode *//邻接链表 头指针
typedef struct//邻接表类型
vertexnode adjlist[M];//存放头结点的顺序表
int n,e;//顶点数，边数
1、顺序检索，二分法检索(存储有序)
&&&&&&&&#define
MAXSIZE 100
typedef struct
datatype a[MAXSIZE];
2、分块检索
&&&&&&&&#define
MAXSIZE 100
typedef struct
datatype a[MAXSIZE];
typedef struct
//块中最大值
3、二叉排序树
typedef&//结点值的类型
typedef struct node
&&&&&&&&&&struct
node&*lchild,*
typedef bsnode *
4、Huffman树
typedef struct node
&&&&&&&&&&struct
node&*lchild,*rchild,*
typedef hufnode *
&&&&&&&&#define
MAXSIZE 100//文件中记录个数的最大值
typedef&//排序码类型
typedef struct
&&&&&&&&&&int
//还可定义记录中除了排序码外的其他域
typedef struct
recordtype r[MAXSIZE+1];
&&&&&&&&&&int
//待排序文件中记录的个数
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。&&&&&&&&&&&&&&&
C语言实例编程:常用算法之哈夫曼算法
　　#include
　　#include
　　#include
　　#include
　　#include
　　/*声明两种链表结构----start*/
　　struct node_a{ /*链表1-----作用：用来统计文件中字符的个数和种类（通过count）*/
　　struct node_a *
　　typedef struct node_a node,*
　　list head=NULL;
　　struct nodeb{ /*链表2-----作用：用来建立用相应的编码代替字符的新文件*/
　　struct nodeb *
　　typedef struct nodeb node_b,*list_b; /*jiang bianma xieru wenjian*/
　　list_b head_b=NULL;
　　/*声明两种链表结构----end*/
　　/*哈夫曼算法种相关的3种结构的声明-----start*/
　　struct forest{
　　struct alphabet{
　　char *
　　struct tree{
　　typedef struct tree *tree_ptr,tree_
　　typedef struct forest *forest_ptr,forest_
　　typedef struct alphabet *alphabet_ptr,alphabet_
　　tree_ptr tree1;
　　forest_ptr forest1;
　　alphabet_ptr alphabet1;
　　int lasttree,
　　int least,
　　/*哈夫曼算法种相关的3种结构的声明-----end*/
　　/**************stack difination start****************/
　　struct stacknode{
　　char *bian_
　　struct stacknode *
　　typedef struct stacknode stack_
　　typedef stack_node *
　　link top=NULL;
　　void push(char *item){
　　if(top!=NULL){
　　p=(link)malloc(sizeof(stack_node));
　　if(p==NULL){
　　printf("Memory allocation error!");
　　　　　　　　　　　　
免责声明：
① 凡本站注明“稿件来源：中国教育在线”的所有文字、图片和音视频稿件，版权均属本网所有，任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本站协议授权的媒体、网站，在下载使用时必须注明“稿件来源：中国教育在线”，违者本站将依法追究责任。
② 本站注明稿件来源为其他媒体的文/图等稿件均为转载稿，本站转载出于非商业性的教育和科研之目的，并不意味着赞同其观点或证实其内容的真实性。如转载稿涉及版权等问题，请作者在两周内速来电或来函联系。
| 京ICP备号 |
CERNET Corporation二叉树相关算法：重构与层次遍历 - 简书
二叉树相关算法：重构与层次遍历
二叉树的重构——需要至少有中序遍历序列，以及前序后序任意一个
基本思路：以下以L表示左子树/左孩子，V表示当前节点，R表示右子树/右孩子，这里以中序+后序为例
中序遍历序列顺序为LVR，后序遍历序列顺序为LRV，因此可以直接从后序遍历序列中找出根节点V，即序列中的最后一个元素
然后以V为分界，对中序遍历序列进行分割——可以很容易地看出，V左侧即为左子树的中序遍历序列，右侧即为右子树的中序遍历序列
同样的长度可以用于分割后序遍历序列，依次得到左右子树的两个序列
接下来对两个子树进行递归调用即可
演示代码：
typedef struct Node {
int post[31]; //LRV
int in[31]; //LVR
void buildTree(int p1, int p2, int i1, int i2, Node* &treeNode) {
if (treeNode==NULL)
treeNode = new Node();
if (p1&p2||i1&i2)
//cout && “flag”&&
treeNode-&lchild = NULL;
treeNode-&rchild = NULL;
treeNode-&data = post[p2];
//cout &&post[p2] &&
int count = p1;
for ( i =i1 ; i &=i2; i++, count++)
if (post[p2] == in[i]) { //V found
buildTree(p1, count – 1, i1, i – 1, treeNode-&lchild);
buildTree(count, p2 – 1, i + 1, i2, treeNode-&rchild);
}//注意边界值
二叉树的层次遍历：
新建一个辅助队列，将根节点入队，然后出队
对根节点进行访问——同时，如果根节点存在后代的话，按照左右孩子的顺序依次入队
循环进行此操作，直至整个队列彻底为空再停止
演示代码：
queue&Node*&
level.push(tree);
vector&int&
while (!level.empty())
if (level.front()-&data)
int number = level.front()-&
cout && number &&
output.push_back(number);
if (level.front()-&lchild!=NULL)
level.push(level.front()-&lchild);
if (level.front()-&rchild!=NULL)
level.push(level.front()-&rchild);
level.pop();
The Angry Toad