threadtree.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

//////////////////线索二叉树//////////////////
#include"queue.h"
#include"stack.h"
#include<iostream.h> 
template<class Type>class	ThreadTree; 
template<class Type> //定义二叉树的结点类
class	ThreadTreeNode 
{ 
  public: 
	friend class ThreadTree<Type>; 
	ThreadTreeNode():lchild(NULL),rchild(NULL){} //构造
	ThreadTreeNode(Type its_data);
	Type data; 
	int ltag;
	int rtag;
	ThreadTreeNode *lchild;  //左，右子树 
	ThreadTreeNode *rchild; 
}; 
template<class Type>
ThreadTreeNode<Type>::ThreadTreeNode(Type its_data)
{
	data=its_data;
	lchild=rchild=NULL;
}

template<class Type> //定义二叉树类
class ThreadTree 
{  
public: 
	ThreadTree():root(NULL){} 
	void CreatTree();               //创建二叉树,主过程 
	void CreatTree(ThreadTreeNode<Type>* child,int k); //子过程 
	//void CreatTree(ThreadTreeNode<Type>	*a,int n);//以数组的中元素建立二叉树
	void PreOrder(ThreadTreeNode<Type> *point) ;
	void Destroy(ThreadTreeNode<Type> *point);     //销毁二叉树 
	bool IsEmpty(); 	
	////中序线索二叉树的一些操作////
	void InThreadTree();							//中序线索化二叉树
	void InThreadTree(ThreadTreeNode<Type> *point,ThreadTreeNode<Type> *&pre);		//中序线索二叉树
	ThreadTreeNode<Type> *InLast(ThreadTreeNode<Type> *point);	//查找中根次序下的前驱节点
	ThreadTreeNode<Type> *InNext(ThreadTreeNode<Type> *point);	//查找中根次序下的后继节点
	ThreadTreeNode<Type> *InFirst(ThreadTreeNode<Type> *point);	//返回以point为根在线索脂中的中序序列下的第一个结点
	ThreadTreeNode<Type> *PreNext(ThreadTreeNode<Type> *point);	//返回先根次序下的后继节点
	ThreadTreeNode<Type> *PostLast(ThreadTreeNode<Type> *point);//返回后根次序下的前驱节点

	
	//先序线索二叉树的一些操作
	void PreThreadTree();
	void PreThreadTree(ThreadTreeNode<Type> *point,ThreadTreeNode<Type> *&pre);
	
	//后序线索二叉树的一些操作
	void PostThreadTree();
	void PostThreadTree(ThreadTreeNode<Type> *point,ThreadTreeNode<Type> *&pre);

	ThreadTreeNode<Type> *GetRoot(){return root;}
	void InOrder();												//中根次序遍历中序二叉树
	void PreOrder();											//先根次序遍历中序二叉树
	void PostOrder();											//后根次序遍历中序二叉树
private: 
	ThreadTreeNode<Type>* root; 
};
template<class Type> 
void ThreadTree<Type>::CreatTree() 
{ 
	CreatTree(root,1); 
} 

template<class Type> 
void ThreadTree<Type>::CreatTree(ThreadTreeNode<Type>* child,int k) 
{ 
	ThreadTreeNode<Type>* point; 
	point=new ThreadTreeNode<Type>; 
	cout<<"输入节点数据项 :"; 
	cin>>point->data; 
	switch(k) 
	{ 
		case 1: 
			root=point; 
			break; 
		case 2: 
			child->lchild=point;
			child->ltag=0;
			break; 
		case 3: 
			child->rchild=point;
			child->rtag=0;
			break; 
	} 
	char temp; 
	cout<<"该"<<point->data<<"节点是否有左子树 Y / 任意键 :"; 
	cin>>temp; 
	if(temp=='y'||temp=='Y') 
		CreatTree(point,2); 
	else
	{
		//point->ltag=1;
		point->lchild=NULL;
	}
	cout<<"该"<<point->data<<"节点是否有右子树 Y / 任意键 :"; 
	cin>>temp; 
	if(temp=='y'||temp=='Y') 
		CreatTree(point,3); 
	else
	{
		//point->rtag=1;
		point->rchild=NULL;
	}
} 



template<class Type> 
bool ThreadTree<Type>::IsEmpty() 
{ 
	return root==NULL; 
} 

template<class Type> 
void ThreadTree<Type>::Destroy(ThreadTreeNode<Type> *point) 
{ 
	if(point!=NULL) 
	{ 
		Destroy(point->lchild); 
		Destroy(point->rchild); 
		delete point; 
	} 
} 

///中序线索二叉树的一些算法
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type>
void ThreadTree<Type>::InThreadTree()
{
	ThreadTreeNode<Type> *pre=new ThreadTreeNode<Type>; 	
	if(root!=NULL)
	{
		InThreadTree(root,pre);
		pre->rchild=NULL;
		pre->rtag=1;
		/*root->rchild=NULL;
		root->rtag=1;*/
	}
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

template<class Type>
void ThreadTree<Type>::InThreadTree (ThreadTreeNode<Type> *point, ThreadTreeNode<Type> *&pre)//有问题
{
	if(point!=NULL)
	{
		InThreadTree(point->lchild,pre);
		if(point->lchild == NULL)
		{
			point->ltag=1;
			point->lchild=pre;				
		}
		if(pre!=NULL&&pre->rchild==NULL)
		{
			pre->rchild=point;
			pre->rtag=1;
		}	
		pre=point;
		InThreadTree(point->rchild,pre);
	}
}


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template<class Type>
ThreadTreeNode<Type> *ThreadTree<Type>::InLast(ThreadTreeNode<Type> *point)
{
	if(point->ltag==1)
		point=point->lchild;
	else
	{
		point=point->lchild;
		while(point->rtag==0)
			point=point->rchild;
	}
	return point;
}

template <class Type>
ThreadTreeNode<Type> *ThreadTree<Type>::InFirst(ThreadTreeNode<Type> *point)
{
	ThreadTreeNode<Type> *p=point;
	while(p->ltag==0)
		p=p->lchild;
	return p;
}

template<class Type>
ThreadTreeNode<Type> *ThreadTree<Type>::InNext(ThreadTreeNode<Type> *point)
{
	ThreadTreeNode<Type> *p=point->rchild;
	if(point->rtag==0)
		return InFirst(p);//表示有后继点
	else
		return p;		//直接返回其后继
} 

template<class Type>
void ThreadTree<Type>::InOrder()
{
	cout<<"the inorder is:"<<endl;
	ThreadTreeNode<Type> *p;
	p=InFirst(root);
	for(;p!=NULL;p=InNext(p))
		cout<<p->data<<setw(3);
	cout<<endl;
}

template<class Type>
ThreadTreeNode<Type> *ThreadTree<Type>::PreNext(ThreadTreeNode<Type> *p)//返回先根次序下的后继结点
{
	if(p->ltag==0)
		p=p->lchild;
	else
	{
		if(p->rtag==0)
			p=p->rchild;
		else
		{
			while(p->rtag==1&&p->rchild!=NULL)//
				p=p->rchild; 
			p=p->rchild;
		}
	}
	return p;
}

template<class Type>
void ThreadTree<Type>::PreOrder()
{
	ThreadTreeNode<Type> *p=root;
	if(p!=NULL)
	{
		cout<<"preorder is:"<<endl;
		do
		{
			cout<<p->data<<setw(3);
			p=PreNext(p);
		}while(p!=NULL);
	cout<<endl;
	}
}
	
template<class Type>
ThreadTreeNode<Type> *ThreadTree<Type>::PostLast(ThreadTreeNode<Type> *p)//返回后根次序下前驱结点
{
	if(p->rtag==0)
		p=p->rchild;
	else
	{
		while(p->ltag==1&&p->lchild!=NULL)
			p=p->lchild;
		p=p->lchild;
	}
	return p;
}

template<class Type>
void ThreadTree<Type>::PostOrder()
{
	Stack<ThreadTreeNode<Type> *> stk;
	ThreadTreeNode<Type> *p=root;
	cout<<"post inder:"<<endl;
	while(p!=NULL)
	{	
		stk.Push(p);
		p=PostLast(p);
	}
	while(!stk.IsEmpty())
	{
		p=stk.Pop();
		cout<<p->data<<setw(3);
	}	
	cout<<endl;
}

template <class Type>
void ThreadTree<Type>::PreThreadTree(ThreadTreeNode<Type> *point,ThreadTreeNode<Type> *&pre)
{
	if(point!=NULL)
	{
		if(point->lchild == NULL)
		{
			point->ltag=1;
			point->lchild=pre;				
		}
		if(pre!=NULL&&pre->rchild==NULL)
		{
			pre->rchild=point;
			pre->rtag=1;
		}	
		InThreadTree(point->lchild,pre);
		pre=point;
		InThreadTree(point->rchild,pre);
	}
}

template <class Type>
void ThreadTree<Type>::PreThreadTree()
{
	ThreadTreeNode<Type> *pre=new ThreadTreeNode<Type>; 	
	if(root!=NULL)
	{
		InThreadTree(root,pre);
		pre->rchild=NULL;
		pre->rtag=1;
		/*root->rchild=NULL;
		root->rtag=1;*/
	}
}

template <class Type>
void ThreadTree<Type>::PostThreadTree(ThreadTreeNode<Type> *point,ThreadTreeNode<Type> *&pre)
{
	if(point!=NULL)
	{
		
		InThreadTree(point->lchild,pre);
		pre=point;
		InThreadTree(point->rchild,pre);
		if(point->lchild == NULL)
		{
			point->ltag=1;
			point->lchild=pre;				
		}
		if(pre!=NULL&&pre->rchild==NULL)
		{
			pre->rchild=point;
			pre->rtag=1;
		}	
	}
}

template <class Type>
void ThreadTree<Type>::PostThreadTree()
{
	ThreadTreeNode<Type> *pre=new ThreadTreeNode<Type>; 	
	if(root!=NULL)
	{
		InThreadTree(root,pre);
		pre->rchild=NULL;
		pre->rtag=1;
		/*root->rchild=NULL;
		root->rtag=1;*/
	}	
}