数据结构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)

有什么问题的话可以在下方留言,如果能够帮助到你,希望能帮忙点个赞!!!蟹蟹喽!!!

 

上一篇:[转]sa不能远程连接sql server 2008的解决办法


下一篇:字典和集合的区别以及常用方法