最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

精彩看点：[数据结构] 哈夫曼树

来源：博客园

哈夫曼树

哈夫曼树简介

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

哈夫曼树涉及的基本概念

路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第 L层结点的路径长度为 L - 1。

树的带权路径长度

设二叉树具有 n 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为 树的带权路径长度（Weighted Path Length of Tree，WPL）。


(资料图)

设 w为二叉树第 i个叶结点的权值，l为从根结点到第 i个叶结点的路径长度，则 WPL计算公式如下：

对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL最小的二叉树称为哈夫曼树。其叶结点权值越小，离根越远，叶结点权值越大，离根越近。

哈夫曼树的构建

哈夫曼树的构建思路

（1）将给定的 n个节点构建成一个二叉树（初始情况下单个节点看成是一颗二叉树）的集合；（2）每次在集合中选取最小权值的两个二叉树根节点，并将这两个二叉树将最小的一个作为左子树，次小的一个作为右子树，合并成一个新的二叉树；（3）将取出的最小的两个二叉树从集合中删除，并将新的二叉树加入到集合中；（4）重复步骤（2）、（3），最后集合中只剩下一个二叉树时，哈夫曼树构建完成。

构建哈夫曼树图解

（1）

初始化二叉树集合

（2）

最小的 1 和 3 合并为 4

（3）

最小的 4 和 4 合并为 8

（4）

最小的 5 和 6 合并为 11

（5）

最小的 7 和 8 合并为 15

（6）

最小的 9 和 11 合并为 20

（7）

最小的 15 和 20 合并为 35

（8）

计算 WPL

哈夫曼树相关试题

哈夫曼树

Acwing 3531.哈夫曼树

#include#include#include#includeusing namespace std;int n, ans = 0;priority_queue, greater > heap;  //小根堆int main(){    ios::sync_with_stdio(false);    cin.tie(0);        cin>>n;    while(n--){        int x; cin>>x;        heap.push(x);    }        while(heap.size() > 1){        int a = heap.top();        heap.pop();        int b = heap.top();        heap.pop();                ans += a + b;        heap.push(a + b);    }    cout<

关键词： 路径长度 基本概念