一、基本介绍
1、 简介:在给定n个权值作为n个叶子节点,构造一颗二叉树,如果该二叉树的带权路径长度(wpl)达到最小,称为这样的树称为最优二叉树,也称赫夫曼树。赫夫曼树是带权路径最短的树,权值越大的结点离根结点最近。
2、 二叉树的路径长度:由根结点到所有叶子结点的路径长度之和。
3、 二叉树的带权路径长度:从根结点到各个叶子结点的路径长度与相应结点权值的乘积之和。
例如一下树的带权路径长度为:WPL=2 * 2 + 4 * 2 + 5 * 2 + 3 * 2 = 28
二、赫夫曼树的创建过程
在给定一个数组,{13,6,7,8,3,29,1}要求转为一颗赫夫曼树。大致过程如下:
1、将该