// -------- HuffmanTree.h

#include "MinHeap.h"
#include <iostream.h>


template <class T> class HuffmanTree;
template <class T>
class HuffmanTreeNode  {
	friend class HuffmanTree<T>;
private:
	T info;
	HuffmanTreeNode<T> *parent;
	HuffmanTreeNode<T> *left;
	HuffmanTreeNode<T> *right;	
public:
	HuffmanTreeNode() {};
	HuffmanTreeNode<T> *leftchild() {return left;};
	HuffmanTreeNode<T> *rightchild() {return right;};
//	bool operator > (HuffmanTreeNode<T> &HN) {return info > HN.info;}; // 注意要重載運算符
//	bool operator < (HuffmanTreeNode<T> &HN) {return info < HN.info;}; 
//	bool operator == (HuffmanTreeNode<T> &HN) {return info == HN.info;};
};

template <class T>
class HuffmanTree  {
private:
	HuffmanTreeNode<T>* root;					//Huffman樹的樹根

	//把ht1和ht2為根的Huffman子樹合并成一棵以parent為根的二叉樹
	void MergeTree ( HuffmanTreeNode<T> &ht1, HuffmanTreeNode<T> &ht2,  HuffmanTreeNode<T>* parent);
	
	void DeleteTree(HuffmanTreeNode<T>* root);//刪除Huffman樹或其子樹
public:
	//構造Huffman樹，weight是存儲權值的數組，n是數組長度
	HuffmanTree(T weight[],int n);	
	virtual ~HuffmanTree(){	DeleteTree(root);}; 	//析構函數

	void InOrder(HuffmanTreeNode<T> *root);          //中序周游 
	HuffmanTreeNode<T> *GetRoot() {return root;};

};

template<class T>
HuffmanTree<T>::HuffmanTree(T weight[], int n)  {
	MinHeap< HuffmanTreeNode<T> > heap(n);		//定義最小值堆
	HuffmanTreeNode<T> *parent, firstchild, secondchild;
	HuffmanTreeNode<T>* NodeList = new HuffmanTreeNode<T>[n];
	for(int i = 0;i < n;i++)  {    				//初始化
		NodeList[i].info = weight[i];
		NodeList[i].parent = NodeList[i].left = NodeList[i].right = NULL;
		heap.Insert(NodeList[i]);				//向堆中添加元素
	}
	
	for(i = 0;i < n-1;i++)  {               		//通過n-1次合并建立Huffman樹
		parent = new HuffmanTreeNode<T>;
		firstchild = heap.RemoveMin();				//選擇權值最小的結點
		secondchild = heap.RemoveMin();				//選擇權值次小的結點
		MergeTree(firstchild,secondchild,parent);	//合并權值最小的兩棵樹
		heap.Insert(*parent);					//把parent插入到堆中去
		root = parent;							//建立根結點
	}
	delete []NodeList;
}

template <class T>
void HuffmanTree<T>::DeleteTree(HuffmanTreeNode<T> *root)  {
	if (root)  	{
		DeleteTree(root->left);
		DeleteTree(root->right);
		delete root;
	}
}


template <class T>
void HuffmanTree<T>::InOrder(HuffmanTreeNode<T> *root)  { //中序周游
	if (root)  	{
		InOrder(root->left);
		cout << root->info << " ";
		InOrder(root->right);
	}
}


/*template <class T>
void HuffmanTree<T>::MergeTree(HuffmanTreeNode<T> &ht1, HuffmanTreeNode<T> &ht2, HuffmanTreeNode<T> *parent)  {
	HuffmanTreeNode<T> *l = new HuffmanTreeNode<T>();
	HuffmanTreeNode<T> *r = new HuffmanTreeNode<T>();
	
	*l = ht1; // 不能寫為l = &ht1，注意地址引用，開辟的是新空間，或者應用拷貝構造函數，只是有些麻煩
	*r = ht2;
	
	parent->parent = NULL;
	parent->left = l;
	parent->right = r;
	parent->info = ht1.info + ht2.info;
	ht1.parent = ht2.parent = parent; // 指向父節(jié)點
}*/