huffman.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

/////////////////////////// 
//    // 
//   二叉树数据结构  Huffman.h       // 
//    // 
////////////////////////// 
#include"stack.h"
#include<iostream.h> 
template<class Type>class Huffman; 
template<class Type> //定义二叉树的结点类
class TreeNode 
{ 
  public: 
	friend class Huffman<Type>; 
	TreeNode():lchild(NULL),rchild(NULL){} //构造
	Type data; 
	TreeNode *lchild;  //左，右子树 
	TreeNode *rchild; 
}; 

template<class Type> //定义二叉树类
class Huffman 
{ 
public: 
	Huffman();
	void CreatTree();               //创建二叉树,主过程 
	void CreatTree(TreeNode<Type>* child,int k); //子过程 
	void PreOrderN(TreeNode<Type> *point);     //先序遍历二叉树 
	TreeNode<Type> *CreatHuffman();
	void Code(TreeNode<Type> *point,int n);
	void Destroy(TreeNode<Type> *point);     //销毁二叉树 
	bool IsEmpty(); 
	int Depth(TreeNode<Type> *point);//返回以point根结点的子树的深度
	int CountNode(TreeNode<Type> *point);
	TreeNode<Type> *GetRoot(){return root;}
	void SetRoot(const TreeNode<Type> *point){root=point;}
private: 
	TreeNode<Type>* root; 
	Type *arr;
	int size;
}; 

template <class Type>
Huffman<Type>::Huffman()
{
	size=0;
	CreatTree();
}

template<class Type> 
void Huffman<Type>::CreatTree() 
{ 
	CreatTree(root,1); 
} 

template<class Type> 
void Huffman<Type>::CreatTree(TreeNode<Type>* child,int k) 
{ 
	TreeNode<Type>* point; 
	point=new TreeNode<Type>; 
	cout<<"输入节点数据项 :"; 
	cin>>point->data; 
	switch(k) 
	{ 
		case 1: root=point; break; 
		case 2: child->lchild=point;break; 
		case 3: child->rchild=point;break; 
	} 
	char temp; 
	cout<<"该"<<point->data<<"节点是否有左子树 Y / 任意键 :"; 
	cin>>temp; 
	if(temp=='y'||temp=='Y') 
	{ 
		CreatTree(point,2); 
	} 
	cout<<"该"<<point->data<<"节点是否有右子树 Y / 任意键 :"; 
	cin>>temp; 
	if(temp=='y'||temp=='Y') 
	{ 
		CreatTree(point,3); 
	} 
} 

template<class Type>
void Huffman<Type>::PreOrderN(TreeNode<Type> *point)	//先序的非递归算法
{
	size=0;
	arr=new Type[20];
	Stack<TreeNode<Type> *> stk;
	while(!stk.IsEmpty()||point!=NULL)//当point不为空或栈不为空时遍历
	{
		while(point!=NULL)
		{
			arr[size++]=point->data;
			if(point->rchild!=NULL)
				stk.Push(point->rchild);//右结点入栈
			point=point->lchild;		//遍历左结点
		}
		if(!stk.IsEmpty())point=stk.Pop();
	}
}

template<class Type>
int Huffman<Type>::Depth(TreeNode<Type> *point)
{
	if(point==NULL)
		return 0;
	else
	{
		int dep1=Depth(point->lchild);
		int dep2=Depth(point->rchild);
		if(dep1>dep2)
			return dep1+1;
		else
			return dep2+1;
	}	
}

template<class Type>
int Huffman<Type>::CountNode(TreeNode<Type> *point)
{
	if(point==NULL)
		return 0;
	else
		return CountNode(point->rchild)+CountNode(point->lchild)+1;
}

template<class Type> 
void Huffman<Type>::Destroy(TreeNode<Type> *point) 
{ 
	if(point!=NULL) 
	{ 
		Destroy(point->lchild); 
		Destroy(point->rchild); 
		delete point; 
	} 
}

template <class Type>
TreeNode<Type> *Huffman<Type>::CreatHuffman()
{
	PreOrderN(root);
	TreeNode<Type> **b,*q;
	b=new TreeNode<Type> *[size+1];
	int i,j;
	for(i=0;i<size;i++)		//初始化b数组，使每个指针元素指向a数组对应元素的结点
	{
		b[i]=new TreeNode<Type>;
		b[i]->data=arr[i];
		b[i]->lchild=b[i]->rchild=NULL;
	}
	for(i=1;i<size;i++)
	{
		int k1=-1,k2;		//让k1表示森林中具有最小权值的树根结点的下标
		for(j=0;j<size;j++)	//让k2表示森林中具有次小权值的树根结点的下标
		{
			if(b[j]!=NULL&&k1==-1){k1=j;continue;}
			if(b[j]!=NULL){k2=j;break;}
		}					
		for(j=k2;j<size;j++)//从当前森林中找出最小值和次小值
		{
			if(b[j]!=NULL)
			{
				if(b[j]->data<b[k1]->data){k2=k1;k1=j;}
				else if(b[j]->data<b[k2]->data)k2=j;
			}
		}
		q=new TreeNode<Type>;			//由最小权值和次小权值建立一棵新树，指向树的根结点
		q->data=b[k1]->data+b[k2]->data;
		q->lchild=b[k1];q->rchild=b[k2];
		b[k1]=q;b[k2]=NULL;				//将指向新树的指针赋给b指针数组中k1位置，k2位置置为空
	}
	delete []b;
	return q;
}
template <class Type>
void Huffman<Type>::Code(TreeNode<Type> *point,int len)
{
	static int a[10];			//数组的维数要比树的深度大1
	if(point!=NULL)
	{
		if(point->lchild==NULL&&point->rchild==NULL)
		{
			cout<<"the node   "<<point->data<<"  code";
			for(int i=0;i<len;i++)
				cout<<a[i]<<setw(3);
			cout<<endl;
		}
		else
		{
			a[len]=0;Code(point->lchild,len+1);
			a[len]=1;Code(point->rchild,len+1);
		}
	}
}