bintree3p.h

是编译器我花了好几个礼拜才编好的确实难的这是个不错的编译器

/********************************************************
					自建模板库 树
					  作者:李芳
*********************************************************/

/********************************************************
使用说明：
1）void reportError(char info[],int length)函数用于报告错误
在不同平台下请自己编写
*********************************************************/

#if !defined(BINTREE3PHFILE)
#define BINTREE3PHFILE


#include <stack>		
#include <vector>		
#include <queue>		
using namespace std;



template <class MYT>
class CBinTree3P;

class CHuffmanTree;

void CreatTree(CBinTree3P<char> & tree, char * data , int len);




template <class MYTN>
class CBinTreNode
{
public:
	CBinTreNode(MYTN d,CBinTreNode<MYTN> * lp=0, CBinTreNode<MYTN> *rp=0,CBinTreNode<MYTN> *pp = 0)
		:m_MData(d),m_pLefC(lp),m_pRigC(rp),m_pParent(pp)	{}
	CBinTreNode(CBinTreNode<MYTN> * lp=0, CBinTreNode<MYTN> *rp=0,CBinTreNode<MYTN> *pp = 0)
		:m_pLefC(lp),m_pRigC(rp),m_pParent(pp)		{}
public:
	CBinTreNode<MYTN> * m_pLefC,* m_pRigC, *m_pParent;
	MYTN m_MData;
};



/****************************************************************
****************************************************************/

template <class MYT>
class CBinTree3P  
{

	friend void CreatTree(CBinTree3P<char> & tree, char * data , int len);
	friend class CView;
public:
	CBinTree3P(){								//构造空的二叉树
		m_pRoot = NULL;
	}

	CBinTree3P(MYT d){							//构造二叉树
 	m_pRoot = new CBinTreNode<MYT>(d);			//并初始化根节点
	}

	bool IsEmpty(){
		return m_pRoot == NULL;
	}
	CBinTreNode<MYT> * GetRoot(){
		return m_pRoot;
	}
	CBinTreNode<MYT>* LeftChild(CBinTreNode<MYT> *p){
		return p == 0 ? 0 : p->m_pLefC;	
	}
	CBinTreNode<MYT>* RightChild(CBinTreNode<MYT> *p){	
		return ( p == 0 ? 0 : p->m_pRigC );	
	}
	MYT Retrieve(CBinTreNode<MYT> *p){				//取该节点的数据
		return p->m_MData;
	}
	bool Assign (CBinTreNode<MYT> *p,MYT d)	{
		return (p == 0) ? false : (p->m_MData = d ,true) ;
	}
	void CreatRoot(MYT d){
		if(IsEmpty())			//注意只能用于刚刚创建的二叉树
			m_pRoot = new CBinTreNode<MYT>(d);	//否则可能会出现内存遗漏
		else
			reportError("错误，对空树CREATROOT",21);
	}

	
public:

	CBinTreNode<MYT> * InsertLefC(CBinTreNode<MYT> *p,MYT d){
		CBinTreNode<MYT> * q = 0;
		if(p == NULL) reportError("空指针不能插入左孩子",20);
		else{
			q = new CBinTreNode<MYT>(d);
			q->m_pLefC = p->m_pLefC;
			q->m_pParent = p;
			p->m_pLefC = q;

			if(q->m_pLefC != NULL) q->m_pLefC->m_pParent = q;
		}
		return q;
	}


	CBinTreNode<MYT> * InsertRigC(CBinTreNode<MYT> *p,MYT d){
		CBinTreNode<MYT> * q = 0;
		if(p == NULL) reportError("空指针不能插入右孩子",20);	
		else{
			q = new CBinTreNode<MYT>(d);
			q->m_pRigC = p->m_pRigC;
			q->m_pParent = p;
			p->m_pRigC = q;

			if(q->m_pRigC != NULL) q->m_pRigC->m_pParent = q;
		}
		return q;
	}
    
	
	void Clear(){
		 Destroy(m_pRoot); 
		 m_pRoot = 0;
	}

	void Destroy(CBinTreNode<MYT> *p){
		 if(p){
			 Destroy(p->m_pLefC);
		     p->m_pLefC = 0;
		     Destroy(p->m_pRigC);
		     p->m_pRigC = 0;
		     delete p;
		 }
	}




	void PreOrder(){
		m_veOrderRes.clear();
		PreOrder(m_pRoot);
	}


	void PreOrder(CBinTreNode<MYT> *p){
		if(p != NULL)
		{
			m_veOrderRes.push_back(p);
			PreOrder(p->m_pLefC);
			PreOrder(p->m_pRigC);
		}
	}

	void InOrder(){
		m_veOrderRes.clear();
		InOrder(m_pRoot);
	}


	void InOrder(CBinTreNode<MYT> *p){
		if(p != 0)
		{
			InOrder(p->m_pLefC);
			m_veOrderRes.push_back(p);
			InOrder(p->m_pRigC);
		}
	}
	void PostOrder(){
		m_veOrderRes.clear();
		PostOrder(m_pRoot);
	}


	void PostOrder(CBinTreNode<MYT> *p){
		if(p != 0)
		{
			PostOrder(p->m_pLefC);
			PostOrder(p->m_pRigC);
			m_veOrderRes.push_back(p);
		}
	}

	
	void LevOrder(){

		m_veOrderRes.clear();
		queue< CBinTreNode<MYT>* > quPos;
		CBinTreNode<MYT> *pPos = m_pRoot;
		if (pPos == NULL){
				reportError("该树为空!",9); 
				return;
		}
		quPos.push(pPos);
		while(!quPos.empty()){
			pPos = quPos.front();
			quPos.pop();
			m_veOrderRes.push_back(pPos);
			if(pPos->m_pLefC != NULL) quPos.push(pPos->m_pLefC);
			if(pPos->m_pRigC != NULL) quPos.push(pPos->m_pRigC);
		}
   
	}




/****************************************************************

 临时测试函数 用于输出vector< CBinTreNode<MYT>* > m_veOrderRes

****************************************************************/


	void Print() const{
		cout<<endl;
		int len = m_veOrderRes.size();
		for(int i = 0 ;i<len;i++)
		{
			cout<<m_veOrderRes[i] ->m_MData;
		}

	}

                      


protected:
	CBinTreNode<MYT> * m_pRoot;
	vector< CBinTreNode<MYT>* > m_veOrderRes;
};








#endif