【头歌】构建哈夫曼树及编码

构建哈夫曼树及编码

第1关：构建哈夫曼树

任务描述

本关任务：构建哈夫曼树，从键盘读入字符个数n及这n个字符出现的频率即权值，构造带权路径最短的最优二叉树（哈夫曼树）。

相关知识

哈夫曼树的定义

设二叉树具有n个带权值的叶子结点{w1,w2,...,wn}，从根结点到每个叶子结点都有一个路径长度。

从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和称为该二叉树的带权路径长度，记作：

其中，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。

例如：

以上二叉树的带权路径长度值： WPL=1×3+3×3+5×2+7×1=29

给定一组具有确定权值的叶子结点，可以构造出许多形状的二叉树，把其中具有最小带权路径长度的二叉树称为哈夫曼树。

例如，用4个整数1、3、5、7作为4个叶子结点的权值，可以构造出不同的二叉树，它们的带权路径长度可能不相同，如下：