线索二叉树实现

作者：来源：zz 发表时间：2008-06-12 浏览次数：字号：大 中 小

/////////////////////////////////////////////////////////////
//线索二叉树结点结构
/////////////////////////////////////////////////////////////
template <class T>
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 T>
class TBST
{
public:
TBST()
{
  root=new TBSTNode<T>(T());
  type=0;
}
    TBST(BST<T>& tree)
{
  BSTNode<T>* temp=tree.getroot();
  root=copyBST(temp);
  type=0;

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

TBSTNode<T>* previous(TBSTNode<T>* p);
TBSTNode<T>* next(TBSTNode<T>* p);

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

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

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

/////////////////////////////////////////////////////////////
//线索二叉树结点p的前驱
/////////////////////////////////////////////////////////////
template <class T>
TBSTNode<T>* TBST<T>::previous(TBSTNode<T>* p)
{
        switch(type)
  {
  case 0:
             cout<<"to be continued"<<endl;
    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"<<endl;
  break;

}

/////////////////////////////////////////////////////////////
//线索二叉树结点p的后继
/////////////////////////////////////////////////////////////
template <class T>
TBSTNode<T>* TBST<T>::next(TBSTNode<T>* 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"<<endl;
   break;
  default:
   cout<<"the tree has node been create"<<endl;
   break;
  }
}

/////////////////////////////////////////////////////////////
//建立中序线索二叉树
/////////////////////////////////////////////////////////////
template <class T>
void TBST<T>::MakeInThread(TBSTNode<T>* t,TBSTNode<T>*& 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 <class T>
void TBST<T>::MakeInThread()
{
TBSTNode<T>* pre=NULL;
if(root!=NULL)
{
MakeInThread(root,pre);
pre->rTag=1;
}
type=1;
}

/////////////////////////////////////////////////////////////
//建立先序线索二叉树
/////////////////////////////////////////////////////////////
template <class T>
void TBST<T>::MakePreThread(TBSTNode<T>* t,TBSTNode<T>*& 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 <class T>
void TBST<T>::MakePreThread()
{
TBSTNode<T>* pre=NULL;
if(root!=NULL)
{
MakePreThread(root,pre);
pre->rTag=1;
}
type=0;
}

/////////////////////////////////////////////////////////////
//建立后序线索二叉树
/////////////////////////////////////////////////////////////
template <class T>
void TBST<T>::MakePostThread(TBSTNode<T>* t,TBSTNode<T>*& 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 <class T>
void TBST<T>::MakePostThread()
{
TBSTNode<T>* pre=NULL;
if(root!=NULL)
{
MakePostThread(root,pre);
}
type=2;
}

/////////////////////////////////////////////////////////////
//线索二叉树的拷贝
/////////////////////////////////////////////////////////////
template <class T>
TBSTNode<T>* TBST<T>::copyBST(BSTNode<T>* node)
{
  if(node!=NULL)
  {
         TBSTNode<T>* temp=new TBSTNode<T>(node->element);
   temp->left=copyBST(node->left);
   temp->right=copyBST(node->right);
   return temp;
  }
  return NULL;
}
TBSTNode<T>* copyBST(TBSTNode<T>* node)
{
  if(node!=NULL)
  {
         TBSTNode<T>* temp=new TBSTNode<T>(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 <class T>
void TBST<T>::printData(T data,int level ){
for( int i = 0; i < level; i++ ){
printf( " ");
}
cout<<data<<endl;
}

/////////////////////////////////////////////////////////////
//打印线索二叉树结构
/////////////////////////////////////////////////////////////
template <class T>
void TBST<T>::printTree(TBSTNode<T>* 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 <class T>
void TBST<T>::Output(ostream& out)
{
out<<"the TBST tree is as follows:"<<endl;
printTree(root,0);
}

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

责任编辑 webmaster

相关链接

Linux bootsect.S源代码分析

算术编码过程源代码

数据结构词汇汇总

COM客户调用解析及源代码