Python教程
数据结构c+python代码6：哈夫曼树构造及编码
首先介绍一下什么是哈夫曼树？
给定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)
有什么问题的话可以在下方留言，如果能够帮助到你，希望能帮忙点个赞！！！蟹蟹喽！！！
-
Python编程基础详解11-24
-
Python编程基础教程11-21
-
Python编程基础与实践11-20
-
Python编程基础与高级应用11-20
-
Python 基础编程教程11-19
-
Python基础入门教程11-19
-
在FastAPI项目中添加一个生产级别的数据库——本地环境搭建指南11-17
-
`PyMuPDF4LLM`：提取PDF数据的神器11-16
-
四种数据科学Web界面框架快速对比：Rio、Reflex、Streamlit和Plotly Dash11-16
-
获取参数学习：Python编程入门教程11-14
-
Python编程基础入门11-14
-
Python编程入门指南11-14
-
Python基础教程11-13
-
Python编程基础指南11-12
-
Python基础编程教程11-12
