首页 > 代码库 > 由二叉树构造赫夫曼树
由二叉树构造赫夫曼树
赫夫曼树：
如果有n个权值{w1,w2,w3....},试构造一棵具有n个叶子节点的二叉树，每一个叶子节点带权为wi。则当中带权路径长度最小的二叉树称为最优二叉树或者叫赫夫曼树。
构造赫夫曼树：
如果有n个权值，则构造出的赫夫曼树有n个叶子节点，n个权值分别设置为w1，w2,....wn,则赫夫曼树的构造规则为：
1.将w1,w2...看成是有n棵树的森林；
2.在森林中选择两个根节点的权值最小的树合并，作为一棵新树的左右子树，且新树的根节点权值为其左右子树根节点权值之和；
3.从森林中删除选取的两棵树，并将新树增加森林。
4.反复2、3步，直到森林中仅仅剩一棵树为止。该树即为所求得的赫夫曼树。
实现：
以数组形式存储赫夫曼树节点，节点形态：
/**************************************************
构造赫夫曼树
by Rowandjj
2014/6/2
**************************************************/
#include<IOSTREAM>
using namespace std;
#define UINT_MAX 0xffffffff
typedef struct _BITREE_//二叉树
{
int data;//存放节点的圈中
struct _BITREE_ *lChild;
struct _BITREE_ *rChild;
}Bitree,*pBitree;
typedef struct _HUFFMANTREE_//赫夫曼树
{
unsigned int weight;
unsigned int parent;
unsigned int lChild;
unsigned int rChild;
}HuffmanTree,*pHuffmanTree;
int iCount = 0;//叶子节点数
int iIndex = 1;//索引
//-----------------------------------------
void CreateBiTree(pBitree* pBitreeTemp);//创建二叉树
void CreatreArray(pHuffmanTree& pHuffmanTreeTemp,pBitree pBitreeTemp);//将二叉树每一个节点的值作为权放进赫夫曼树中
pHuffmanTree InitHuffmanTree();//初始化赫夫曼树，
void CreateHuffmanTree(pHuffmanTree& pHuffmanTreeTemp);//创建赫夫曼树
int GetNode(pHuffmanTree& pHuffmanTreeTemp,int i);//获取赫夫曼树中位置0-i中值最小的节点的索引
void SelectNode(pHuffmanTree& pHuffmanTreeTemp,int i,int *m,int *n);//选择赫夫曼树数组中值最小的两个节点的索引（不包括已有父节点的节点）
void DestroyTree(pBitree* pBitreeTemp);
void DestroyHuffmanTree(pHuffmanTree& pHuffmanTreeTemp);
int main()
{
int i;
//创建二叉树
pBitree pBitreeTemp;
CreateBiTree(&pBitreeTemp);
//初始化赫夫曼树
pHuffmanTree pHuffmanTreeTemp = InitHuffmanTree();
//初始化赫夫曼树的叶子节点的权
CreatreArray(pHuffmanTreeTemp,pBitreeTemp);
for(i = 1; i <= iCount ; i++)
{
cout<<pHuffmanTreeTemp[i].weight<<" ";
}
cout<<endl;
//创建赫夫曼树
CreateHuffmanTree(pHuffmanTreeTemp);
for(i = 1; i <= 2*iCount-1 ; i++)
{
cout<<pHuffmanTreeTemp[i].weight<<" ";
}
cout<<endl;
DestroyTree(&pBitreeTemp);
DestroyHuffmanTree(pHuffmanTreeTemp);
return 0;
}
void CreateBiTree(pBitree* pBitreeTemp)
{
int data;
cin>>data;
if(data =http://www.mamicode.com/= -1)>測试：
图解构造过程：
1.首先将二叉树中的节点所有存到代表赫夫曼树的数组中。其余位置为0:
2.循环遍历该数组。每次找到最小权重的两个节点。之和作为其父节点的权重
3.循环一遍后。便得到赫夫曼树：
由二叉树构造赫夫曼树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。