threadedbtnode.cpp

中序线索化二叉树 实验<一>:构造二叉树

#include"threadedbtnode.h"
#include"stdlib.h"
//构造函数
template<class T>
ThreadedBTNode<T>::ThreadedBTNode(void)
{
	root=NULL;
};
//析构函数
template<class T>
ThreadedBTNode<T>::~ThreadedBTNode(void){};

template<class T>
bool ThreadedBTNode<T>::IsEmpty(void)const
{
	return ((root)?false:true);
}

template<class T>
bool ThreadedBTNode<T>::Root(T&x)const
{
	if(root)
	{
		x=root->data;
		return true;
	}
	else 
		return false;
}
//创建二叉树
template<class T>
BinaryTreeNode<T> *ThreadedBTNode<T>::MakeTree(const T&element,BinaryTreeNode<T>*left,BinaryTreeNode<T>*right)
{
	root=new BinaryTreeNode<T>(element,left,right);
	if(root==NULL)
	{
		cerr<<"Memory allocation failure!\n:";
		exit(1);
	}
	return root;
}
//对二叉树中序线索化
template<class T>
void ThreadedBTNode<T>::InorderThread(BinaryTreeNode<T>*p,BinaryTreeNode<T>*&pre)
	{
	if(p!=NULL)
	{//左子树线索化
	 InorderThread((BinaryTreeNode<T> *)p->LeftChild,pre);
	 //建立右线索
	 if(pre!=NULL&&pre->rtag==1)
		pre->RightChild=p;
	 //建立左线索
	 if(p->LeftChild==NULL)
	 {
		p->ltag=1;
		p->LeftChild=pre;
	 }
	 //建立左右线索标志
	 else
		p->ltag=0;
        if(p->RightChild==NULL)
			p->rtag=1;
		else
			p->rtag=0;
		pre=p;
     //右子树线索化
      InorderThread((BinaryTreeNode<T> *)p->RightChild,pre);
	}
	
}
//在中序线索二叉树中查找结点p的中序后继
template<class T>
void ThreadedBTNode<T>::Inordernext(BinaryTreeNode<T>*p,BinaryTreeNode<T>*q)
{
  if(p->rtag==1)   //指定结点右子树为空
	  q=(BinaryTreeNode<T>*)p->RightChild;
  else              //指定结点右子树非空
  {
	q=(BinaryTreeNode<T>*)p->RightChild;
	while(q->ltag==0)
		q=(BinaryTreeNode<T>*)q->LeftChild;
  }
  cout<<q->data;
}
//对称序遍历对称序线索化二叉树
template<class T>
void ThreadedBTNode<T>::ThreadInTravel(BinaryTreeNode<T>*p)
{
  if(p!=NULL)
  {
	//找对称序第一个结点
	while(p->ltag==0)
		p=(BinaryTreeNode<T>*)p->LeftChild;
	do
	{  //访问*p所指结点
	  cout<<p->data<<" ";
	  if(p->rtag==1)
		  p=(BinaryTreeNode<T>*)p->RightChild;
	  else
	  {
		  p=(BinaryTreeNode<T>*)p->RightChild;
		  while(p->ltag==0)
			  p=(BinaryTreeNode<T>*)p->LeftChild;
	  }
	}while(p!=NULL);
  }
}