tree.h

二叉树的基本操作

template<class TElem>
class Node{
public:
	TElem value;
	Node *lc,*rc;
	Node *father;
	Node *Getson(char no)
	{
		return(no==1?lc:rc);
	}
	Node* Getfather()
	{
		return father;
	}
	void Setson(char no,Node *obj)
	{
		(no==1?lc:rc)=obj;
	}
	Node()
	{
		father=lc=rc=NULL;
	}
};
template <class TElem>
class Tree{
public:
	//Node *poTElems;
	Node<TElem> *root;
	void Clusterpre(TElem **e)
	{
		int temp=0;
		Clusterpre(root,e,temp);
	}
	void Clusterin(TElem **e)
	{
		int temp=0;
		Clusterin(root,e,temp);
	}
	void Inpretotree(TElem a[],TElem b[])
	{
		extern int n;
		root=Inpretotree(a,b,0,n-1,0,n-1);
	}
	void Clusterpost(TElem **e)
	{
		int temp=0;
		Clusterpost(root,e,temp);
	}
protected:
	void Clusterpre(Node<TElem>*pnode,TElem **obj,int &cnt)
	{
		if(pnode==NULL) return;
		obj[cnt++]=&(pnode->value);
		Clusterpre(pnode->Getson(1),obj,cnt);
		Clusterpre(pnode->Getson(2),obj,cnt);
	}
	void Clusterin(Node<TElem> *pnode,TElem **e,int &cnt)
	{
		if(pnode==NULL)return;
		Clusterin(pnode->Getson(1),e,cnt);
		e[cnt++]=&(pnode->value);
		Clusterin(pnode->Getson(2),e,cnt);
	}
	void Clusterpost(Node<TElem> *pnode,TElem **e,int &cnt)
	{
		if(pnode==NULL)return;
		Clusterpost(pnode->Getson(1),e,cnt);
		Clusterpost(pnode->Getson(2),e,cnt);
		e[cnt++]=&(pnode->value);
	}
	Node<TElem>* Inpretotree(TElem *pa,TElem *ia,int p1,int p2,int i1,int i2)
	{
		Node<TElem> *p;
		if(i1>i2)return NULL;
		int k=0;
		while(pa[p1]!=ia[i1+k])k++;
		p=new Node<TElem>;
		p->value=pa[p1];
		p->Setson(1,Inpretotree(pa,ia,p1+1,p1+k,i1,i1+k-1));
		p->Setson(2,Inpretotree(pa,ia,p1+k+1,p2,i1+k+1,i2));
		if(p->Getson(1)!=NULL)p->Getson(1)->father=p;
		if(p->Getson(2)!=NULL)p->Getson(2)->father=p;
		return p;
	}
};