首页 > 代码库 > 哈夫曼树
哈夫曼树
哈夫曼树
给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。节点的带权长度是这样定义的:节点的权值*根节点到该节点的路径长度。树的带权路径长度(Weighted Path Length of Tree,简记为WPL)则是指所有节点的带权长度和。哈夫曼树就是使WPL最小的一种树,并且哈夫曼树是满二叉树。它的构造方法是哈夫曼方法。哈夫曼树是这样构造的:
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:(摘自百度百科)
- 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
- 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
- 从森林中删除选取的两棵树,并将新树加入森林;
- 重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
哈夫曼编码
提到哈夫曼树,这就不得不提到哈夫曼编码。哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。它的构造比较简单:先建好哈夫曼树,左子树的路径标记为0,右子树的路径标记为1。叶节点的哈夫曼编码就是根节点到叶节点的简单路径上的0、1序列。
下面给出构建哈夫曼树和哈夫曼编码的c++代码:
代码
//Huffman树 #include<iostream> #include<iomanip> #include<stack> using namespace std; //最大权值 const int MAXWEIGHT = 100; //Huffman节点 typedef struct { int weight; //节点权值 int parent; //父节点下标 int lchild; //左孩子下标 int rchild; //右孩子下标 }HuffNode, *HuffTree; //HuffCode typedef struct { //权值 int weight; //用栈存储编码 stack<char> code; }HuffCode; /* 创建Huffman树 根据指定的权值数组创建Huffman树 */ HuffNode *buildHuffTree(int weight[], int n) { if (!weight || n < 1) return NULL; /* 用顺序存储Huffman树 Huffman树是满二叉树 n为叶子节点数,则内部节点数是n-1,共有2*n-1个节点 */ int m = 2 * n - 1; //节点总数 HuffNode* tree = new HuffNode[m]; //初始化Huffman树 int i, j; for (i = 0; i < m; i++) { //把初始节点存储在数组前部 if (i < n) tree[i].weight = weight[i]; tree[i].parent = tree[i].lchild = tree[i].rchild = -1; } /* 建树 只需n-1次循环 w1是当前最小权值,p1是其下标;w2是当前次最小权值,p2是其下标 */ int w1, w2, p1, p2; for (i = n; i < m; i++) { //每次循环前都得初始化权值和下标 w1 = w2 = MAXWEIGHT; p1 = p2 = 0; //寻找最小和次最小权值节点 for (j = 0; j < i; j++) { //父节点下标为-1,说明该节点未被使用 if (tree[j].parent == -1) { if (tree[j].weight < w1) { w2 = w1; p2 = p1; w1 = tree[j].weight; p1 = j; } else if (tree[j].weight < w2) { w2 = tree[j].weight; p2 = j; } } } //把产生的新节点放入位置i tree[p1].parent = tree[p2].parent = i; tree[i].weight = tree[p1].weight + tree[p2].weight; tree[i].lchild = p1; tree[i].rchild = p2; } return tree; } /* 根据Huffman树构建Huffman编码 */ HuffCode* huffCode(HuffTree tree, int n) { HuffCode* Code = new HuffCode[n]; int i, child, parent; for (i = 0; i < n; i++) { stack<char> stack; child = i; parent = tree[child].parent; while (parent != -1) { //左孩子的分支是1 if (tree[parent].lchild == child) stack.push('0'); else//右孩子的分支是1 stack.push('1'); child = parent; parent = tree[child].parent; } Code[i].weight = tree[i].weight; Code[i].code = stack; } return Code; } //打印Huffman树 void printHuffTree(HuffTree tree, int n) { int i; cout.setf(ios::left); for (i = 0; i < n; i++) { cout << setw(2) << i << " 权值:" << setw(3) << tree[i].weight << "父亲:" << setw(3) << tree[i].parent << "左孩子:" << setw(3) << tree[i].lchild << "右孩子:" << setw(3) << tree[i].rchild << endl; } } int main() { cout << "***Huffman树***by David***" << endl; int n; cout << "输入权值个数 "; while (cin >> n && n < 1) cout << "出错,重新输入 "; int *weight = new int[n]; cout << "输入权值序列 "; int i = 0; while (i < n) cin >> weight[i++]; cout << "创建Huffman树" << endl; HuffTree tree = buildHuffTree(weight, n); printHuffTree(tree, 2 * n - 1); cout << endl; cout << "进行Huffman编码" << endl; HuffCode *code = huffCode(tree, n); for (i = 0; i < n; i++) { cout << "权值:" << setw(3) << code[i].weight << "Huffman编码:"; stack<char> stack = code[i].code; while (!stack.empty()) { cout << stack.top(); stack.pop(); } cout << endl; } //释放空间 delete[]weight; delete[]tree; delete[]code; system("pause"); return 0; }
运行
转载请注明出处,本文地址:http://blog.csdn.net/zhangxiangdavaid/article/details/37696533
若有所帮助,顶一个哦!
专栏目录:数据结构与算法目录
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。