tbstree2m.txt

来自「C++描述的数据结构内容,在C++builder的环境中运行,这是第二部分」· 文本 代码 · 共 209 行

//线索二叉树结点类型存储结构体TBSTree2.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 void First()=0;
  virtual void Last()=0;
  //数据检索与修改成员函数
  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)
 {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);
 }
 else {
  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; 
}
//派生类ITBSTree2.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 void First();
  //线索二叉树的中序反向遍历
  virtual void Last();
};
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>
void ITBSTree<T>::First()
{THNode<T> *p;
 curr=root;//从根结点开始
 while(curr->lflag==0)
  curr=curr->left;
 if(curr==root) nextC=1;//当二叉树为空时
 else nextC=0;//当二叉树为非空时
 while(nextC==0)
 {cout<<curr->data<<"  ";
  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()
{THNode<T> *p;
 curr=root->right;//使curr定位到中序下的最后一个结点
 if(curr==root) priorC=1;
 else priorC=0;
 while(priorC==0)
 {cout<<curr->data<<"  ";
  p=curr->left;
  if(curr->lflag==0)
  while(p->rflag==0)
   p=p->right;
  curr=p;
  if(curr==root) priorC=1;
 }
}
//线索二叉树类相关操作的测试TBSTree2M.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<conio.h>
#include "TBSTree2.h"
#include "ITBSTree2.h"
void main()
{cout<<"TBSTree2M.cpp运行结果:\n";
 THNode<char> *q,*p;
 q=MakeCharT(q,2);
 ITBSTree<char> t(q);
 t.CreatInThread();
 cout<<"二叉树的中序正向遍历序列为:\n";
 t.First();
 cout<<"\n二叉树的中序反向遍历序列为:\n";
 t.Last();
 p=MakeCharT(p,1);
 ITBSTree<char> d(p);
 d.CreatInThread();
 cout<<"\n二叉树的中序正向遍历序列为:\n";
 d.First();
 cout<<"\n二叉树的中序反向遍历序列为:\n";
 d.Last();
 getch();}
TBSTree2M.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