// HuffmanTree.h: interface for the HuffmanTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_HUFFMANTREE_H__E2FE6C12_C0A9_4483_AF1B_9623F1FD0EF8__INCLUDED_)
#define AFX_HUFFMANTREE_H__E2FE6C12_C0A9_4483_AF1B_9623F1FD0EF8__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "HuffmanTreeNode.h"
#include "MinHeap.h"

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);
public:
	//構(gòu)造Huffman樹，weight是存儲權(quán)值的數(shù)組，n是數(shù)組長度
	HuffmanTree(T weight[],int n);
	//刪除Huffman樹或其子樹
	void DeleteTree(HuffmanTreeNode<T>* root);
	virtual ~HuffmanTree();							//析構(gòu)函數(shù)
};

template <class T>
void HuffmanTree<T>::MergeTree(HuffmanTreeNode<T> &ht1,HuffmanTreeNode<T> &ht2, HuffmanTreeNode<T>* parent)
{
	parent->left=&ht1;
	parent->right=&ht2;
	parent->element=ht1.element+ht2.element;
	parent->parent=NULL;
	ht1.parent=ht2.parent=parent;
}

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].element=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();				//選擇權(quán)值最小的結(jié)點(diǎn)
		secondchild=heap.RemoveMin();				//選擇權(quán)值次小的結(jié)點(diǎn)
		MergeTree(firstchild,secondchild,parent);	//合并權(quán)值最小的兩棵樹
		heap.Insert(*parent);						//把parent插入到堆中去
		root=parent;								//建立根結(jié)點(diǎn)
	}
	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>
virtual HuffmanTree<T>::~HuffmanTree()
{
	DeleteTree(root);
}

#endif // !defined(AFX_HUFFMANTREE_H__E2FE6C12_C0A9_4483_AF1B_9623F1FD0EF8__INCLUDED_)