数据结构Huffman头文件

#include"MinHeap.h"

class HuffmanTree;

class HuffmanNode //Huffman树节点类的定义
{
friend class HuffmanTree;
private:
int data;
char ch;
char path[100];
HuffmanNode *parent;
HuffmanNode *left;
HuffmanNode *right;
public:
HuffmanNode();
HuffmanNode *getParent();
HuffmanNode *Leftchild();
HuffmanNode *Rightchild();
bool isLeaf();
int getData();
char getCH();
char *getPath();
bool operator > (HuffmanNode h); //重载'>'
};

HuffmanNode::HuffmanNode() //构造函数
{
for(int i=0;i<100;i++)
path[i] = '\0';
parent = NULL;
left = NULL;
right = NULL;
}

HuffmanNode *HuffmanNode::getParent() //父节点
{
return parent;
}

HuffmanNode *HuffmanNode::Leftchild() //左子树
{
return left;
}

HuffmanNode *HuffmanNode::Rightchild() //右子树
{
return right;
}

bool HuffmanNode::isLeaf() //判断是否叶子节点
{
if((left == NULL) && (right == NULL))
return true;
else
return false;
}

int HuffmanNode::getData() //出现次数
{
return data;
}

char HuffmanNode::getCH() //节点里字符
{
return ch;
}

char *HuffmanNode::getPath() //路径
{
return path;
}

bool HuffmanNode::operator >(HuffmanNode h) //重载'>'
{
if(data > h.data)
return true;
else
return false;
}

//////////////////////////////////////////////////////////////////////////////////

class HuffmanTree //Huffman树类的定义
{
private:
HuffmanNode *root; //根节点
public:
HuffmanTree(int weight[], int n, HuffmanNode *LeafNode[]); //构造函数，并带回叶子节点位置
HuffmanNode *Root();
void MergeTree(HuffmanNode *tr1, HuffmanNode *tr2, HuffmanNode *t); //*(&t) 两棵树合并一棵树
void pre(HuffmanNode *r); //前序遍历
void Path(HuffmanNode *r); //得到所有的叶子节点的路径
void DeleteTree(HuffmanNode *r); //删除树
~HuffmanTree(); //析构函数
};

HuffmanTree::HuffmanTree(int weight[], int n, HuffmanNode *LeafNode[])
{
MinHeap< HuffmanNode > MyHeap(n);
HuffmanNode *parent_p , *firstchild, *secondchild ,temp;
HuffmanNode NodeList;
for(int i = 0; i < 128; i++)
{
if(weight[i] > 0)
{
NodeList.data = weight[i];
NodeList.ch = (char)i;
NodeList.parent = NULL;
NodeList.left = NULL;
NodeList.right = NULL;
MyHeap.Insert(NodeList);
}
}

int j = 0;
for(i = 0; i < n - 1; i++)
{
parent_p = new HuffmanNode; //每次开辟节点空间

if(MyHeap.Min().isLeaf()) //从最小堆中取出的元素如果是叶子节点，就开辟空间
{
firstchild = new HuffmanNode;
MyHeap.RemoveMin(*firstchild);
}
else //如果不是，直接赋值
{
MyHeap.RemoveMin(temp);
firstchild = temp.Leftchild()->parent;
}

if(MyHeap.Min().isLeaf()) //同上
{
secondchild = new HuffmanNode;
MyHeap.RemoveMin(*secondchild);
}
else
{
MyHeap.RemoveMin(temp);
secondchild = temp.Rightchild()->parent;
}

MergeTree(firstchild, secondchild, parent_p); //合并


if(firstchild->isLeaf()) //如果是叶子节点，带回
{
LeafNode[j] = firstchild;
j++;
}

if(secondchild->isLeaf()) //如果是叶子节点，带回
{
LeafNode[j] =secondchild;
j++;
}

if(i < n - 2) //进行 n - 3 次插入最小堆操作
MyHeap.Insert( *parent_p );
root = parent_p; //根节点重新赋值
}
}

HuffmanNode *HuffmanTree::Root()
{
return root;
}

void HuffmanTree::MergeTree(HuffmanNode *tr1, HuffmanNode *tr2, HuffmanNode *t) //*(&t)
{
t->parent = NULL;
t->left = tr1;
tr1->parent = t;

t->right = tr2;
tr2->parent = t;
t->data = tr1->data + tr2->data; //数值相加
}

void HuffmanTree::pre(HuffmanNode *r) //前序遍历，输出存放的值
{
if(r != NULL)
{
if(r->isLeaf())
cout<data<<" "<ch<<" "<path<pre(r->Leftchild());
pre(r->Rightchild());
}
}

void HuffmanTree::Path(HuffmanNode *r) //路径的获取
{
int i;
if(r != NULL)
{
if(r->left != NULL)
{
for(i = 0; i < 100; i++) //每次都将父节点的路径赋值给左右子节点
r->left->path[i] = r->right->path[i] = r->path[i];
r->left->path[strlen(r->left->path)] = '0';
r->right->path[strlen(r->right->path)] = '1';
}
/*else
{
word[t->c].c=t->c;
word[t->c].times=t->times;
strcpy(word[t->c].code,t->code);
}*/
Path(r->left);
Path(r->right);
}
}

void HuffmanTree::DeleteTree(HuffmanNode *r) //删除树
{
if(r != NULL)
{
DeleteTree(r->left);
DeleteTree(r->right);
delete r;
}
}

HuffmanTree::~HuffmanTree() //析构
{
DeleteTree(root);
}