哈夫曼树遍历译码.txt

该程序实现哈夫曼树的构建

typedef enum PointerTag{Link,Thread};
typedef struct BiThrNode{
	char data;
	struct BiThrNode *lchild,*rchild;
      PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
 char str[20];
void preCreateBiTree(BiThrTree &);
void preOrderTraversal(BiThrTree );
void inOrderTraversal(BiThrTree );
void postOrderTraversal(BiThrTree );
void inOrderThreading(BiThrTree &,BiThrTree);
void inOrderTraversal_thr(BiThrTree);
void InThreading(BiThrTree,BiThrTree &);
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int main()
{
 BiThrTree rootptr,thrt;
 cout<<"以先序方式输入元素 空格表示空结点 "<<endl;
  cout<<"输入字符"<<endl;
	cin.getline(str,20);
	preCreateBiTree(rootptr);
cout<<"preOrderTraversal(先序遍历)"<<endl;
preOrderTraversal(rootptr);
cout<<endl;
cout<<"inOrderTraversal(中序遍历)"<<endl;
inOrderTraversal(rootptr);
cout<<endl;
cout<<"postOrderTraversal(后序遍历)"<<endl;
postOrderTraversal(rootptr);
cout<<endl<<"中序线索化"<<endl;
inOrderThreading(thrt,rootptr);
cout<<"中序线索遍历"<<endl;
inOrderTraversal_thr(thrt);
cout<<endl;
return 0;
}
void preCreateBiTree(BiThrTree &ptr)
{ 
	static int i=0;
	char ch;
	ch=str[i++];
	if(ch==' ')
		ptr=NULL;
	else {
		if(!(ptr=(BiThrNode *)malloc(sizeof(BiThrNode))))
			exit(-2);
		ptr->data=ch;
		ptr->LTag=Link;
		ptr->RTag=Link;
     preCreateBiTree(ptr->lchild);
		 preCreateBiTree(ptr->rchild);
	}
}

void preOrderTraversal(BiThrTree ptr)
{  
	if(ptr)
	{
		cout<<(ptr->data)<<"   ";
        preOrderTraversal(ptr->lchild);
	    preOrderTraversal(ptr->rchild);
	}
}
void inOrderTraversal(BiThrTree ptr)
{
   if(ptr)
	{
        inOrderTraversal(ptr->lchild);
		cout<<(ptr->data)<<"   ";
	    inOrderTraversal(ptr->rchild);
	}
}
void postOrderTraversal(BiThrTree ptr)
{
   if(ptr)
	{
        postOrderTraversal(ptr->lchild);
	    postOrderTraversal(ptr->rchild);
		cout<<(ptr->data)<<"   ";
	}
}
void inOrderThreading(BiThrTree &thrt,BiThrTree t)
{
   BiThrTree pre;
	if(!(thrt=(BiThrTree)malloc(sizeof(BiThrNode))))
		exit(-2);
	thrt->LTag=Link;
	thrt->RTag=Thread;
	thrt->rchild=thrt;
	if(!t)
		thrt->lchild=thrt;
	else{
		thrt->lchild=t;
		pre=thrt;
		InThreading(t,pre);
		pre->rchild=thrt;
		pre->RTag=Thread;
		thrt->rchild=pre;
}
}
void InThreading(BiThrTree p,BiThrTree &pre)
{
	if(p){
    InThreading(p->lchild,pre);
	if(!p->lchild){
		p->LTag = Thread;
		p->lchild = pre;}//前驱线索
	if(!pre->rchild){
		pre->RTag = Thread;
		pre->rchild = p;}//后驱线索
	pre = p;
   InThreading(p->rchild,pre);
}
}
void inOrderTraversal_thr(BiThrTree thrt)
{
   BiThrTree p = thrt->lchild;
   while(p!=thrt){
	   while(p->LTag==Link)
		   p = p->lchild;
	   cout<<p->data<<"  ";
	   while(p->RTag==Thread&&p->rchild!=thrt){
		   p = p->rchild;
		   cout<<p->data<<"  "; 
	   }
	   p = p->rchild;
   }
}

哈夫曼树：
#include<iostream.h>
#define MAX  30//最大结点数；
typedef struct//Huffman树结点定义；
{
	char data;
	int weight;
	int parent;
	int lchild;
	int rchild;
}huffnode;
typedef struct //编码结点定义；
{
	char cd[MAX];
	int start;
}huffcode;
//主函数
void main()
{
	huffnode ht[2*MAX];
	huffcode hcd[MAX],d;
	int n;
	cout<<"输入要编码的语句字符集所包含的元素个数:";
	cin>>n;
	int i;
	for(i=1;i<=n;i++)//输入元素值
	{
		cout<<"输入第"<<i<<"个元素->\t结点值:";
		cin>>ht[i].data;
		cout<<"\t\t权重:";
		cin>>ht[i].weight;
	}
	int k;
	for(i=1;i<=2*n-1;i++)
	ht[i].parent=ht[i].lchild=ht[i].rchild=0;
	int m1,m2,l,r;
	for(i=n+1;i<=2*n-1;i++)
	{
		m1=m2=1000;
		l=r=0;
		for(k=1;k<=i-1;k++)
		{
			if(ht[k].parent==0)
				if(ht[k].weight<m1)
				{
					m2=m1;
					r=l;
					m1=ht[k].weight;
					l=k;
				}
				else if(ht[k].weight<m2)
				{
					m2=ht[k].weight;
					r=k;
				}
		}//此for循环寻找最小权重l,r;
		ht[l].parent=i;
		ht[r].parent=i;
		ht[i].lchild=l;
		ht[i].rchild=r;
		ht[i].weight=ht[l].weight+ht[r].weight;
	}//以上构造Huffman树
	int c,f;
	for(i=1;i<=n;i++)
	{
		d.start=n+1;
		c=i;
		f=ht[i].parent;
		while(f!=0)
		{
			if(ht[f].lchild==c)
				d.cd[--d.start]='0';
			else d.cd[--d.start]='1';
			c=f;
			f=ht[f].parent;
		}
		hcd[i]=d;
	}
	cout<<"Huffman编码输出:\n";
	for(i=1;i<=n;i++)
	{
		cout<<" "<<ht[i].data<<":";
		for(k=hcd[i].start;k<=n;k++)
			cout<<hcd[i].cd[k];
		cout<<endl;
	}
	int lenth;
	cout<<"输入编码电文的总长:";
	cin>>lenth;
	cout<<"输入电文所含的字符总数:";
	int lenth1;
	cin>>lenth1;
	cout<<"输入要编译的编码序列:\n";
	char ch[1000];
	for(i=1;i<=lenth;i++)
		cin>>ch[i];
	int j=1;
	cout<<"以下语句为译玛:\n";
	cout<<"\t\t\t";
	for(i=1;i<=lenth1;i++)
	{	f=2*n-1;
		while(ht[f].lchild!=0)
		{
			if(ch[j]=='0')
				f=ht[f].lchild;
			else f=ht[f].rchild;
			j++;
		}
		cout<<ht[f].data;
	}//以上for循环为译码;
	cout<<"\n";
}