哈夫曼树的建立 任务：建立最优二叉树函数

HuffmanTree.h文件
#include
#include
#include
using namespace std;

class HTNode
{
friend class MyHuffmanTree;
public:
char charater;//元素值(字符)
int weight;//权值(频率)
string code;//Huffman编码
HTNode *left;//左孩子
HTNode *right;//右孩子

HTNode (char c=0, int w=0)
{ charater=c; weight=w; left=right=NULL; }

bool operator > (HTNode & target)
{
if( weight > target.weight )
return true;
else return false;
}//operator>

bool operator > (HTNode * target)
{
if( weight > target->weight )
return true;
else return false;
}

friend ostream & operator << (ostream &cout, HTNode * target)
{
cout<<"char: "<charater<<"\t"<<"weight: "<weight<<" "<code< return cout;
}
};

class MyHuffmanTree
{
private:
HTNode *root;
void visit(HTNode * target)
{
if(NULL==target->right && NULL==target->left)
cout<charater<<" "<weight<<" "<code< }
void HuffmanCode(HTNode *root)
{
//以前序周游的思想编码
root->code="";//root的Huffman编码
stack< HTNode * > aStack;//存储未访问元素的栈
HTNode * temp =root;
aStack.push(NULL);//栈底监视哨
while(temp)
{
if(NULL != temp->right )
{
temp->right->code=temp->code + "1";
aStack.push(temp->right);
}
if( NULL != temp->left )
{
temp->left->code=temp->code + "0";
temp=temp->left;
}
else//左子树访问完毕，转向访问右子树
{
temp=aStack.top();
aStack.pop();
}
}//while
}//Huffman编码函数
public:
MyHuffmanTree(HTNode * r)
{
root=r;
HuffmanCode(root);
}//构造函数

~MyHuffmanTree(){DeleteTree(root);} //析构函数
void DeleteTree(HTNode *root)
{
if(NULL!=root)
{
DeleteTree(root->left);
DeleteTree(root->right);
}
delete root;
}//销毁树函数
void InOrder(HTNode * root)
{
if(NULL!=root)
{
InOrder(root->left);
visit(root);
InOrder(root->right);
}
}//中序周游
HTNode * Root() {return root;}//返回跟结点函数

};
main文件
#include "HuffmanTree.h"
#include "MinHeap.h"
#include
#include
#include
using namespace std;

int main ()
{
int f[128]={0};//频率表
char c;//读入字符
//打开文件
ifstream fin("input.txt");
if(!fin)
{ cout<<"cannot open input.txt"; return 0; }
//从文件中读入数据
while(!fin.eof())
{
fin>>c;
f[c]++;
}

MinHeap< HTNode * > heap(128);
HTNode * p;//建堆用指针
HTNode *first , * second , *pa;
for(int i=0;i<128;i++)
{
if( 0 != f[i] )
{
p=new HTNode(i,f[i]);
heap.insert(p);
}//if
}//for,建最小堆
heap.display();

while( 1 != heap.GetCurrentSize() )//n-1次合并
{
first=heap.min();//取得最小的一个结点
heap.remove(0);
second=heap.min();//取得第二小的一个结点
heap.remove(0);
pa=new HTNode(0,first->weight+second->weight);
pa->left=first;
pa->right=second;
heap.insert(pa);
}
pa=heap.min();
heap.remove(0);
MyHuffmanTree mht(pa);
mht.InOrder(mht.Root());
return 0;
}
最小堆MinHeap.h文件
#include
using namespace std;

template < class T >
class MinHeap
{
private:
T * heapArray ; //存放堆数据的数组
int CurrentSize ; //当前堆中的元素数目
int MaxSize ; //最大元素数目
void swap( int pos_x, int pos_y ) //交换位置xy的元素的函数
{
if( pos_x<0 || pos_y<0 ) return ;
T temp ;
temp=heapArray[pos_x];
heapArray[pos_x]=heapArray[pos_y];
heapArray[pos_y]=temp;
}
public:
MinHeap( const int size ) //构造函数，size为堆的最大元素数目
{
if( size<=0 ) return ;
CurrentSize = 0 ;
MaxSize = size ;
heapArray = new T[MaxSize];
}
~MinHeap() { delete [] heapArray; } //析构函数

bool isEmpty() //判断堆是否为空的函数
{ return ( (CurrentSize==0) ? true : false ) ;}
bool isLeaf( int pos ) //判断是否是叶子结点的函数
{ return ( pos >= CurrentSize/2) && ( pos < CurrentSize ); }
int leftchild( int pos ) //返回左孩子位置的函数
{ return ( 2 * pos + 1 ); }
int rightchild( int pos )//返回右孩子位置的函数
{ return ( 2 * pos + 2 ); }
int Parent( int pos ) //返回父结点位置的函数
{ return ( (pos-1) / 2 ); }
int Pos( T value ) //找出值为value的元素在堆中位置的函数
{
for(int i=0; i {
if( heapArray[i] == value )
return i ;
}
return -1 ;
}//pos
bool insert( const T & newNode )//向堆中插入新元素newNode
{
//判断堆是否已满
if ( CurrentSize == MaxSize )//堆已满
{ cout<<"堆已满"< //堆未满
heapArray[CurrentSize]= newNode ;//新元素newNode放到堆的末尾
SiftUp( CurrentSize ); //向上调整
CurrentSize ++ ; //堆的当前元素数加1
return true ;
}//insert
bool remove( int pos)//删除给定下标的元素
{//判断下标是否越界
if ( (pos < 0) || (pos >= CurrentSize) )
return false ;
//下标未越界
heapArray[pos]=heapArray[--CurrentSize];//用最后的元素值代替被删除的元素
if( pos == 0 )
SiftDown(pos);
if ( heapArray[Parent(pos)] > heapArray[pos] )
SiftUp(pos);
else SiftDown(pos);
return true ;
}//remove
T & min() //返回最小值元素
{ return heapArray[0] ; }
void SiftUp( int pos ) //从pos开始向上调整
{
int temppos=pos;
T temp = heapArray[temppos];
while( (temppos>0) && (heapArray[Parent(temppos)] > temp) )
{
heapArray[temppos]=heapArray[Parent(temppos)];
temppos=Parent(temppos);
}
heapArray[temppos]=temp ;
}//SiftUp
void SiftDown ( int pos )//从pos开始向下调整
{
int i = pos ; //标识父结点
int j = leftchild(i);//用于记录关键值较小的子结点
T temp = heapArray[i];//记录父结点元素值
while( j < CurrentSize)
{
if( (j < CurrentSize-1 ) && (heapArray[j] > heapArray[j+1]) )//若有右子结点且小于左子结点
j++; //j指向小的右子结点
if ( temp > heapArray[j] )//若父结点的值大于子结点的值则交换
{
heapArray[i]=heapArray[j];
i=j;
j=leftchild(j);
}//if
else break ; //父结点<=子结点满足堆序跳出
}//while
heapArray[i]=temp;
}//SiftDown
void display()//显示堆中内容
{
// int level=1;
// int count=0;
int i ;
for(i=0; i {/*
if( count==level )
{
count=0;
level=level*2;
cout< }*/
cout< // count++;
}

}//display
T & RemoveMin()
{
if(CurrentSize==0){
cout<<"Cannot Delete";
exit(1);}//if
else
{
swap(0,--CurrentSize);
if(CurrentSize > 1)
SiftDown(0);
return heapArray[CurrentSize];
}//else
}//RemoveMin
int GetCurrentSize()
{return CurrentSize ;}
};

//别忘了自己建个input.txt输入文件

这棵树有碗口大的那么粗