extbintree.h

来自「这些程序是本人学习数据结构时编的」· C头文件 代码 · 共 91 行

/////////////////////////////////////////////////////////////////////
// ExtBinTree.h: interface for the ExtBinTree class.
//
//  PROGRAM BY	:	SINGLE LAO
//  DATE		:   2004. 5. 25
//  VERSION		:	DEBUG 1.1 
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_EXTBINTREE_H__A976920E_955C_46E5_B481_2531A77D1EEA__INCLUDED_)
#define AFX_EXTBINTREE_H__A976920E_955C_46E5_B481_2531A77D1EEA__INCLUDED_

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


#include "MinHeap.cpp"
#include "MinHeap.h"

using namespace std;


template<class Type> class ExtBinTree;

template<class Type>
class Element
{
	friend class ExtBinTree<Type>;
	friend class Huffman;
private:
	Type data;
	Element<Type> *leftChild,*rightChild;
};

template<class Type>
class ExtBinTree  
{
friend class Huffman;
public:
	ExtBinTree()
	{
		root = new Element<Type>;
		root->leftChild = NULL;
		root->rightChild = NULL;
	};
	ExtBinTree(ExtBinTree<Type> & bt1,ExtBinTree<Type> & bt2)
	{
		root = new Element<Type>;
		root->leftChild = bt1.root;
		root ->rightChild = bt2.root;
		root->data = bt1.root->data + bt2.root->data;
		key = bt1.key + bt2.key;
	};
	void HuffmanTree(MinHeap<ExtBinTree<Type> >* hp,Type* fr,int n,ExtBinTree<Type> & newtree);
	int key;
protected:
	enum{DefaultSize = 256};
	Element<Type> * root;

};


template<class Type>
void ExtBinTree<Type>::HuffmanTree(MinHeap<ExtBinTree<Type> >* hp,Type* fr,int n,ExtBinTree<Type> & newtree)
{
	ExtBinTree<Type> first, second;
	ExtBinTree<Type> Node[DefaultSize];
	if (n > DefaultSize)
	{
		cerr<<"Size n"<< n<<"exceeds the boundary of Array"<<endl;
		return;
	}
	for (int i = 0; i<n; i++)
	{
		Node[i].root->data = fr[i];
		Node[i].root->leftChild  = NULL;
		Node[i].root ->rightChild = NULL;
		Node[i].key = fr[i].key;
	}
	hp = new  MinHeap<ExtBinTree<Type> >(Node,n);
	for (i= 0;i<n-1;i++)
	{
		hp->RemoveMin(first);
		hp->RemoveMin(second);
		newtree = *(new ExtBinTree<Type> (first,second) );
		hp->Insert(newtree);
	}
}
#endif // !defined(AFX_EXTBINTREE_H__A976920E_955C_46E5_B481_2531A77D1EEA__INCLUDED_)