首先介绍一下什么是哈夫曼树?
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
哈夫曼树又称为最优树.
1、路径和路径长度
在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
哈夫曼树
哈夫曼树(3张)
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。
哈夫曼树的构造
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
c代码过程分析
构造哈夫曼树算法的实现可以分成两大部分:
1、初始化:首先动态申请2n个单元;然后循环2n-1次,从1号单元开始,依次将1至2n-1所有单元中的双亲、左孩子、右孩子的下标都初始化为0;最后再循环n次,输入前n个单元中叶子节点的权值。
2、创建树:循环n-1次,通过n-1次的选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树跟节点是s1和s2;删除是指将节点s1和s2的双亲改为非0;合并就是将s1和s2的权值和作为一个新节点的权值依次存入到数组的第n+1之后的单元中,同时记录这个新节点左孩子的下标为s1,右孩子的下标为s2。
哈夫曼编码的算法实现
在构造哈夫曼树之后,求哈夫曼编码的主要思想是:依次以叶子为出发点,向上回溯至根节点为止。回溯时走左分支则生成代码0,走右分支则生成代码1。
由于每个哈夫曼编码是变长编码,因此使用一个指针数组来存放每个每个字符编码串的首地址。
**typedef char HuffmanCode; //动态分配数组存储哈夫曼编码表
各字符的哈夫曼编码存储在由HuffmanCode定义的动态分配的数组HC中,为了实现方便,数组的0号单元不使用。从1号单元开始使用,所以数组HC的大小为n+1.即编码表HC包括n+1行。但是因为每个字符编码的长度事先不能确定,所以不能预先为每个字符分配大小合适的存储空间。为了不浪费存储空间,动态分配一个长度为n(字符编码一定小于n)的一维数组cd,用来临时存放当前正在求解的第i(1<=i<=n)个字符的编码,当第i个字符的编码求解完毕后,根据数组cd的字符串长度分配HC[i]的空间,然后将数组cd中的编码复制到HC[i]中。
因为求解编码时是从哈夫曼树的叶子出发,向上回溯至根节点。所以对于每个字符,得到的编码顺序是从右向左的,故将编码向数组cd存放的顺序也是从后向前的,即每个字符的第1个编码存放在cd[n-2]中(cd[n-1]存放字符串结束标志‘\0’),第2个编码存放在cd[n-3]中,依次类推,直到全部编码存放完毕。
其他的我就不多说了,直接放代码,c语言实现哈夫曼树的构造及编码如下:
1 #include <iostream> 2 using namespace std; 3 #include <stdlib.h> 4 typedef char **HuffmanCode; 5 #include <string.h> 6 7 typedef struct HTNode 8 { 9 int weight; 10 int parent, lchild, rchild; 11 }HTNode, *HuffmanTree; 12 13 void Select(HuffmanTree HT, int n, int &s1, int &s2) 14 { 15 int minum; //定义一个临时变量保存最小值 16 for(int i=1;i<=n;i++) //寻找第一个最小值 17 { 18 if(HT[i].parent==0) 19 { 20 minum = i; 21 break; 22 } 23 } 24 for(int i=1;i<=n;i++) 25 { 26 if(HT[i].parent==0) 27 { 28 if(HT[i].weight < HT[minum].weight) 29 { 30 minum = i; 31 } 32 } 33 } 34 s1 = minum; 35 36 for(int i=1;i<=n;i++) //寻找第二个最小值 37 { 38 if(HT[i].parent==0&&i!=s1) 39 { 40 minum = i; 41 break; 42 } 43 } 44 for(int i=1;i<=n;i++) 45 { 46 if(HT[i].parent==0&&i!=s1) 47 { 48 if(HT[i].weight < HT[minum].weight) 49 { 50 minum = i; 51 } 52 } 53 } 54 s2 = minum; 55 } 56 57 58 void creatHuff(HuffmanTree &HT, int *w, int n) 59 { 60 int m, s1, s2; 61 m = 2*n-1; //总的节点个数 62 HT = (HTNode *)malloc(sizeof(HTNode)*(m+1)); 63 for(int i=1;i<=n;i++) //1-n之间存放叶子节点 初始化 64 { 65 HT[i].weight = w[i]; 66 HT[i].parent = 0; 67 HT[i].lchild = 0; 68 HT[i].rchild = 0; 69 } 70 71 for(int i=n+1;i<=m;i++) //非叶子节点的初始化 72 { 73 HT[i].weight = 0; 74 HT[i].parent = 0; 75 HT[i].lchild = 0; 76 HT[i].rchild = 0; 77 } 78 79 cout<<"构造的哈夫曼树如下:\n"; 80 for(int i=n+1;i<=m;i++) //填充n+1-m之间节点的信息 81 { 82 //在HT[1]-HT[i-1]的范围内选择两个parent为0且weight最小的两个节点,其序号分别赋值给s1 s2 83 Select(HT, i-1, s1, s2); 84 HT[s1].parent = i; 85 HT[s2].parent = i; 86 HT[i].lchild = s1; 87 HT[i].rchild = s2; 88 HT[i].weight = HT[s1].weight + HT[s2].weight; 89 printf("%d (%d, %d)\n", HT[i].weight, HT[s1].weight, HT[s2].weight); 90 } 91 92 // cout<<"根节点的标号-权重-左孩子标号-右孩子标号:\n"; 93 // for(int i=n+1;i<=m;i++){ 94 // if(HT[i].parent==0){ 95 // printf("%d-%d-%d-%d", i, HT[i].weight, HT[i].lchild, HT[i].rchild); 96 // } 97 // } 98 } 99 100 101 void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) 102 { 103 HC = (char **)malloc(sizeof(char *)*(n+1)); //分配n个字符编码的编码表空间 104 char *cd = (char *)malloc(sizeof(char)*n); //分配临时存放每个字符编码的动态数组空间 105 cd[n-1] = '\0'; 106 int start, c, f; 107 for(int i=1;i<=n;i++) 108 { 109 start = n-1; 110 c = i; 111 f = HT[i].parent; 112 while(f!=0) 113 { 114 start --; 115 if(HT[f].lchild == c) 116 cd[start] = '0'; 117 else 118 cd[start] = '1'; 119 c = f; 120 f = HT[f].parent; 121 } 122 HC[i] = (char *)malloc(sizeof(char)*(n-start)); 123 strcpy(HC[i], &cd[start]); 124 } 125 delete cd; 126 for(int i=1;i<=n;i++){ 127 cout<<"编号"<<i<<": 权重为"<<HT[i].weight<<"编码为:"<<HC[i]<<endl; 128 } 129 delete HT; 130 } 131 int main() 132 { 133 HuffmanTree HT; 134 int n, wei; 135 cout<<"请输入节点的个数:"; 136 cin>>n; 137 int *w = (int *)malloc(sizeof(int)*(n+1)); 138 cout<<"请输入"<<n<<"个节点的weight:"<<endl; 139 for(int i=1;i<=n;i++) 140 { 141 cin>>wei; 142 w[i] = wei; 143 } 144 145 creatHuff(HT, w, n); 146 147 HuffmanCode HC; 148 CreatHuffmanCode(HT, HC, n); 149 delete w; 150 151 return 0; 152 }
相同的思想用python来实现出来,代码如下:
1 def Int(w): 2 for i in range(0, len(w)): 3 w[i] = int(w[i]) 4 return w 5 6 def Select(tree, n): 7 minum = 0 #寻找第一个权重最小的下标 8 for i in range(0, n+1): 9 if tree[i]["parent"] == -1: 10 minum = i 11 break 12 for i in range(0, n+1): 13 if tree[i]["parent"] == -1: 14 if tree[i]["weight"] < tree[minum]["weight"]: 15 minum = i 16 s1 = minum 17 for i in range(0, n+1): #寻找第二个权重最小的下标 18 if tree[i]["parent"] == -1 and i != s1: 19 minum = i 20 break 21 22 for i in range(0, n+1): 23 if tree[i]["parent"] == -1 and i != s1: 24 if tree[i]["weight"] < tree[minum]["weight"]: 25 minum = i 26 s2 = minum 27 return s1, s2 28 29 def CreatHuffmanTree(w, n): 30 m = 2*n-1 31 tree = [] 32 for i in range(0, n): #先将叶子节点的各个信息放入到集合中 33 node = {"weight": w[i], "parent": -1, "lchild": 0, "rchild": 0} 34 tree.append(node) 35 for i in range(n, m): #把非叶子节点的各个信息放入到集合中 36 node = {"weight": 0, "parent": -1, "lchild": 0, "rchild": 0} 37 tree.append(node) 38 39 for i in range(n, m): #填充n~m-1之间节点的信息 40 s1, s2 = Select(tree, i-1) #在0~i-1的范围内选择两个parent为0且weight最小的两个节点,其序号分别赋值给s1 s2 41 tree[s1]["parent"] = i 42 tree[s2]["parent"] = i 43 44 tree[i]["lchild"] = s1 45 tree[i]["rchild"] = s2 46 tree[i]["weight"] = tree[s1]["weight"] + tree[s2]["weight"] 47 return tree 48 49 def printTree(tree): 50 print("构建哈夫曼树如下:") 51 index = 0 52 for i in tree: 53 print(index, i) 54 index += 1 55 56 def inverse(codes): 57 58 for i in range(0, len(codes)): 59 res = "" 60 for k in range(len(codes[i])-1, -1, -1): 61 res += codes[i][k] 62 codes[i] = res 63 return codes 64 65 def CreatHuffmanCode(tree, n): 66 code = "" 67 for i in range(0, n): 68 c = i 69 f = tree[i]["parent"] 70 while f != -1: 71 if tree[f]["lchild"] == c: 72 code += "0" 73 else: 74 code += "1" 75 c = f 76 f = tree[f]["parent"] 77 if i != n-1: 78 code += "\n" 79 codes = code.split("\n") 80 #print(codes) 81 codes = inverse(codes) 82 print("---------编码如下----------------") 83 for i in range(0, len(codes)): 84 print("权值为{}的叶子节点编码:{}".format(tree[i]["weight"], codes[i])) 85 86 if __name__ == '__main__': 87 n = int(input("请输入节点的个数:")) 88 w = input("请输入{}个节点的权值:".format(n)).split(" ") 89 w = Int(w) 90 HuffmanTree = CreatHuffmanTree(w, n) #创建哈夫曼树 91 printTree(HuffmanTree) 92 CreatHuffmanCode(HuffmanTree, n)
有什么问题的话可以在下方留言,如果能够帮助到你,希望能帮忙点个赞!!!蟹蟹喽!!!