binarytree.h

本程序是实现二叉树跟树的常用算法

#include<iostream>
#include<math.h>
#include<assert.h>
#include"stack.h"
#include"queue.h"
using namespace std;

struct Level{
	
	int yLevel;
    
	int xIndent;
};

template<typename T>class BinaryTree;

template<typename T>class BinaryTreeNode{

public:

	BinaryTreeNode(T data){element=data; LeftChild=NULL; RightChild=NULL; lTag=0;rTag=0;}

	friend class BinaryTree<T>;
private:

	BinaryTreeNode<T> *LeftChild,*RightChild;

	T element;

	int lTag,rTag;
};

template<typename T>class BinaryTree
{
public:

	BinaryTree(){root=NULL;}

	~BinaryTree();

	void MakeEmpty(){ MakeEmpty(root);}        //清除二叉树

    int Research(T data);                      //寻找结点

	void CreatTree(T data);                    //建立二叉树

	void PrintVTree(){ PrintVTree(root);}      //打印图形二叉树
	
	void PrinTree(){ PrinTree(root,0);}        //用凹凸法打印图型二叉树
	
	void PreOrder(){ PreOrder(root);}          //非递归前序遍历

	void InOrder(){InOrder(root);}              //非递归中序遍历

	void PostOrder(){PostOrder(root);}          //非递归后序遍历

	void COrder(){ COrder(root);}               //层次遍历

	void Countleaf(int &c){ Countleaf(root,c);} //计算叶结点个数

	int  Depth_queue(){ return Depth_queue(root);} //用队列求二叉树深度

	int  Depth_stack(){ return Depth_stack(root);} //用栈求二叉树深度

	void PackOrder(){PackOrder(root);}         //用括号遍历二叉树

	void creatpackettree(char *str);           //用括号建立二叉树

	void m_creatbrinarytree(T *str,int n);   //建立满二叉树
    
	BinaryTreeNode<T>* pre_and_in_creatbinary(char *ppos,char * ipos,int n);//用中序周游跟前序周游建立二叉树

	void InThread(){ InThread(root);}                //中序线索二叉树

	void In_thread_Order(){ In_thread_Order(root);}  //中序线索周游二叉树

	void FindNextinInorderTree(T data){                   //中序线索中找指定结点在前序下的后续
		
        BinaryTreeNode<T> *p;

		p=FindNextinInorderTree(root,data);

		if(p==NULL)
		
			cout<<"\n该结点在前序下没有后续!"<<endl<<endl; 
		
		else{
			cout<<endl;
		
			cout<<"在中序线索二叉树中找指定结点在前序下的后缀:"<<p->element<<endl<<endl;
		}
	}
	
	void FindBeforeinInorderTree(T data){                   //中序线索中找指定结点在后序下的前驱
		
        BinaryTreeNode<T> *p;

		p=FindBeforeinInorderTree(root,data);

		if(p==NULL)

			cout<<"\n该结点在后序下没有前驱!"<<endl<<endl; 
			
		else{
			cout<<endl;
		
			cout<<"在中序线索中找指定结点在后序下的前驱:"<<p->element<<endl<<endl;
		}
	}
	void Post_Thread_Order(){ Post_Thread_Order(root);}  //后序周游中序线索二叉树

	void Del_BinaryTreeNode(T data){ Del_BinaryTreeNode(root,data);}//排序二叉树删除结点

	void Del_BinaryTreeNode_EX(T data){ Del_BinaryTreeNode_EX(root,data);}//改进的二叉树删除结点

	void InsertNode_in_Inthread(T find_data,T insert_data){ InsertNode_in_Inthread(root,find_data,insert_data);}//在中序线索二叉树插入结点

	void Ancestor(T data){ Ancestor(root,data);}//打印指定结点的祖先

	void Closed_Ancestor(T data1,T data2){ Closed_Ancestor(root,data1,data2);}//打印指定两个结点的最近祖先

	void PreOrder_Ex(){ PreOrder_Ex(root);}//改进的非递归前序遍历，这个遍历少了一个子循环，高效很多

private:

   BinaryTreeNode<T> *root,*p;

   void MakeEmpty(BinaryTreeNode<T> *t);
   
   void PrintVTree(BinaryTreeNode<T> *t);

   void PrinTree(BinaryTreeNode<T> *b,int level);
   
   void PreOrder(BinaryTreeNode<T> *t);

   void InOrder(BinaryTreeNode<T> *t);

   void PostOrder(BinaryTreeNode<T> *t);

   void COrder(BinaryTreeNode<T> *t);

   void Countleaf(BinaryTreeNode<T> *t,int &c);

   int Depth_queue(BinaryTreeNode<T> *t);

   int Depth_stack(BinaryTreeNode<T> *t);

   void PackOrder(BinaryTreeNode<T> *t);

   void InThread(BinaryTreeNode<T> *t);

   void In_thread_Order(BinaryTreeNode<T> *t);

   BinaryTreeNode<T> *FindNextinInorderTree(BinaryTreeNode<T> *t,T data);

   BinaryTreeNode<T> *FindBeforeinInorderTree(BinaryTreeNode<T> *t,T data);

   void Post_Thread_Order(BinaryTreeNode<T> *t);

   BinaryTreeNode<T>* Is_PostOrder_first_Node(BinaryTreeNode<T> *t);//判断是否后序周游中序线索二叉树的第一个结点

   void Del_BinaryTreeNode(BinaryTreeNode<T> *t,T data);

   void Del_BinaryTreeNode_EX(BinaryTreeNode<T> *t,T data);

   void InsertNode_in_Inthread(BinaryTreeNode<T> *t,T find_data, T insert_data);

   void Ancestor(BinaryTreeNode<T> *t,T data);

   void Closed_Ancestor(BinaryTreeNode<T> *t,T data1,T data2);

   void PreOrder_Ex(BinaryTreeNode<T> *t);

};

template<typename T>BinaryTree<T>::~BinaryTree()
{
	MakeEmpty(root);
}

template<typename T>void BinaryTree<T>::MakeEmpty(BinaryTreeNode<T> *t)
{
	if(t!=NULL)
	{
		if(t->lTag==0)

		MakeEmpty(t->LeftChild);

		if(t->rTag==0)

		MakeEmpty(t->RightChild);

		delete t;
	}
}

template<typename T>int BinaryTree<T>::Research(T data)
{
	BinaryTreeNode<T> *ptr=root;

	p=NULL;

	while(ptr)
	{
		if(ptr->element==data) {p=ptr; return 1;}
		
		if(ptr->element>data)
		{
			p=ptr;

			ptr=ptr->LeftChild;
		}

		else{
			p=ptr;

			ptr=ptr->RightChild;
		}
	}

	return 0;
}
template<typename T> void BinaryTree<T>::CreatTree(T data)
{
	BinaryTreeNode<T> *current;
	
	if(Research(data)==0)
	{
       
	 current=new BinaryTreeNode<T>(data);

	 if(p==NULL) root=current;

	 else if(p->element>data)
	 
		 p->LeftChild=current;

	 else p->RightChild=current;
	}
}

template<typename T>void BinaryTree<T>::PrintVTree(BinaryTreeNode<T> *t){
	
	int screenWidth=64;
	
	int dataWidth=2;
	
	queue<BinaryTreeNode<T> *> Q;
	
	queue<Level> QI;
	
	BinaryTreeNode<T> *p;
	
	Level s,s1,s2;
	
	double offset,level=-1,i;
	
	Q.EnQue(t);
	
	s.xIndent=screenWidth/dataWidth;
	
	s.yLevel=0;
	
	QI.EnQue(s);
	
	while(!Q.IsEmpty()&&!QI.IsEmpty())
	{
		s2=s;
		
		p=Q.DeQue();
		
		s=QI.DeQue();
		
		if(s.yLevel!=level){
		
			cout<<"\n\n第"<<s.yLevel<<"层";
			
			level=s.yLevel;
			
			for(i=0;i<s.xIndent-1;i++) cout<<" ";
		}
		else	
			for(i=0;i<s.xIndent-s2.xIndent;i++) cout<<" ";
		
		cout<<p->element;
		
		if(p->LeftChild!=NULL)
		{
			Q.EnQue(p->LeftChild);
			
			s1.yLevel=s.yLevel+1;
			
			offset=screenWidth/pow(dataWidth,s1.yLevel+1);
			
			s1.xIndent=s.xIndent-offset;
			
			QI.EnQue(s1);
		}
		 if(p->RightChild!=NULL)
		 { 
		 
			Q.EnQue(p->RightChild);
			
			s1.yLevel=s.yLevel+1;
			
			offset=screenWidth/pow(dataWidth,s1.yLevel+1);
			
			s1.xIndent=s.xIndent+offset;
			
			QI.EnQue(s1);
		}
	}
}

template<typename T>void BinaryTree<T>::PrinTree(BinaryTreeNode<T> *b,int level){
	if(b!=NULL)
	{
		PrinTree(b->RightChild,level+1);
		if(level!=0){
			for(int i=0;i<6*(level-1);i++)cout<<" ";
			cout<<"-----";
		}
		cout<<b->element<<endl;
		PrinTree(b->LeftChild,level+1);
	}
}


template<typename T>void BinaryTree<T>::PreOrder(BinaryTreeNode<T> *t)
{
	stack<BinaryTreeNode<T>*> s;

	BinaryTreeNode<T> *p=t;

	while(!s.IsEmpty()||p!=NULL)
	{
        while(p)
		{
			s.Push(p);
			
			cout<<p->element<<'\t';
			
			p=p->LeftChild;
		}
	p=s.Pop();

	p=p->RightChild;
	}
}

template<typename T>void BinaryTree<T>::InOrder(BinaryTreeNode<T> *t)
{
   stack<BinaryTreeNode<T>*> s;

	BinaryTreeNode<T> *p=t;

	while(!s.IsEmpty()||p!=NULL)
	{
        while(p)
		{
			s.Push(p);
			
			p=p->LeftChild;
		}
	p=s.Pop();

	cout<<p->element<<'\t';

	p=p->RightChild;
	}
}

template<typename T>void BinaryTree<T>::PostOrder(BinaryTreeNode<T> *t)
{
    stack<BinaryTreeNode<T>*> s;

	BinaryTreeNode<T> *p=t;

	int tag[255],top=-1;
	
	while(!s.IsEmpty()||p!=NULL)
	{
        while(p)
		{
			s.Push(p);
			
			tag[++top]=0;
			
			p=p->LeftChild;
		}
	if(top>-1)

		if(tag[top]==1)
        
		{
			cout<<s.GetTop()->element<<'\t';

			s.Pop();

			top--;
		}
		else{

			p=s.GetTop();

			tag[top]=1;

			p=p->RightChild;
		}
	}
}

template<typename T>void BinaryTree<T>::COrder(BinaryTreeNode<T> *t)
{

	BinaryTreeNode<T> *p;

	p=t;

	queue<BinaryTreeNode<T> *> Q;

	Q.EnQue(p);

	while(!Q.IsEmpty())
	{
		p=Q.DeQue();

		cout<<p->element<<"\t";

		if(p->LeftChild!=NULL)

			Q.EnQue(p->LeftChild);

		if(p->RightChild!=NULL)

			Q.EnQue(p->RightChild);
	}

}
template<typename T>void BinaryTree<T>::Countleaf(BinaryTreeNode<T> *t,int &c)
{
	 
 stack<BinaryTreeNode<T>*> s;

	BinaryTreeNode<T> *p=t;

	int tag[255],top=-1;
	
	while(!s.IsEmpty()||p!=NULL)
	{
        while(p)
		{
			s.Push(p);
			
			tag[++top]=0;
			
			p=p->LeftChild;
		}
	if(top>-1)

		if(tag[top]==1)
        
		{
			if(s.GetTop()->LeftChild==NULL && s.GetTop()->RightChild==NULL)

				c++;

			s.Pop();

			top--;
		}
		else{

			p=s.GetTop();

			tag[top]=1;

			p=p->RightChild;
		}
	}
}

template<typename T>int  BinaryTree<T>::Depth_queue(BinaryTreeNode<T> *t)
{
	queue<BinaryTreeNode<T> *> Q;

	queue<Level> QI;

	int depth;
	
	Level y,y1;

	BinaryTreeNode<T> *p=t;

	y.yLevel=1;

	Q.EnQue(p);

	QI.EnQue(y);

	while(!Q.IsEmpty())
	{
		p=Q.DeQue();

		y=QI.DeQue();

		if(p->LeftChild!=NULL)
		{
			Q.EnQue(p->LeftChild);

			y1.yLevel=y.yLevel+1;

		    QI.EnQue(y1);
		}

		if(p->RightChild!=NULL)
		{
			Q.EnQue(p->RightChild);

			y1.yLevel=y.yLevel+1;

		    QI.EnQue(y1);
		}
	}
	
	depth=y.yLevel;
	
	return depth;
}

template<typename T>int  BinaryTree<T>::Depth_stack(BinaryTreeNode<T> *t)
{
    stack<BinaryTreeNode<T>*> S;
	
	BinaryTreeNode<T> *p;
	
	int tag[100],top=-1;
	
	p=t;

    stack<Level> s,s1;   //s1是用来记录当前有左右孩子的结点的高读

	Level y,y1,temp;

	temp.yLevel=0;
	
	y.yLevel;

	while(p!=NULL||!S.IsEmpty()){
		
		while(p!=NULL){
			
			S.Push(p);
			
			y.yLevel=0;

			s.Push(y);
			
			tag[++top]=0;
			
			p=p->LeftChild;
		}
		if(top>-1)
			
			if(tag[top]==1)
			{
				
			
				y=s.Pop();


				if(S.GetTop()->LeftChild!=NULL&&S.GetTop()->RightChild!=NULL)
				{
					temp=s1.Pop();
					
					if(temp.yLevel>y.yLevel)
					
						s.Push(temp);
				
				    else{

				    y1.yLevel=y.yLevel+1;
					
					s.Push(y1);
				
				}	
				
				}
				else{

				    y1.yLevel=y.yLevel+1;
					
					s.Push(y1);
				
				}	

			
				
				S.Pop();
				
				top--;
			}
			else {
				
					p=S.GetTop();

					if(p->LeftChild!=NULL&&p->RightChild!=NULL)//当这个结点是它左孩子的后续并且这个结点有右孩子
					{
					   y=s.Pop();

					   y1.yLevel=y.yLevel+1;

					   s1.Push(y1);

					   temp=y1;

					   
					}
					
					tag[top]=1;
					
				    p=p->RightChild;
					
					
				}
			}
    
	y=s.Pop();

	return y.yLevel;
}


template<typename T>void BinaryTree<T>::creatpackettree(char *str)
{
	BinaryTreeNode<T> *p;

	stack<BinaryTreeNode<T> *> s;
      
	int k,i=0;
      
    char ch=str[i];

	while(ch!='\0')
	{
		switch(ch)
		{
		case '(': s.Push(p); k=1; break;

		case ')': s.Pop(); break;

		case ',': k=2; break;

		default:

			p=new BinaryTreeNode<T>(ch);

			if(root==NULL)

			root=p;

			else{

			    switch(k)
				{
				case 1: s.GetTop()->LeftChild=p; break;

				case 2: s.GetTop()->RightChild=p; break;
				}
			}
		}
		i++;

		ch=str[i];
	}
}

template<typename T>void BinaryTree<T>::PackOrder(BinaryTreeNode<T> *t)
{
  if(t!=NULL)
  {
	  cout<<t->element;

	  if(t->LeftChild!=NULL||t->RightChild!=NULL)
	  {
		  cout<<"(";

		  PackOrder(t->LeftChild);

		  if(t->RightChild!=NULL)

			  cout<<",";

		  PackOrder(t->RightChild);

		  cout<<")";
	  }
  }
}

template<typename T>void BinaryTree<T>::m_creatbrinarytree(T *str,int n)//根据满二叉树的性质，2i为左孩子，2i+1为右孩子
{ 
   queue<BinaryTreeNode<T>*> q;

   BinaryTreeNode<T> *p,*p1;

   int i=1;

   p=new BinaryTreeNode<T>(str[i-1]);

   root=p;

   q.EnQue(root);

   while(i<n)
   {
      p1=q.DeQue();
	  
	  if(2*i-1<n)
	  {
		  p=new BinaryTreeNode<T>(str[2*i-1]);

		  p1->LeftChild=p;

		  q.EnQue(p1->LeftChild);
	  }
	  if(2*i<n)
	  {
           p=new BinaryTreeNode<T>(str[2*i]);

		  p1->RightChild=p;

		  q.EnQue(p1->RightChild);
	  }
      	  
	  i++;
   }
}

template<typename T>BinaryTreeNode<T> * BinaryTree<T>::pre_and_in_creatbinary(char *ppos,char *ipos,int n)
{
	char *rpos;

	int k;

	BinaryTreeNode<T> *p;

	if(n<=0)

		return NULL;

         p=new BinaryTreeNode<T>(*ppos);

		 for(rpos=ipos;rpos<ipos+n;rpos++)