线索二叉树实现

/*****************未完全测试，有问题请留言********************************/

/////////////////////////////////////////////////////////////
//线索二叉树结点结构
/////////////////////////////////////////////////////////////
template
struct TBSTNode
{
TBSTNode *left,*right;
T element;
int lTag;
int rTag;
TBSTNode(T e=T())
{
 left=0;
 right=0;
 element=e;
 lTag=0;
 rTag=0;
}
TBSTNode(TBSTNode* x,TBSTNode* y,int a,int b,T e)
{
left=x;
right=y;
element=e;
lTag=a;
rTag=b;
}
};

 

/////////////////////////////////////////////////////////////
//线索二叉树结点类
/////////////////////////////////////////////////////////////
template
class TBST
{
public:
 TBST()
 {
  root=new TBSTNode(T());
  type=0;
 }
    TBST(BST& tree)
 {
  BSTNode* temp=tree.getroot();
  root=copyBST(temp);
  type=0;

 }
 TBST(TBST& node)
 {
  TBSTNode* temp=node.getroot();
  root=copyBST(temp);
 }
 void Visit(TBSTNode* p)
 {
  cout<element< }
 TBST& operator=(TBST& node)
 {
  delete root;
  TBSTNode* temp=node.getroot();
        root=copyBST(temp);
  return *this;
 }

 TBSTNode* previous(TBSTNode* p);
 TBSTNode* next(TBSTNode* p);

//******************线索二叉树的拷贝**********************//
 TBSTNode* copyBST(BSTNode* node);
 TBSTNode* copyBST(TBSTNode* node);
//***********************************************************//
 TBSTNode* getroot()；
 void order();
 void gettype();
 void insert(TBSTNode* node);
//******************线索二叉树的打印**********************//
 void printData(T data,int level);
    void printTree(TBSTNode* node,int level);
//********************************************************//

 

//******************线索二叉树的三种线索化算法**********************//
 void MakePreThread();
    void MakeInThread();
 void MakePostThread();
 void MakePreThread(TBSTNode* t,TBSTNode*& pre);
    void MakeInThread(TBSTNode* t,TBSTNode*& pre);
    void MakePostThread(TBSTNode* t,TBSTNode*& pre);
//******************************************************************//
 ~TBST(){delete root;}
 void Output(ostream& out);
private:
 TBSTNode* root;
 int type;
 friend ostream& operator <<(ostream& out,TBSTNode& node);
};

 

/////////////////////////////////////////////////////////////
//返回二叉线索树根结点
/////////////////////////////////////////////////////////////
template
BSTNode* TBST::getroot()
{
 return root;
}

/////////////////////////////////////////////////////////////
//线索二叉树结点p的前驱
/////////////////////////////////////////////////////////////
template
TBSTNode* TBST::previous(TBSTNode* p)
{
        switch(type)
  {
  case 0:
             cout<<"to be continued"<    break;
  case 1:
             if(p->left==1)
     return p->left;
    else
    {
     p=p->left;
     while(p->rTag==0)
      p=p->right;
     return p;
    }

  case 2:
   if(p->lTag==1)
    retrun p->left;
   else if(p->rTag==0)
    return p->right;
   else
    return p->left;
   break;
  default:
  cout<<"the tree has node been create"<  break;

  }

 }

/////////////////////////////////////////////////////////////
//线索二叉树结点p的后继
/////////////////////////////////////////////////////////////
template
TBSTNode* TBST::next(TBSTNode* p)
{
        switch(type)
  {
  case 0:
   if(p->lTag==0)
    return p->left;
   else p->right;
  case 1:
   if(p->rTag==1)
    return p->right;
   else
   {
    p=p->right;
    while(p->lTag==0)
     p=p->left;
    return p;
   }

  case 2:
            cout<<"to be continued"<   break;
  default:
   cout<<"the tree has node been create"<   break;
  }
 }

 

/////////////////////////////////////////////////////////////
//建立中序线索二叉树
/////////////////////////////////////////////////////////////
template
void TBST::MakeInThread(TBSTNode* t,TBSTNode*& pre)
{
if(t!=NULL)
{
MakeInThread(t->left,pre);
{
if(pre!=NULL)
if(pre->right==NULL)
{
pre->rTag=1;
pre->right=t;
}
else
{
 pre->rTag=0;
}

if(t->left==NULL)
{
t->lTag=1;
t->left=pre;
}
else
{
 t->lTag=0;
}
 pre=t;
MakeInThread(t->right,pre);
}
}
}

template
void TBST::MakeInThread()
{
TBSTNode* pre=NULL;
if(root!=NULL)
{
MakeInThread(root,pre);
pre->rTag=1;
}
type=1;
}

/////////////////////////////////////////////////////////////
//建立先序线索二叉树
/////////////////////////////////////////////////////////////
template
void TBST::MakePreThread(TBSTNode* t,TBSTNode*& pre)
{
if(t!=NULL)
{
if(pre!=NULL)
{
if(pre->right==NULL)
{
pre->right=t;
pre->rTag=1;
}
else
{
pre->rTag=0;
}
}
if(t->left==NULL)
{
t->left=pre;
t->lTag=1;
}
else
{
t->lTag=0;
}
pre=t;
if(t->left==0)
MakePreThread(t->left,pre);
MakePreThread(t->right,pre);
}

}

template
void TBST::MakePreThread()
{
TBSTNode* pre=NULL;
if(root!=NULL)
{
MakePreThread(root,pre);
pre->rTag=1;
}
type=0;
}

/////////////////////////////////////////////////////////////
//建立后序线索二叉树
/////////////////////////////////////////////////////////////
template
void TBST::MakePostThread(TBSTNode* t,TBSTNode*& pre)
{

if(t!=NULL)
{
MakePostThread(t->left,pre);
MakePostThread(t->right,pre);
if(pre!=NULL)
if(pre->right==NULL)
{
pre->right=t;
pre->rTag=1;
}
else
{
pre->rTag=0;
}
if(t->left==NULL)
{
t->left=pre;
t->lTag=1;
}
else
{
t->lTag=0;
}
pre=t;
}
}

template
void TBST::MakePostThread()
{
TBSTNode* pre=NULL;
if(root!=NULL)
{
MakePostThread(root,pre);
}
type=2;
}

/////////////////////////////////////////////////////////////
//线索二叉树的拷贝
/////////////////////////////////////////////////////////////
template
TBSTNode* TBST::copyBST(BSTNode* node)
 {
  if(node!=NULL)
  {
         TBSTNode* temp=new TBSTNode(node->element);
   temp->left=copyBST(node->left);
   temp->right=copyBST(node->right);
   return temp;
  }
  return NULL;
 }
 TBSTNode* copyBST(TBSTNode* node)
 {
  if(node!=NULL)
  {
         TBSTNode* temp=new TBSTNode(node->element);
   temp->left=copyBST(node->left);
   temp->right=copyBST(node->right);
   temp->lTag=node->lTag;
   temp->rTag=node->rTag;
   return temp;
  }
  return NULL;
 }

 

/////////////////////////////////////////////////////////////
//打印线索二叉树结点
/////////////////////////////////////////////////////////////
template
void TBST::printData(T data,int level ){
for( int i = 0; i < level; i++ ){
printf( "   ");
}
cout<}

 

/////////////////////////////////////////////////////////////
//打印线索二叉树结构
/////////////////////////////////////////////////////////////
template
void TBST::printTree(TBSTNode* node,int level){
if( node == NULL ) return;
if(node->rTag!=1){
printTree( node->right, level + 1 );
}
printData( node->element, level );
if(node->lTag!=1){
printTree( node->left, level + 1 );
}
}

/////////////////////////////////////////////////////////////
//输出线索二叉树
/////////////////////////////////////////////////////////////
template
void TBST::Output(ostream& out)
{
out<<"the TBST tree is as follows:"<printTree(root,0);
}

/////////////////////////////////////////////////////////////
//重载线索二叉树<<
/////////////////////////////////////////////////////////////
template
ostream& operator << (ostream& out,TBST& node)
{
node.Output(out);
return out;
}