网站建设思维导图,28网站建设,厦门成品网站,杭州学校网站建设文章目录 数据结构—基础知识#xff1a;哈夫曼树哈夫曼树的基本概念哈夫曼树的构造算法哈夫曼树的构造过程哈夫曼算法的实现算法#xff1a;构造哈夫曼树 数据结构—基础知识#xff1a;哈夫曼树
哈夫曼树的基本概念
哈夫曼#xff08;Huffman#xff09;树又称最优树哈夫曼树哈夫曼树的基本概念哈夫曼树的构造算法哈夫曼树的构造过程哈夫曼算法的实现算法构造哈夫曼树 数据结构—基础知识哈夫曼树
哈夫曼树的基本概念
哈夫曼Huffman树又称最优树是一类带权路径长度最短的树在实际中有广泛的用途。哈夫曼树的定义涉及路径、路径长度、权等概念下面先给出这些概念的定义然后再介绍哈夫曼树
路径从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径长度路径上的分支数目称作路径长度。树的路径长度从树根到每一结点的路径长度之和。权赋予某个实体的一个量是对实体的某个或某些属性的数值化描述。在数据结构中实体有结点元素和边关系两大类所以对应有结点权利边权结点权或边权具体代表什么意义由具体情况决定。如果在一棵树中的结点上带有权值则对应的就有带权树等概念。结点的带权路径长度从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度树中所有叶子结点的带权路径长度之和通常记作WPL。哈夫曼树设有m个权值{w1w2…wm},可以构造一棵含n个叶子结点的二叉树每个叶子结点的权为w则其中带权路径长度WPL最小的一叉树称做最优二叉树或哈夫曼树。
例如下图中所示的3棵二叉树都含4个叶子结点a、b、c、d分别带权7、5、2、4他们的带权路径长度分别为 哈夫曼树的构造算法
哈夫曼树的构造过程
根据给定的n个权值{w1w₂…wn}构造n棵只有根结点的二叉树这n棵二叉树构成一个森林F。在森林F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。选用两小造新树在森林F中删除这两棵树同时将新得到的二叉树加人F中。删除两小添新人重复(2)和(3),直到F只含一棵树为止。这棵树便是哈夫曼树。重复(2)(3)剩单根
在构造哈夫曼树时首先选择权小的这样保证权大的离根较近这样一来在计算树的带权路径长度时自然会得到最小带权路径长度这种生成算法是一种典型的贪心法。
注哈夫曼树的结点的度数为0或2没有度为1的结点。
哈夫曼算法的实现
//-------哈夫曼树的存储表示-------
typedef struct{int weight;//结点的权值int parent,lchild,rchild;//结点的双亲、左孩子、右孩子的下标
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树权值双亲左孩子右孩子weightparentlchildrchild
包含n棵树的森林经过n-1次合并才能形成哈夫曼树共产生n-1个新结点
算法构造哈夫曼树
【算法步骤】
初始化首先动态申请2n个单元;然后循环 2n-1次从1号单元开始依次将1至2n-1所有单元中的双亲、左孩子、右孩子的下标都初始化为0最后再循环n次输入前n个单元中叶子结点的权值。创建树:循环n-1次通过n-1次的选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树根结点s1和 s2删除是指将结点s1 和s2白的双亲改为非 0合并就是将s1 和 s2的权值和作为一个新结点的权值依次存入到数组的第n1之后的单元中同时记录这个新结点左孩子的下标为s1右孩子的下标为 s2。
void CreateHuffmanTree(HuffmanTree HT,int n)
{if(n1) return;m2*n-1;HTnew HTNode[m1];//0号单元未用所以需要动态分配m1个单元HT[m]表示根结点for(i1;im,1)//将1~m号单元中的双亲、左孩子右孩子的下标都初始化为0{HT[i].parnt0;HT[i].lchild0;HT[i].rchild0;}for(i1;in,1)//输入前n个单元中叶子结点的权值cinHT[i].weight;
/*-----------初始化工作结束下面开始创建哈夫曼树-----------*/for(in1;in;1){//通过n-1次的选择、删除、合并来创建哈夫曼树Select(HT,i-1,s1,s2);//在HT[k]1≤k≤i-1中选择两个其双亲域0且权值最小的结点并返回它们在HT中的序号s1和s2最小结点下标HT[s1].parenti;HT[s2].parenti;//修改HT[s1][s2]的parent值HT[i].lchilds1;HT[i].rchilds2;//s1,s2分别作为i的左右孩子HT[i].weightHT[s1].weightHT[s2].weight;//i的权值为左右孩子之和}
}已知w529781423311构造一棵哈夫曼树计算树的带权路径长度并给出构造过程中存储结构HT的初始状态和终结状态。 HT初态结点iweightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000
HT的终态结点iweightparentlchildrchild1590022914003710004810005141200623130073900811110098117110151234111913981229145101342151161458152121510001314
