binarytree.h

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

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

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



#if !defined(BINARYTREEHFILE)
#define BINARYTREEHFILE

/**********************************************************
该二叉树中用到的标准模板类如下
要注意添加头文件
***********************************************************/
#include <iostream>			//要改动的代码
#include <stack>		
#include <vector>		
#include <queue>		
using namespace std;		


template <class MYT>
class BinaryTree;

void CreatTree(BinaryTree<char> & tree, char * data , int len);
void reportError(char info[],int length);	//错误提示函数




template <class MYTN>
class BinTreNode
{
	friend class BinaryTree<MYTN>;
public:
	BinTreNode(MYTN d,BinTreNode<MYTN> * lp=0, BinTreNode<MYTN> *rp=0)
		:m_MData(d),m_pLefC(lp),m_pRigC(rp)	{}
	BinTreNode(BinTreNode<MYTN> * lp=0, BinTreNode<MYTN> *rp=0)
		:m_pLefC(lp),m_pRigC(rp)			{}
private:
	BinTreNode<MYTN> * m_pLefC,* m_pRigC;
	MYTN m_MData;
};



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

template <class MYT>
class BinaryTree  
{

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

public:
	BinaryTree(){								//构造空的二叉树
		m_pRoot = NULL;
	}

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

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

	
public:

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


	BinTreNode<MYT> * InsertRigC(BinTreNode<MYT> *p,MYT d){
		BinTreNode<MYT> * q = 0;
		if(p == NULL) reportError("空指针不能插入右孩子",20);	
		else{
			q = new BinTreNode<MYT>(d);
			q->m_pRigC = p->m_pRigC;
			p->m_pRigC = q;
		}
		return q;
	}
    
	
	void Clear(){
		 Destroy(m_pRoot); 
		 m_pRoot = 0;
	}

	void Destroy(BinTreNode<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(BinTreNode<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(BinTreNode<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(BinTreNode<MYT> *p){
		if(p != 0)
		{
			PostOrder(p->m_pLefC);
			PostOrder(p->m_pRigC);
			m_veOrderRes.push_back(p);
		}
	}

	
	void LevOrder(){

		m_veOrderRes.clear();
		queue< BinTreNode<MYT>* > quPos;
		BinTreNode<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< BinTreNode<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;
		}

	}

                      


private:
	BinTreNode<MYT> * m_pRoot;
	vector< BinTreNode<MYT>* > m_veOrderRes;
};









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




void reportError(char info[],int length)	//错误提示函数
{
	for(int i=0;i < length; i++)
		cerr<<info[i];
	cerr<<endl;
}





/****************************************************************
用字符串初始化数 按先序顺序输入 "空"用 
****************************************************************/

void CreatTree(BinaryTree<char> & tree, char * data , int len)
{
	 stack<BinTreNode<char> *> skPos;				//保存应插入的地址
	 stack<bool> skIsRig;					//判断插入位置是否在右侧 

	 tree.CreatRoot(data[0]);
	 BinTreNode<char> * pPos = tree.m_pRoot;
	 skPos.push(pPos);
	 skIsRig.push(false);
 	 
	 for(int i = 1;i<len && !skPos.empty();i++){
	 	if(data[i] == '#'){
			 if(skIsRig.top() == false){
          		  		skIsRig.pop();
          		  		skIsRig.push(true);
          		  		continue;
	            }
	         else{
          		  		skPos.pop();
          		  		skIsRig.pop();
          		  		continue;
	            }
	 	}
	     else{
	          if(skIsRig.top() == false){
	      		  		 pPos = tree.InsertLefC(skPos.top(),data[i]);
	      		  		 skIsRig.pop();
	      		  		 skIsRig.push(true);
	      		  		 skPos.push(pPos);
	      		  		 skIsRig.push(false);
	      		  		continue;
	           }
	           else{
	                     pPos = tree.InsertRigC(skPos.top(),data[i]);
	                     skIsRig.pop();
	                     skPos.pop();
	                     skPos.push(pPos);
	                     skIsRig.push(false);
	      		  		continue;
	           }
	    }
	}
	if(!skPos.empty() || i< len ) reportError("！！！创建二叉树指令字符串错误",30);

}


#endif