HuffmanTree.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

template<class T>
struct HuffmanTreeNode
{
	HuffmanTreeNode<T>* _left;
	HuffmanTreeNode<T>* _right;
	T _data;                        //這里的data实际上是权重(weight)
	HuffmanTreeNode(const T& d)
		:_data(d)
		, _left(NULL)
		, _right(NULL)
	{
	
	}
};
template<class T>
struct WeitLessThan        
{
	bool operator()(const HuffmanTreeNode<T>* _left, const HuffmanTreeNode<T>* _right) const
	{
		return _left->_data < _right->_data;
	}
};

template<class T>
class HuffmanTree
{
	typedef HuffmanTreeNode<T> Node;
private:
	Node* _root;
public:
	HuffmanTree()  //无参构造
		:_root(NULL)
	{
	}
	HuffmanTree(T* a,size_t n)         //传上来一个数组
	{
		//template<class T>                                            //刚开始我写模板参数列表的出错了，说模板声明只能再全局命名空间或者类范围内。 后来想我写一个内置类，还需要什么模板 就是Node*类型的
		//struct WeitLessThan         //這个结构体一定要放在這里吗？ 其实也可以放在上面
		//{
		//	bool operator()(const Node* _left, const Node* _right) const
		//	{
		//		return _left->_data < _right->_data;
		//	}
		//};

		//利用小堆选出数组中两个最小的数
		//建堆
		Heap<Node*, WeitLessThan<T>> minHeap;
		for (size_t i = 0; i < n; i++)
		{
			minHeap.Push(new Node(a[i]));
		}
		while (minHeap.Size()>1)                  //注意這里循环的条件 为什么是>1
		{
			                                   //选出权值最小的两个结点
			Node* left = minHeap.Top();
			minHeap.Pop();
			Node* right = minHeap.Top();
			minHeap.Pop();
			                                     //构造父结点然后三点相链
			Node* parent = new Node(left->_data + right->_data);
			parent->_left = left;
			parent->_right = right;
			                                    //链接好之后再放回去比较 // 注意：放回去比较没啥特别的，要知道是放回到数组里面，链接好的不会产生什么影响
			minHeap.Push(parent);
		}
		    _root = minHeap.Top();                 //注意：为什么這里是min.Top();
	}
	~HuffmanTree()
	{
		cout << "析构" << endl;
	}
};

void test()
{
	int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	HuffmanTree<int> h1(arr,sizeof(arr)/sizeof(arr[0]));

}
int main()
{
	test();
	return 0;
}