数据结构与算法：哈夫曼树（源码）！

红太狼 2021-09-19 09:06 218阅读 0赞

![复制代码][copycode.gif]

\#include < iostream >    
 \#define  MAXVALUE 100000   
 using   namespace  std;  
 const   int  n = 4 ; // 叶子节点个数   
 // 构造哈夫曼树结点    
 typedef  struct \{  
 int  weight; // 权值    
 int  parent; // 父节点    
 int  lchild; // 左子树    
 int  rchild; // 右子树    
 \}HNodeType;  
  
HNodeType HFMTree\[ 2 \* n \- 1 \]; // 结点数   
  
 // 构造哈夫曼编码数组   
 typedef  struct \{  
 int  bit\[n\];  
 int  start;  
\}HCodeType;  
  
HCodeType HFMCode\[n\];  
 // 创建哈夫曼树    
 void  createHFMTree(HNodeType HFMTree\[\], int  n)\{  
 int  m1,x1,m2,x2;  
 int  i,j;  
 // 初始化   
 for (i = 0 ;i < 2 \* n \- 1 ;i \++ )\{  
   HFMTree\[i\].weight = 0 ;  
   HFMTree\[i\].parent =- 1 ;  
   HFMTree\[i\].lchild =- 1 ;  
   HFMTree\[i\].rchild =- 1 ;  
\}  
cout << " 请输入结点权值： " << endl;   
 for (i = 0 ;i < n;i \++ )\{                  
   cin >> HFMTree\[i\].weight;  
\}  
 for (i = 0 ;i < n \- 1 ;i \++ )\{  
   x1 = x2 = MAXVALUE;  
   m1 = m2 = 0 ;  
    for (j = 0 ;j < n \+ i;j \++ )\{  
     if (HFMTree\[j\].parent ==- 1 && HFMTree\[j\].weight < x1)\{  
     x2 = x1;  
     m2 = m1;  
     x1 = HFMTree\[j\].weight;  
     m1 = j;  
    \}  
     else   if (HFMTree\[j\].parent ==- 1 && HFMTree\[j\].weight < x2)\{  
     x2 = HFMTree\[j\].weight;  
     m2 = j;  
    \}  
   \}  
   HFMTree\[m1\].parent = n \+ i;HFMTree\[m2\].parent = n \+ i;  
   HFMTree\[n \+ i\].weight = HFMTree\[m1\].weight \+ HFMTree\[m2\].weight;  
   HFMTree\[n \+ i\].lchild = m1;  
   HFMTree\[n \+ i\].rchild = m2;  
\}  
\}  
 // 转化编码    
 void  createHFMCode(HNodeType HFMTree\[\],HCodeType HFMCode\[\])\{  
HCodeType cd;  
 int  i,j,c,p;  
 for (i = 0 ;i < n;i \++ )\{  
   cd.start = n \- 1 ;  
   c = i;  
   p = HFMTree\[c\].parent;  
    while (p !=- 1 )  
   \{  
     if (HFMTree\[p\].lchild == c)cd.bit\[cd.start\] = 0 ;  
     else  cd.bit\[cd.start\] = 1 ;  
    cd.start \-- ;  
    c = p;  
    p = HFMTree\[c\].parent;  
   \}  
    for (j = cd.start \+ 1 ;j < n;j \++ )  
    HFMCode\[i\].bit\[j\] = cd.bit\[j\];  
   HFMCode\[i\].start = cd.start \+ 1 ;  
\}  
\}  
 // 主函数    
 int  main()  
\{  
 int  i,j;  
 // 创建树    
 createHFMTree(HFMTree,n);  
 // 转码    
 createHFMCode(HFMTree,HFMCode);  
cout << endl;  
 for (i = 0 ;i < n;i \++ )  
\{  
    for (j = HFMCode\[i\].start;j <= n \- 1 ;j \++ )  
   \{  
    cout << HFMCode\[i\].bit\[j\];  
   \}  
   cout << endl;  
\}  
 return   0 ;  
\}

![复制代码][copycode.gif]

这个是雏形，下面我们要实现的功能是，输入一个含有N位A,B,C,D四种字母的字符串。

然后转换成只含有0，1的代码串。之所以要使用哈夫曼树是因为哈夫曼树是最优树。根据权值来实现最短编码。

下面是实现自动转码的程序：

![复制代码][copycode.gif]

\#include < iostream >    
 \#define  MAXVALUE 100000   
 using   namespace  std;  
 const   int  n = 4 ; // 叶子节点个数    
 string  l;  
 int  size;  
 // 构造哈夫曼树结点    
 typedef  struct \{  
 int  weight; // 权值    
 int  parent; // 父节点    
 int  lchild; // 左子树    
 int  rchild; // 右子树    
 \}HNodeType;  
  
HNodeType HFMTree\[ 2 \* n \- 1 \]; // 结点数   
  
 // 构造哈夫曼编码数组   
 typedef  struct \{  
 int  bit\[n\];  
 int  start;  
\}HCodeType;  
  
HCodeType HFMCode\[n\];  
 // 创建哈夫曼树    
 void  createHFMTree(HNodeType HFMTree\[\], int  n)\{  
 int  m1,x1,m2,x2;  
 int  i,j;  
 // 初始化   
 for (i = 0 ;i < 2 \* n \- 1 ;i \++ )\{  
   HFMTree\[i\].weight = 0 ;  
   HFMTree\[i\].parent =- 1 ;  
   HFMTree\[i\].lchild =- 1 ;  
   HFMTree\[i\].rchild =- 1 ;  
\}  
cout << " \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*哈夫曼树字符串最优转码程序\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* " << endl;   
cout << " 请输入一个字符串：(只含有A，B，C，D四种字符,输入回车结束) " << endl;   
cin >> l;  
std:: string  str(l);  
  size = str.size();      
   for ( int  i = 0 ;i < size; \++ i)\{     
    if (str.at(i) == ' A ' )HFMTree\[ 0 \].weight \++ ;  
    else   if (str.at(i) == ' B ' )HFMTree\[ 1 \].weight \++ ;  
    else   if (str.at(i) == ' C ' )HFMTree\[ 2 \].weight \++ ;  
    else   if (str.at(i) == ' D ' )HFMTree\[ 3 \].weight \++ ;  
    else \{   
   cout << " 输入有误! " << endl;  
    break ;  
   \}  
\}  
  
 for (i = 0 ;i < n \- 1 ;i \++ )\{  
   x1 = x2 = MAXVALUE;  
   m1 = m2 = 0 ;  
    for (j = 0 ;j < n \+ i;j \++ )\{  
     if (HFMTree\[j\].parent ==- 1 && HFMTree\[j\].weight < x1)\{  
     x2 = x1;  
     m2 = m1;  
     x1 = HFMTree\[j\].weight;  
     m1 = j;  
    \}  
     else   if (HFMTree\[j\].parent ==- 1 && HFMTree\[j\].weight < x2)\{  
     x2 = HFMTree\[j\].weight;  
     m2 = j;  
    \}  
   \}  
   HFMTree\[m1\].parent = n \+ i;HFMTree\[m2\].parent = n \+ i;  
   HFMTree\[n \+ i\].weight = HFMTree\[m1\].weight \+ HFMTree\[m2\].weight;  
   HFMTree\[n \+ i\].lchild = m1;  
   HFMTree\[n \+ i\].rchild = m2;  
\}  
\}  
 // 转化编码    
 void  createHFMCode(HNodeType HFMTree\[\],HCodeType HFMCode\[\])\{  
HCodeType cd;  
 int  i,j,c,p;  
 for (i = 0 ;i < n;i \++ )\{  
   cd.start = n \- 1 ;  
   c = i;  
   p = HFMTree\[c\].parent;  
    while (p !=- 1 )  
   \{  
     if (HFMTree\[p\].lchild == c)cd.bit\[cd.start\] = 0 ;  
     else  cd.bit\[cd.start\] = 1 ;  
    cd.start \-- ;  
    c = p;  
    p = HFMTree\[c\].parent;  
   \}  
    for (j = cd.start \+ 1 ;j < n;j \++ )  
    HFMCode\[i\].bit\[j\] = cd.bit\[j\];  
   HFMCode\[i\].start = cd.start \+ 1 ;  
\}  
\}  
 // 主函数    
 int  main()  
\{  
 int  i,j;  
 // 创建树    
 createHFMTree(HFMTree,n);  
 // 转码    
 createHFMCode(HFMTree,HFMCode);  
cout << endl;  
 int  k = 65 ;  
 for (i = 0 ;i < n;i \++ )  
\{  
   cout << ( char )k << " 的编码： " ;  
    for (j = HFMCode\[i\].start;j <= n \- 1 ;j \++ )  
   \{  
    cout << HFMCode\[i\].bit\[j\];  
   \}  
   k \++ ;  
   cout << endl;  
\}  
cout << " 转码后的字符串为： " << endl;  
std:: string  str(l);  
  size = str.size();      
   for ( int  i = 0 ;i < size; \++ i)\{     
    if (str.at(i) == ' A ' )\{  
    for (j = HFMCode\[ 0 \].start;j <= n \- 1 ;j \++ )  
   cout << HFMCode\[ 0 \].bit\[j\];  
   \}  
    else   if (str.at(i) == ' B ' )\{  
    for (j = HFMCode\[ 1 \].start;j <= n \- 1 ;j \++ )  
   cout << HFMCode\[ 1 \].bit\[j\];  
   \}  
    else   if (str.at(i) == ' C ' )\{  
    for (j = HFMCode\[ 2 \].start;j <= n \- 1 ;j \++ )  
   cout << HFMCode\[ 2 \].bit\[j\];  
   \}  
    else   if (str.at(i) == ' D ' )\{  
    for (j = HFMCode\[ 3 \].start;j <= n \- 1 ;j \++ )  
   cout << HFMCode\[ 3 \].bit\[j\];  
   \}  
    else \{   
   cout << " 输入有误! " << endl;  
    break ;  
   \}  
\}  
 return   0 ;  
\}

![复制代码][copycode.gif]

程序本机测试通过，可以放心运行！

本文转自施杨博客园博客，原文链接：http://www.cnblogs.com/shiyangxt/archive/2008/12/05/1348174.html，如需转载请自行联系原作者

[copycode.gif]: /images/20210726/48be7216cec047e79f74ca14fde04476.png