假设给定一个有n个权值的集合{w1,w2,w3,…,wn},其中wi>0(1<=i<=n)。若T是一棵有n个叶结点的二叉树，而且将权值w1,w2,w3…wn分别赋值给T的n个叶结点，则称T是权值为w1,w2,w3…wn的扩充二叉树。带有权值的叶节点叫着扩充二叉树的外结点，其余不带权值的分支结点叫做内结点。外结点的带权路径长度为T的根节点到该结点的路径长度与该结点上的权值的乘积。n个外结点的扩充二叉树的带权路径长度为
Huffman树构造算法： 1、由给定的n个权值{w1,w2,w3,…,wn}构造n棵只有根节点的扩充二叉树森林F={T1,T2,T3,…,Tn},其中每棵扩充二叉树Ti只有一个带权值wi的根节点，左右孩子均为空。 2、重复以下步骤，直到F中只剩下一棵树为止： a、在F中选取两棵根节点的权值最小的扩充二叉树，作为左右子树构造一棵新的二 叉树。将新二叉树的根节点的权值为其左右子树上根节点的权值之和。 b、在F中删除这两棵二叉树； c、把新的二叉树加入到F中； 最后得到的就是Huffman树。
对次可以借助小堆来创建Huffman树当堆中只有一个节点是这个节点就是Huffman树的根 堆的实现上一篇博文已经讲过本文不在多说http://blog.csdn.net/dakuan_chen/article/details/72884960
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include "heap.hpp" #include <string> #include <stack> #include <memory> #include <stdio.h> template<class T> struct HuffmanNode { HuffmanNode(const T& weight) : _weight(weight) , _pLeft(NULL) , _pRight(NULL) , _pParent(NULL) {} HuffmanNode<T>* _pLeft; HuffmanNode<T>* _pRight; HuffmanNode<T>* _pParent; T _weight; T _data; }; template<class T> class HuffmanTree { public: HuffmanTree() : _pRoot(NULL) {} HuffmanTree(const T array[], size_t size, const T& invalue) { _Create(array, size, invalue); } HuffmanNode<T>* GetRoot() { return _pRoot; } // ~HuffmanTree() // { // Destory(_pRoot); // } private: void Destory(HuffmanNode<T>* pRoot) { Destory(pRoot->_pLeft); Destory(pRoot->_pRight); delete pRoot; } struct Compare { bool operator()(const HuffmanNode<T>* pLeft, const HuffmanNode<T>* pRight) { return pLeft->_weight < pRight->_weight; } }; void _Create(const T array[], size_t size, const T& invalue) { assert(array); Heap<HuffmanNode<T>*, Compare> hp; for (size_t i = 0; i < size; i++) { if (array[i] != invalue) { HuffmanNode<T>* ptmp = new HuffmanNode<T>(array[i]); hp.Push(ptmp); } } while (hp.Size()>1) { HuffmanNode<T>* pLeft = hp.Top(); hp.Pop(); HuffmanNode<T>* pRight = hp.Top();; hp.Pop(); HuffmanNode<T>* pParent = new HuffmanNode<T>(pRight->_weight + pLeft->_weight); pParent->_pLeft = pLeft; pParent->_pRight = pRight; pLeft->_pParent = pParent; pRight->_pParent = pParent; hp.Push(pParent); } _pRoot = hp.Top(); } protected: HuffmanNode<T>* _pRoot; };