最优二叉树

全栈程序员-站长 • 2026年3月20日上午11:48 • 未分类 • 阅读 2

权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。
只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点
哈夫曼算法基本思想：
⑴ 初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}；
⑵ 选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；
⑶ 删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中；
⑷ 重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。
设置一个数组huffTree[2n-1]保存哈夫曼树中各点的信息，数组元素的结点结构。

其中：weight：权值域，保存该结点的权值；
lchild：指针域，结点的左孩子结点在数组中的下标；
rchild：指针域，结点的右孩子结点在数组中的下标；
parent：指针域，该结点的双亲结点在数组中的下标。
1、数组huffTree初始化，所有元素结点的双亲、左
右孩子都置为-1；
2.数组huffTree的前n个元素的权值置给定值w[n]；
3、进行n-1次合并
3.1 在二叉树集合中选取两个权值最小的根结点，
其下标分别为i1, i2；
3.2 将二叉树i1、i2合并为一棵新的二叉树k(初值为n；依次递增)；

从叶子结点到根， 逆向求每个叶子结点对应的哈夫曼编码 根据huffman树中叶子节点的个数，构造一个字符串数组，每个数组分量是一个字符串，用于存放该节点对应的huffman编码 对每个叶子节点i(i=0; i<n; i++)，进行下面的工作： 1 cd［n-1］＝′\0′； /*cd是一个字符数组，共有n个元素，即每个字符编码的长度不超过n。从右向左逐位存放编码， 首先存放编码结束符*/ 2 start=n-1; /*初始化编码起始指针*/ 3 for(c=i, p= huffTree [i].parent; p! =0; c=p, p= huffTree [p].parent) /*i是要编码的叶子节点编号，从叶子到根结点求编码*/ if(huffTree [p].LChild==c) cd［--start］=‘0’ /*左分支标0*/  else cd［--start］=‘1’; /*右分支标1*/  4 循环结束，完成一个字符的编码 5 重复上述工作，直到完成所有节点的编码 }

从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码

Char **hcode,*cd; hcode=new char *[n]; cd=new char [n * sizeof(char )]; /*分配求当前编码的工作空间*/ cd[n-1]＝’\0’; /*从右向左逐位存放编码，首先存放编码结束符*/ for(i=1; i<=n; i++) /*求n个叶子结点对应的哈夫曼编码*/ { 
    start=n-1; /*初始化编码起始指针*/ for(c=i, p=ht［i］.parent; p! =0; c=p, p=ht［p］.parent) if(ht［p］.LChild==c) cd［--start］=′0′;  else cd［--start］=′1′; /*右分支标1*/ hcode［i］=new char [n-start] /*为第i个编码分配空间*/ strcpy(hcode［i］, &cd［start］);  } } start=n-1; /*初始化编码起始指针*/ for(c=i, p=ht［i］.parent; p! =0; c=p, p=ht［p］.parent) if(ht［p］.LChild==c) cd［--start］=′0′;  else cd［--start］=′1′; /*右分支标1*/ hcode［i］=new char [n-start] /*为第i个编码分配空间*/ strcpy(hcode［i］, &cd［start］);  } }