binarytree.h

本程序中定义了霍夫曼类实现霍夫曼编码和解码

// 
// 二叉树类定义
//
// 二叉树节点类定义
template<class T, class M>
class BinaryTree;
class Huffman;
template <class T, class M>
class BinaryTreeNode {
	friend class BinaryTree<T,M>;
	friend class Huffman;
public:
	BinaryTreeNode() {LeftChild = RightChild = 0;}
	BinaryTreeNode(const T& e, const M& w)
	{data = e; weight = w; LeftChild = RightChild = 0;}
	BinaryTreeNode(const T& e, const M& w, BinaryTreeNode *l, BinaryTreeNode *r)
	{data = e; weight = w; LeftChild = l; RightChild = r;}
private:
	T data;
	M weight;
	BinaryTreeNode<T,M> *LeftChild, //左子树
		              *RightChild; // 右子树
};
// 二叉树类定义

template<class T, class M>
class BinaryTree {
	friend class Huffman;
public :
	BinaryTree() {root = 0; };
	~ BinaryTree() { };
	bool IsEmpty() const {reurn ((root) ? false : true);}
	bool Root(T& x) const;
	void MakeTree(const T& element, const M& weight, BinaryTree<T,M>& left, BinaryTree<T,M>& right);
	BinaryTree<T,M>& operator=(const BinaryTree<T,M>& x)
	{root = x.root; return *this;}
	bool operator>(const BinaryTree<T,M>& x);
	bool operator<=(const BinaryTree<T,M>& x);
private:
BinaryTreeNode<T,M> *root; // 根节点指针
};

template<class T, class M>
bool BinaryTree<T,M>::Root(T& x) const
{// 取根节点的data域，放入x
// 如果没有根节点，则返回false
	if (root) {x = root->data;
	return true;}
	else return false; // 没有根节点
}
// 合并一棵新树
template<class T, class M>
void BinaryTree<T,M>::MakeTree(const T& element, const M& weight, BinaryTree<T,M>& left, BinaryTree<T,M>& right)
{// 将left,right和element合并成一棵新树
// left, right和t h i s必须是不同的树
// 创建新树
	root = new BinaryTreeNode<T,M>(element, weight, left.root, right.root);
	// 阻止访问l e f t和r i g h t
	left.root = right.root = 0;
}

//重载操作符实现对树根节点中的weight的操作
template<class T, class M>
bool BinaryTree<T,M>::operator>(const BinaryTree<T,M>& x)
{
	if(root->weight > x.root->weight)
		return true;
	else return false;
}
template<class T, class M>
bool BinaryTree<T,M>::operator<=(const BinaryTree<T,M>& x)
{
	if(root->weight <= x.root->weight)
		return true;
	else return false;
}