C语言实现最优二叉树——霍夫曼（Huffman）树算法_c语言霍夫曼算法

作者：从前慢现在也慢 | 2024-06-12 20:54:21

踩

c语言霍夫曼算法

1、基本概念：霍夫曼（Huffman）树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。在许多应用中，常常赋给树中结点一个有某种意义的实数，称此实数为该结点的权。从树根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度(WPL)，树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，通常记为：

2、算法思想：

（1）以权值分别为W1,W2,...Wn的n个结点，构成n课二叉树T1,T2...Tn。其中每棵二叉树Ti是仅有一个权值为Wi的根结点，让它们按权值从小到大的顺序挂在一棵树上；

（2）然后从这些结点中挑选两棵最小的二叉树作为左右子树构造一棵新的二叉树，并且此时的新二叉树的根节点权值为左右子树权值之和；

（3）从上面（第一步中生成的）的那棵顺序树中删掉上面一步的两棵二叉树，把新的二叉树结点放进那棵顺序树中重新排序；

（4）重复（2）、（3）直到最后剩下一颗二叉树为止，这棵二叉树就是Huffman二叉树；

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/709579