huffmantree.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#ifndef HAFFMANTREE_H
#define HAFFMANTREE_H
#include "Heap.h"
#include<iostream>
template <class T, class E>
struct HuffmanNode {								//Huffman树结点的类定义
	E data;   										//结点的数据
	HuffmanNode<T,E> * leftChild, * rightChild, * parent;
	//左、右子女和父结点指针
	HuffmanNode() : leftChild(NULL),rightChild(NULL),parent(NULL) {}
	//构造函数
	HuffmanNode(E elem, HuffmanNode<T,E> * pr ,	//构造函数  //=NULL
		HuffmanNode<T,E> * left , HuffmanNode<T,E> * right ) 
		:data(elem),parent(pr),leftChild(left),rightChild(right) {}
	//重载操作符：
	bool operator> (HuffmanNode<T,E>  right) { return data>right.data; }
	bool 	operator>= (HuffmanNode<T,E>  right) { return (data>right.data) || (data==right.data); }
	bool 	operator< (HuffmanNode<T,E>  right) { return data<right.data; }
	bool 	operator<= (HuffmanNode<T,E>  right) { return (data<right.data) || (data==right.data); }
	bool 	operator== (HuffmanNode<T,E>  right) { return data==right.data; }
};
template <class T, class E>
class HuffmanTree {									//Huffman树类定义
public:
	HuffmanTree(E w[], int n);						//构造函数
	HuffmanNode<T,E> * getRoot()  {return root;}  //取根结点
protected:
	HuffmanNode<T, E> *root;	     //树的根
	void deleteTree (HuffmanNode<T, E> *t);			//删除以 t 为根的子树
	void mergeTree (HuffmanNode<T, E> ht1,HuffmanNode<T, E> ht2,   
		HuffmanNode<T, E> *& parent);
};
template <class T, class E>
HuffmanTree<T,E>::HuffmanTree(E w[], int n) {
	//给出n个权值w[1]～w[n], 构造Huffman树
	MinHeap<T, HuffmanNode<T,E> > hp;						//使用最小堆存放森林的结点
	HuffmanNode<T,E> * parent = new HuffmanNode<T,E>;
	HuffmanNode<T, E> first, second;
	HuffmanNode<T, E> *NodeList = new HuffmanNode<T,E>[n];    //森林
	for (int i = 0; i < n; i++) {
		NodeList[i].data = w[i+1];
		NodeList[i].leftChild = NULL;
		NodeList[i].rightChild = NULL;
		NodeList[i].parent = NULL;
		hp.Insert(NodeList[i]);	//插入最小堆中
	}
	for (int i = 0; i < n-1; i++) {	//n-1趟, 建Huffman树
		hp.RemoveMin (first); 		//根权值最小的树
		hp.RemoveMin (second);	//根权值次小的树
		mergeTree (first, second, parent);	//合并
		hp.Insert ( * parent);		//重新插入堆中
		root = parent;		//建立根结点
		cout<<"       root = "<<root->data<<endl;
	}
};

template <class T, class E>
void HuffmanTree<T, E>::
mergeTree (HuffmanNode<T, E> bt1, 	HuffmanNode<T, E> bt2, HuffmanNode<T, E> *& parent) 
{
	parent = new HuffmanNode<T,E>;
	parent->leftChild = &bt1;
	parent->rightChild = &bt2;
	parent->data= bt1.data+bt2.data;
	bt1.parent = bt2.parent = parent;
	cout<<bt1.data<<" 和 "<<bt2.data<<" 合并为："<<parent->data<<endl;
};

#endif;