//声明类BiTree及定义结构BiNode,文件名为bitree.h
<IMG style="PADDING-BOTTOM: 0px; BORDER-RIGHT-WIDTH: 0px; LIST-STYLE-TYPE: none; MARGIN: 0px; PADDING-LEFT: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; BORDER-LEFT-WIDTH: 0px; PADDING-TOP: 0px; border-image: initial" title="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" name=image_operate_35811398500362098 alt="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" src="http://s11.sinaimg.cn/mw690/0026ZEdigy6IpofFCAO6a&690" width=606 height=450 action-type="show-slide" action-data="http%3A%2F%2Fs11.sinaimg.cn%2Fmw690%2F0026ZEdigy6IpofFCAO6a%26690" real_src="http://s11.sinaimg.cn/mw690/0026ZEdigy6IpofFCAO6a&690">
//定义类中的成员函数，文件名为bitree.cpp
<IMG style="PADDING-BOTTOM: 0px; BORDER-RIGHT-WIDTH: 0px; LIST-STYLE-TYPE: none; MARGIN: 0px; PADDING-LEFT: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; BORDER-LEFT-WIDTH: 0px; PADDING-TOP: 0px; border-image: initial" title="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" name=image_operate_55931398500471570 alt="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" src="http://s9.sinaimg.cn/mw690/0026ZEdigy6IpogvbWUb8&690" action-type="show-slide" action-data="http%3A%2F%2Fs9.sinaimg.cn%2Fmw690%2F0026ZEdigy6IpogvbWUb8%26690" real_src="http://s9.sinaimg.cn/mw690/0026ZEdigy6IpogvbWUb8&690">
注意该创建思路是根据前序遍历的思路创建的 ，所以输入的时候要按前序遍历的顺序输入，并且每个叶子后面都要跟两个#。这样才能输入结束。
递归算法的我就不说了，很简单。
仅说说层序遍历：
用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。因为层序遍历的思想是先访问的节点的左右孩子节点也要先访问。这类似于队列的先进先出的思想。
1.要用一个队列（先进先出），存放树结点的指针，可以自已定义一个队列；
算法：
1.从根结点开始，初始先把根结点入队列；
2. 如果队列中结点为空，则程序结束；
3. 从队列中取出一节点作为被访问的节点，出列并显示它的数据；并把它非空的左右子树
放到队列中；
4.回到2循环
<IMG style="PADDING-BOTTOM: 0px; BORDER-RIGHT-WIDTH: 0px; LIST-STYLE-TYPE: none; MARGIN: 0px; PADDING-LEFT: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; BORDER-LEFT-WIDTH: 0px; PADDING-TOP: 0px; border-image: initial" title="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" name=image_operate_31111398505994194 alt="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" src="http://s13.sinaimg.cn/mw690/0026ZEdizy6IpuBPA1S3c&690" action-type="show-slide" action-data="http%3A%2F%2Fs13.sinaimg.cn%2Fmw690%2F0026ZEdizy6IpuBPA1S3c%26690" real_src="http://s13.sinaimg.cn/mw690/0026ZEdizy6IpuBPA1S3c&690">
//二叉树的主函数，文件名为bitreemain.cpp
<IMG style="PADDING-BOTTOM: 0px; BORDER-RIGHT-WIDTH: 0px; LIST-STYLE-TYPE: none; MARGIN: 0px; PADDING-LEFT: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; BORDER-LEFT-WIDTH: 0px; PADDING-TOP: 0px; border-image: initial" title="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" name=image_operate_96721398500498929 alt="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" src="http://s12.sinaimg.cn/mw690/0026ZEdigy6IpooREqT3b&690" action-type="show-slide" action-data="http%3A%2F%2Fs12.sinaimg.cn%2Fmw690%2F0026ZEdigy6IpooREqT3b%26690" real_src="http://s12.sinaimg.cn/mw690/0026ZEdigy6IpooREqT3b&690">
<IMG style="PADDING-BOTTOM: 0px; BORDER-RIGHT-WIDTH: 0px; LIST-STYLE-TYPE: none; MARGIN: 0px; PADDING-LEFT: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; BORDER-LEFT-WIDTH: 0px; PADDING-TOP: 0px; border-image: initial" title="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" name=image_operate_75011398499699198 alt="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" src="http://s16.sinaimg.cn/mw690/0026ZEdigy6Ipmy1QQL2f&690" action-type="show-slide" action-data="http%3A%2F%2Fs16.sinaimg.cn%2Fmw690%2F0026ZEdigy6Ipmy1QQL2f%26690" real_src="http://s16.sinaimg.cn/mw690/0026ZEdigy6Ipmy1QQL2f&690">
下面的代码贴到新浪博客上好像有点问题，不过大致可以看出算法思路就行了。反正我是跑通了，见后面截图<IMG style="PADDING-BOTTOM: 0px; LINE-HEIGHT: 1.5; BORDER-RIGHT-WIDTH: 0px; LIST-STYLE-TYPE: none; MARGIN: 0px; PADDING-LEFT: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; BORDER-LEFT-WIDTH: 0px; PADDING-TOP: 0px; border-image: initial" title="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" alt="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" src="http://www.sinaimg.cn/uc/myshow/blog/misc/gif/E___6724EN00SIGG.gif" real_src="http://www.sinaimg.cn/uc/myshow/blog/misc/gif/E___6724EN00SIGG.gif" type="face">
//哈夫曼树算法
#include
#include
#define m 2*n-1
using namespace std;
const int float_max=1000;
typedef int datatype;
typedef struct
{
int weight; //定义权重
int parent; //定义双亲在向量中的下标
int lchild,rchild; //定义左右子树
} HFnode, * hftree;
void InitHuffmanTree(hftree& T,int n)
//无双亲，即为根结点，尚未合并过,左右孩子指针置为-1
{
int i;
T=new HFnode[m];
for(i=0;i
{
T.weight=0;
T.parent=-1;
T.lchild=-1;
T.rchild=-1;
}
}
void Select(hftree& T,int i,int &p1, int &p2)
{
int j;
int small1,small2;
small1=small2=float_max; //float_max为float类型的最大值,small1 是最小权，small2是次小权。
for(j=0;j<=i-1;j++)
{
if(T[j].parent!=-1) continue;//不考虑已合并过的点
if(T[j].weight //修改最小权和次小权及位置
{
small2=small1;
small1=T[j].weight;
p2=p1;
p1=j;
}
else if(T[j].weight //修改次小权及位置
{
small2=T[j].weight;
p2=j;
}
}
}
//哈夫曼树的构造
void huffman(hftree &T,int n)
{
int i,p1,p2;
InitHuffmanTree(T,m);
for(i=0;i
{
cin>>T.weight;
//输入n个叶子的权
}
for(i=n;i //进行n-1次合并，产生n-1个新结点
{
Select(T,i,p1,p2);
T[p1].parent=T[p2].parent=i; //新根
T.parent=-1;
T.lchild=p1;
T.rchild=p2;
T.weight=T[p1].weight+T[p2].weight; //新结点的权值为最小权与次小权之和
}
}
/
typedef struct
{
char ch;
char * bits;
}CodeNode, * HFCode;
void CreateHuffmanCode(hftree &T,HFCode &HC,int n)
{
int i;
int start;
int c;
int p;
char*cd;
char q;
HC=new CodeNode[n];
cd=new char[n];
cd[n-1]='\0';
for(i=0;i
{
cin>>q;
HC.ch=q;
start=n-1; //从最后一个节点开始
c=i;
while(T[c].parent!=-1) //从字符结点回溯,直至根结点
{
p=T[c].parent;
--start;
cd[start]=(T[p].lchild==c)?'0':'1'; //左孩子编码为0 ,右孩子编码为1
c=p;
}
HC.bits = new char[n-start]; //为第i个字符编码分配空间
strcpy(HC.bits,&cd[start]);
}
delete cd;
}
void OutputHuffmanCode(HFCode &HC,int n)
{
int i;
for(i=0;i
{
cout<<HC.ch<<""<<HC.bits<<endl;
}
}
void Decoding(hftree &T, HFCode &HC,int n, string Str)
{
int p = m-1;
int pos=0;
while (Str[pos])
{
if (Str[pos] == '0') p = T[p].lchild;
else p = T[p].rchild;
if(T[p].lchild==-1 && T[p].rchild==-1 )
{
cout<<HC[p].ch;
p = m-1;
}
pos++;
}
}
int main()
{
int i,n;
cout<<"输入字符个数：";
cin>>n;
hftree T; //哈夫曼树向量
cout<<"
欢迎测试！！！！
"<<endl;
cout<<"----------测试开始-----------"<<endl;
cout<<"首先调用哈夫曼树构造的函数：huffman"<<endl;
cout<<"按下标顺序输入叶子的权重:"<<endl;
for(i=0;i
cout<<i<<' ';
cout<<endl;
huffman(T,n);
cout<<"输出合并后的哈夫曼树的所有结点："<<endl;
for(i=0;i
cout<<i<<" ";
cout<<endl;
for(i=0;i
{
cout<<T.weight<<" ";
}
cout<<endl;
HFCode HC;
cout<<"请输入n个需要编码的字符:"<<endl;
CreateHuffmanCode(T,HC,n);
cout<<"哈夫曼编码:"<<endl;
OutputHuffmanCode(HC,n);
string Str;
cout<<"请输入要译码的二进制串"<<endl;
cin>>Str;
cout<<"哈夫曼译码:"<<endl;
Decoding(T,HC,n,Str);
system("pause");
return 0;
}
<IMG style="PADDING-BOTTOM: 0px; BORDER-RIGHT-WIDTH: 0px; LIST-STYLE-TYPE: none; MARGIN: 0px; PADDING-LEFT: 0px; PADDING-RIGHT: 0px; BORDER-TOP-WIDTH: 0px; BORDER-BOTTOM-WIDTH: 0px; BORDER-LEFT-WIDTH: 0px; PADDING-TOP: 0px; border-image: initial" title="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" alt="C++ 二叉树的创建 层序遍历 以及 哈夫曼树的编译码实现" src="http://s10.sinaimg.cn/mw690/0026ZEdigy6It2ImCaR49&690" width=434 height=367 action-type="show-slide" action-data="http%3A%2F%2Fs10.sinaimg.cn%2Fmw690%2F0026ZEdigy6It2ImCaR49%26690" real_src="http://s10.sinaimg.cn/mw690/0026ZEdigy6It2ImCaR49&690">
| 
