tbstreem.txt

C++描述的数据结构内容,在C++builder的环境中运行,这是第二部分

//线索二叉树结点类型存储结构体TBSTree.h
template<class T> class TBSTree;
template<class T> class ITBSTree;
template<class T> struct THNode
{public:
  int lflag,rflag;//标志域
  THNode<T> *left;//第一个孩子结点指针域
  THNode<T> *right;//下一个兄弟结点指针域
  T data;//数据域
  friend class TBSTree<T>;//线索二叉树类为友元
  friend class ITBSTree<T>;
//构造函数
  THNode():left(NULL),right(NULL),lflag(0),rflag(0){ }
  THNode(int la,int ra,T value,THNode<T> *fc=NULL,
   THNode<T> *ns=NULL):data(value),left(fc),
    right(ns){lflag=la;rflag=ra;}
//访问指针域的成员函数
  THNode<T>* &FirstChild()
   {return left;}
  THNode<T>* &NextSibling()
   {return right;}
};
//线索二叉树类
template<class T> class TBSTree
{protected:
  THNode<T> *root;//根结点指针
  THNode<T> *curr;//当前结点指针
  int nextC;
  int priorC;
 public:
  //构造函数与析构函数
  TBSTree(){root=curr=NULL;}
  TBSTree(THNode<T> *&tree)
  {root=tree;
   curr=root;
   if(tree==NULL)
    {nextC=1;priorC=1;}
   else {nextC=0;priorC=0;}
  }
  //纯虚函数
  virtual THNode<T> *First()=0;
  virtual void Next()=0;
  virtual void Last()=0;
  virtual void Prior()=0;
  int EndOfNext()
   {return nextC;}
  int EndOfPrior()
   {return priorC;}
  //数据检索与修改成员函数
  T &Data();
};
//线索二叉树类的实现
template<class T>
T &TBSTree<T>::Data()
{if(root==NULL)
 {cout<<"二叉树空!\n";exit(1);}
 return curr->data;
}
//由结点构造线索二叉树的类外一般函数
template<class T>
THNode<T> *GetTreeNode(T item,THNode<T> *le=NULL,
   THNode<T> *ri=NULL,int lf=0,int rf=0)
{THNode<T> *p=new THNode<T>;
 p->data=item;p->left=le;p->right=ri;
 p->lflag=lf;p->rflag=rf;
 if(p==NULL)
  {cerr<<"内存分配失败!\n";exit(1);}
 return p;
}
//创建特定线索二叉树的类外一般函数
template<class T>
THNode<T> *MakeCharT(THNode<T> *&root,int num)
{THNode<T> *b,*c,*d,*e,*f,*g,*null=NULL;
 if(num==1)
  root=GetTreeNode('X',null);
 if(num==2)
 {e=GetTreeNode('R');
  f=GetTreeNode('W');
  d=GetTreeNode('P',e,f);
  g=GetTreeNode('Q');
  b=GetTreeNode('N',d,g);
  c=GetTreeNode('O');
  root=GetTreeNode('M',b,c);
 }
 if(num==3)
 {g=GetTreeNode('G');
  d=GetTreeNode('D',null,g);
  b=GetTreeNode('B',d);
  e=GetTreeNode('E');
  f=GetTreeNode('F');
  c=GetTreeNode('C',e,f);
  root=GetTreeNode('A',b,c);
 }
 return root;
}
//派生类ITBSTree.h
template<class T>
class ITBSTree:public TBSTree<T>
{private:
  //中序线索化二叉树
  void InThread(THNode<T> *&root,THNode<T> *&pre);
 public:
  //构造函数
  ITBSTree(THNode<T> *&tree):TBSTree<T>(tree) {}
  //中序线索化二叉树
  void CreatInThread();
  //定位到中序下的第一个结点
  virtual THNode<T> *First();
  //将当前指针移到中序下的后继结点
  virtual void Next();
  //定位到中序下的最后一个结点
  virtual void Last();
  //将当前指针移到中序下的前驱结点
  virtual void Prior();
  //插入结点
  void InsertR(THNode<T> *&s,THNode<T> *&r);
};
template<class T>
void ITBSTree<T>::InThread(THNode<T> *&root,THNode<T> *&pre)
{if(root!=NULL)
 {InThread(root->left,pre);//中序线索化左子树二叉树
  if(root->left==NULL)//当前结点左指针为空指针时
  {root->lflag=1; //建立左线索指针
   root->left=pre;//建立左线索标志
  }
  if(pre->right==NULL)//前驱结点右指针为空指针时
  {pre->rflag=1; //建立右线索标志
   pre->right=root;//建立右线索指针
  }
  pre=root;//前驱结点右指针等于当前结点指针
  InThread(root->right,pre);}//中序线索化右子树二叉树
}
template<class T>
void ITBSTree<T>::CreatInThread()
{THNode<T> *t=root;//保存原根结点指针
 root=new THNode<T>;//建立头结点
 root->lflag=0;
 root->rflag=1;
 if(t==NULL)//当为空树时
  {root->left=root;
   root->right=root;
  }
 else     //当为非空树时
  {curr=root->left=t;//置头结点的左指针
   root->lflag=0;    //置头结点的左标志
   THNode<T> *pre=root;//定义临时指针
   InThread(curr,pre);//中序线索化二叉树
   pre->right=root;//置最后一个结点的右线索
   pre->rflag=1;   //置最后一个结点的右标志
   root->right=pre;//置头结点的右线索
   root->rflag=1;//置头结点的右标志
  }
}
template<class T>
THNode<T> *ITBSTree<T>::First()
{curr=root;//从根结点开始
 while(curr->lflag==0)
  curr=curr->left;
 if(curr==root) nextC=1;//当二叉树为空时
 else nextC=0;//当二叉树为非空时
 return curr;
}
template<class T>
void ITBSTree<T>::Next()
{if(nextC==1)
  {cerr<<"已到二叉树尾!\n";exit(1);}
 THNode<T> *p=curr->right;//将当前指针移到中序下的后继结点
 if(curr->rflag==0)
  while(p->lflag==0) p=p->left;
 curr=p;
 if(curr==root) nextC=1;
}
template<class T>
void ITBSTree<T>::Last()
{curr=root->right;//使curr定位到中序下的最后一个结点
 if(curr==root) priorC=1;
 else priorC=0;
}
template<class T>
void ITBSTree<T>::Prior()
{if(priorC==1)
  {cerr<<"已到二叉树头!\n";exit(1);}
 THNode<T> *p=curr->left;
 if(curr->lflag==0)
  while(p->rflag==0) p=p->right;
 curr=p;
 if(curr==root) priorC=1;
}
template<class T>
void ITBSTree<T>::InsertR(THNode<T> *&s,THNode<T> *&r)
{//将r当做s的右子女插入
 r->right=s->right;//s的右子女指针或后继线索传给r
 r->rflag=s->rflag;//传送标志
 r->left=s;r->lflag=1;//r的left成为指向s的前驱线索
 s->right=r;s->rflag=0;//r成为s的右子女
 if(r->rflag==0)//s原来有右子女
 {curr=r->right;
  THNode<T> *temp=First();//在s原来的右子树中找中序下第一个结点
  temp->left=r;//建立指向r的前驱线索
 }
}
//线索二叉树类相关操作的测试TBSTreeM.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<conio.h>
#include "TBSTree.h"
#include "ITBSTree.h"

void main()
{cout<<"TBSTreeM.cpp运行结果:\n";
 THNode<char> *q,*p,*r;
 q=MakeCharT(q,3);
 ITBSTree<char> t(q);
 t.CreatInThread();
 cout<<"线索二叉树的中序正向遍历序列为:\n";
 for(t.First();!t.EndOfNext();t.Next())
   cout<<t.Data()<<"  ";
 cout<<"\n线索二叉树的中序反向遍历序列为:\n";
 for(t.Last();!t.EndOfPrior();t.Prior())
   cout<<t.Data()<<"  ";
 p=MakeCharT(p,2);
 ITBSTree<char> d(p);
 d.CreatInThread();
 cout<<"\n线索二叉树的中序正向遍历序列为:\n";
 for(d.First();!d.EndOfNext();d.Next())
   cout<<d.Data()<<"  ";
 cout<<"\n线索二叉树的中序反向遍历序列为:\n";
 for(d.Last();!d.EndOfPrior();d.Prior())
   cout<<d.Data()<<"  ";
 r=MakeCharT(r,1);
 ITBSTree<char> h(r);
 h.CreatInThread();
 cout<<"\n线索二叉树的中序正向遍历序列为:\n";
 for(h.First();!h.EndOfNext();h.Next())
   cout<<h.Data()<<"  ";
 d.InsertR(p,r);
 cout<<"\n插入结点后线索二叉树的中序正向遍历序列为:\n";
 for(d.First();!d.EndOfNext();d.Next())
   cout<<d.Data()<<"  ";
 getch();}
TBSTreeM.cpp运行结果:
线索二叉树的中序正向遍历序列为:
D  G  B  A  E  C  F  
线索二叉树的中序反向遍历序列为:
F  C  E  A  B  G  D  
线索二叉树的中序正向遍历序列为:
R  P  W  N  Q  M  O  
线索二叉树的中序反向遍历序列为:
O  M  Q  N  W  P  R  
线索二叉树的中序正向遍历序列为:
X  
插入结点后线索二叉树的中序正向遍历序列为:
R  P  W  N  Q  M  X  O