二叉树叶子节点的霍夫曼编码

 1 #include<iostream>
 2 #include<list>
 3 
 4 using namespace std;
 5 
 6 typedef struct treenode
 7 {
 8     treenode* leftchild;
 9     treenode* rightchild;
10     int data;
11 }Treenode,*pTreenode;
12 
13 //遍历list<int>中的元素
14 void printL(list<int> &l)
15 {
16     for(list<int>::iterator it=l.begin();it!=l.end();it++)
17     {
18         cout<<(*it);
19     }
20 }
21 
22 
23 //对二叉树的每个叶子节点进行霍夫曼编码，将编码的结果存储在链表l中并打印出来，打印的叶子节点的顺序按照先序遍历的顺序。编码的原则是二叉树向左是0，向右是1
24 void Huffmancode(pTreenode root,list<int> &l)
25 {
26     if(!root)
27     {
28         return;
29     }
30 
31     if(!root->leftchild && !root->rightchild)
32     {
33         cout<<root->data<<":";
34         printL(l);
35         cout<<endl;
36     }
37 
38     if(root->leftchild)
39     {
40         l.push_back(0);//将元素"0"压入栈的末端
41         Huffmancode(root->leftchild,l);
42         l.pop_back();//执行完递归函数的这一层，需要将其弹出，就只剩下上一层的根节点的编码了，这位为后面该根节点的右子树叶子节点编码扫清了障碍
43     }
44 
45     if(root->rightchild)
46     {
47         l.push_back(1);//将元素"1"压入栈的末端
48         Huffmancode(root->rightchild,l);
49         l.pop_back();
50     }
51 }
52 
53  
54 
55 int main()
56 {
57     //建立一颗树
58     Treenode t1,t2,t3,t4,t5,t6,t7;
59     memset(&t1,0,sizeof(Treenode));
60     memset(&t2,0,sizeof(Treenode));
61     memset(&t3,0,sizeof(Treenode));
62     memset(&t4,0,sizeof(Treenode));
63     memset(&t5,0,sizeof(Treenode));
64     memset(&t6,0,sizeof(Treenode));
65     memset(&t7,0,sizeof(Treenode));
66 
67     t1.data=1;
68     t2.data=2;
69     t3.data=3;
70     t4.data=4;
71     t5.data=5;
72     t6.data=6;
73     t7.data=7;
74 
75     t1.leftchild=&t2;
76     t1.rightchild=&t3;
77     t2.leftchild=&t4;
78     t2.rightchild=&t5;
79     t3.rightchild=&t6;
80     t4.leftchild=&t7;
81     //霍夫曼编码
82     list<int> L;
83     Huffmancode(&t1,L);
84 
85     return 0;
86 }