bstreefm.txt

一本数据结构的经典书籍-数据结构算法程序集里

//二叉搜索树的类定义BSTreeF.h
//定义学生记录类型
//定义二叉搜索树结点值的类型为学生记录类型
typedef struct student
{char num[6];//学号
 int grade; //成绩
}ElemType;
template<class T>class BSTree {
 private:
  BSTree<T> *left;//左子树指针
  BSTree<T> *right;//右子树指针
 public:
  T data;//数据域
  //构造函数
  BSTree():left(NULL),right(NULL) { }
  BSTree(T item,BSTree<T> *left1=NULL,
    BSTree<T> *right1=NULL):data(item),
    left(left1),right(right1){ }
  BSTree<T> *&Left(){return left;}
  BSTree<T> *&Right(){return right;}
//初始化二叉搜索树，即把树根指针置空
  void InitBSTree(BSTree<T> *&BST);
//判断二叉搜索树是否为空
  bool BSTreeEmpty(BSTree<T> *&BST);
//从二叉搜索树中查找元素
  bool Find(BSTree<T> *&BST,T item);
//更新二叉搜索树中的结点值
  bool Update(BSTree<T> *&BST,const T item,T newc);
//向二叉搜索树中插入元素
  void Insert(BSTree<T> *&BST,const T &item);
//从二叉搜索树中删除元素
  bool Delete(BSTree<T> *&BST,T item);
//利用数组建立一棵二叉搜索树
  void CreateBSTree(BSTree<T> *&BST,T a[],int n);
//中序遍历输出二叉搜索树中的所有结点
  void Inorder(BSTree<T> *&BST);
//求二叉搜索树的深度
  int BSTreeDepth(BSTree<T> *&BST);
//求二叉搜索树中所有结点数
  int BSTreeCount(BSTree<T> *&BST);
//求二叉搜索树中所有叶子结点数
  int BSTreeLeafCount(BSTree<T> *&BST);
//按照二叉搜索树的广义表表示输出二叉搜索树
  void PrintBSTree(BSTree<T> *&BT);
//清除二叉搜索树，使之变为一棵空树
  void ClearBSTree(BSTree<T> *&BT);
//把BST二叉搜索树按照先根遍历的次序存储到文件fname中
  void WriteFile(char* fname, BSTree *BST);
//把fname文件中按先根遍历存储的二叉搜索树恢复到内存中
  void ReadFile(char* fname, BSTree* &BST);
  void PreorderWrite(ofstream& ofs, BSTree* BST);
  void PreorderRead(ifstream& ifs, BSTree* BST, int& b);
  friend ostream& operator<<(ostream& ostr, const ElemType& x)
   {ostr<<x.num<<':'<<x.grade;return ostr;}
};
//二叉搜索树类的实现BSTreeF.cpp
//初始化二叉树,即把树根指针置空
template<class T>
void BSTree<T>::InitBSTree(BSTree<T> *&BST)
{BST=NULL;}
//判断二叉树是否为空
template<class T>
bool BSTree<T>::BSTreeEmpty(BSTree<T> *&BST)
{return BST==NULL;}
//从二叉搜索树中查找元素
template<class T>
bool BSTree<T>::Find(BSTree<T> *&BST,T item)
{if(BST==NULL) return false;
 else {if(item.grade==BST->data.grade) {
       	item=BST->data;
	return true;}
       	else if(item.grade<BST->data.grade)//递归查找左子树
	  return Find(BST->left,item);
	else                  //递归查找右子树
       return Find(BST->right,item);
}}
//更新二叉搜索树中的结点值
template<class T>
bool BSTree<T>::Update(BSTree<T> *&BST,const T item,T newc)
{if(BST==NULL) return false;
 else {
   if(item.grade==BST->data.grade) {
     BST->data=newc;
     return true;}
   else if(item.grade<BST->data.grade)
	  return Update(BST->left,item,newc);
	else
	  return Update(BST->right,item,newc);}
}
//向二叉搜索树中插入元素
template<class T>
void BSTree<T>::Insert(BSTree<T> *&BST,const T &item)
{if(BST==NULL)
  {BSTree<T> *p=new BSTree;
   p->data=item;
   p->left=p->right=NULL;
   BST=p;}
 else if(item.grade<BST->data.grade)
       Insert(BST->left,item);  //向左子树中插入元素
      else
       Insert(BST->right,item);//向右子树中插入元素
}
//从二叉搜索树中删除元素
template<class T>
bool BSTree<T>::Delete(BSTree<T> *&BST,T item)
{//从二叉搜索树中查找值为item的结点,指针t指向待比较的结点，
 //指针s指向t的双亲结点,从树根结点开始比较
  BSTree<T> *t=BST,*s=NULL;
  while(t!=NULL) {
     if(item.grade==t->data.grade) break;
     else if(item.grade<t->data.grade) {
	  s=t; t=t->left;}
	  else {s=t; t=t->right;}
  }
 //若没有找到待删除的结点，则返回假
  if(t==NULL) return false;
 //分三种不同情况删除已查找到的t结点
  if(t->left==NULL && t->right==NULL)
   { //对t结点(即待删除的结点)为叶子结点的情况进行处理
    if(t==BST) BST=NULL;
    else if(t==s->left) s->left=NULL;
        else  s->right=NULL;
    delete t;}
  else if(t->left==NULL || t->right==NULL)
	{ //对t结点为单分支结点的情况进行处理
	 if(t==BST) {  //删除树根结点
	 if(t->left==NULL) BST=t->right;
	 else  BST=t->left;}
       else {//删除非树根结点时,分四种情况进行处理
	 if(t==s->left && t->left!=NULL)
            s->left=t->left;
	 else if(t==s->left && t->right!=NULL)
	         s->left=t->right;
	       else if(t==s->right && t->left!=NULL)
                s->right=t->left;
	 else if(t==s->right && t->right!=NULL)
	        s->right=t->right;}
	 delete t;  //回收t结点,即t指针所指向的结点
       }
   else if(t->left!=NULL && t->right!=NULL)
    { //对t结点为双分支结点的情况进行处理
      //p初始指向t结点,q初始指向p结点的左子树的根结点
     BSTree<T> *p=t,*q=t->left;
      //查找t结点的中序前驱结点，查找结束后q结点为t结点
      //的中序前驱结点,p结点为q结点的双亲结点
     while(q->right!=NULL) {p=q;q=q->right;}
      //q结点的值赋给t结点
       t->data=q->data;
      //删除右子树为空的q结点,使它的左子树链接到它所在的链接位置
       if(p==t) t->left=q->left;
       else p->right=q->left;
    //回收q结点
       delete q;}
  //删除结束后返回真
    return true;
}
//利用数组建立一棵二叉搜索树
template<class T>
void BSTree<T>::CreateBSTree(BSTree<T> *&BST,T a[],int n)
{BST=NULL;
 for(int i=0;i<n;i++)
   Insert(BST,a[i]);
}
//中序遍历输出二叉搜索树中的所有结点
template<class T>
void BSTree<T>::Inorder(BSTree<T> *&BST)
{if(BST!=NULL) {
  Inorder(BST->left);
  cout<<BST->data.grade<<' ';
  Inorder(BST->right);}
}
//求二叉搜索树的深度
template<class T>
int BSTree<T>::BSTreeDepth(BSTree<T> *&BST)
{if(BST==NULL) return 0;//对于空树,返回0并结束递归
 else
  {  //计算左子树的深度
   int dep1=BSTreeDepth(BST->left);
     //计算右子树的深度
   int dep2=BSTreeDepth(BST->right);
     //返回树的深度
   if(dep1>dep2) return dep1+1;
   else return dep2+1;}
}
//求二叉搜索树中所有结点数
template<class T>
int BSTree<T>::BSTreeCount(BSTree<T> *&BST)
{if(BST==NULL) return 0;
 else 
  return BSTreeCount(BST->left)+BSTreeCount(BST->right)+1;
}
//求二叉搜索树中所有叶子结点数
template<class T>
int BSTree<T>::BSTreeLeafCount(BSTree<T> *&BST)
{if(BST==NULL) return 0;
 else if(BST->left==NULL && BST->right==NULL) return 1;
 else return BSTreeLeafCount(BST->left)+BSTreeLeafCount(BST->right);
}
//按照二叉树的广义表表示输出二叉搜索树
template<class T>
void BSTree<T>::PrintBSTree(BSTree<T> *&BST)
{if(BST==NULL) return;  //树为空时返回
 else {//否则执行如下操作
       cout<<BST->data.grade;  //输出根结点的值
       if(BST->left!=NULL || BST->right!=NULL)
	{cout<<'(';  //输出左括号
	 PrintBSTree(BST->left);  //输出左子树
	 if(BST->right!=NULL)
	  cout<<',';  //若右子树不为空则输出逗号分隔符
         PrintBSTree(BST->right);  //输出右子树
	  cout<<')';} //输出右括号
}}
//清除二叉搜索树,使之变为一棵空树
template<class T>
void BSTree<T>::ClearBSTree(BSTree<T> *&BST)
{if(BST!=NULL)
  {//当二叉树非空时进行如下操作
   ClearBSTree(BST->left);  //删除左子树
   ClearBSTree(BST->right); //删除右子树
   delete BST;              //删除根结点
   BST=NULL;}               //置根指针为空
}
//把BST二叉搜索树按照先根遍历的次序存储到文件fname中
template<class T>
void BSTree<T>::WriteFile(char* fname, BSTree<T>* BST)
{//把由fname所指字符串作为文件名的文件定义
 //为输出文件流ofs,并按二进制方式打开
 ofstream ofs(fname,ios_base::out|ios_base::binary);
 if(!ofs) {cout<<"File not open!"<<endl; exit(1);}
  //调用PreorderWrite函数向文件输出二叉搜索树
 PreorderWrite(ofs, BST);
  //关闭文件流对象所对应的文件
  ofs.close();}
//向ofs文件流所对应的文件中按先根遍历次序写入
//一棵二叉搜索树BST的递归算法,它由WriteFile函数调用
template<class T>
void BSTree<T>::PreorderWrite(ofstream& ofs,BSTree<T>* BST)
{if(BST!=NULL) {
   ofs.write((char*)BST,sizeof(*BST));
   PreorderWrite(ofs, BST->left);
   PreorderWrite(ofs, BST->right);}
}
//把fname文件中按先根遍历存储的二叉搜索树恢复到内存中
template<class T>
void BSTree<T>::ReadFile(char* fname, BSTree<T>*& BST)
{//把fname文件定义为输入文件流ifs，并按二进制方式打开
 ifstream ifs(fname,ios_base::in|ios_base::binary);
 if(!ifs) {cout<<"File not open!"<<endl; exit(1);}
 //把文件指针移到结束位置
 ifs.seekg(0,ios_base::end);
 //求出二叉搜索树中每个结点的大小
 int b=sizeof(BSTree);
 //求出文件中所存二叉树的结点数并赋给n
 int n=ifs.tellg()/b;
 //如果文件为空，则把BST置空后返回
 if(n==0) {ifs.close(); BST=NULL; return;}
 //将文件指针移到文件开始位置,以便从头开始读取每个结点
 ifs.seekg(0);
 //用文件中的第一个结点构成树根结点
 BST=new BSTree<T>;
 ifs.read((char*)BST, b);
 cout<<setw(4)<<BST->data.grade;
 //分别从文件中读取左、右子树
 PreorderRead(ifs, BST->left, b);
 PreorderRead(ifs, BST->right, b);
 //关闭ifs对应的磁盘文件
 ifs.close();}
//从ifs文件流所对应的文件中按先根遍历次序读出
//一棵二叉搜索树的递归算法,它由ReadFile函数调用
template<class T>
void BSTree<T>::PreorderRead(ifstream& ifs,BSTree<T>* BST,int& b)
{if(BST!=NULL) {
  BST=new BSTree<T>;
  ifs.read((char*)BST, b);
  cout<<setw(4)<<BST->data.grade;
  PreorderRead(ifs, BST->left, b);
  PreorderRead(ifs, BST->right, b);}
}
//二叉搜索树类的相关操作的测试BSTreeFM.cpp
#include<iostream.h>
#include<iomanip.h>
#include<fstream.h>
#include<stdlib.h>
#include<string.h>
#include "BSTreeF.h"
#include "BSTreeF.cpp"
void main()
{cout<<"BSTreeFM.cpp运行结果:\n";
 ElemType b[10]={{"1001",72},{"1002",84},{"1009",83},{"1010",75},
 {"1012",87},{"1013",79},{"1019",91},{"1020",84}};
 ElemType m={"1014",89},m2={"1016",90};
 int n,i,m1=8;
 char f[20]="D:.\\file.txt";
 BSTree<ElemType> t,*B;
 t.InitBSTree(B);
 t.CreateBSTree(B,b,m1);
 n=t.BSTreeCount(B);
 cout<<"二叉搜索树的所有结点数="<<n<<endl;
 if(!t.BSTreeEmpty(B))
   cout<<"二叉搜索树非空!\n";
 else
   cout<<"二叉搜索树为空!\n";
 cout<<"中序遍历:";t.Inorder(B);cout<<endl;
 n=t.BSTreeDepth(B);
 cout<<"二叉搜索树的深度="<<n<<endl;
 n=t.BSTreeLeafCount(B);
 cout<<"二叉搜索树的所有叶子结点数="<<n<<endl;
 cout<<"按二叉搜索树的广义表:\n";
 t.PrintBSTree(B);cout<<endl;
 t.Insert(B,m);
 cout<<"中序遍历:";t.Inorder(B);cout<<endl;
 if(t.Find(B,m)) cout<<"查找成功!\n";
 else cout<<"查找不成功!\n";
 m=b[6];
 if(t.Update(B,m,m2)) cout<<"更新成功!\n";
 else cout<<"更新不成功!\n";
 cout<<"中序遍历:";t.Inorder(B);cout<<endl;
 n=t.BSTreeCount(B);
 cout<<"二叉搜索树的所有结点数="<<n<<endl;
 n=t.BSTreeDepth(B);
 cout<<"二叉搜索树的深度="<<n<<endl;
 if(t.Delete(B,m)) cout<<"删除成功!\n";
 else cout<<"删除不成功!\n";
 cout<<"中序遍历:";t.Inorder(B);cout<<endl;
 n=t.BSTreeDepth(B);
 cout<<"二叉搜索树的深度="<<n<<endl;
 n=t.BSTreeCount(B);
 cout<<"二叉搜索树的所有结点数="<<n<<endl;
 cout<<"输出所有成绩:\n";
 t.WriteFile(f,B);t.ReadFile(f,B);
 cin.get();}
BSTreeFM.cpp运行结果:
二叉搜索树的所有结点数=8
二叉搜索树非空!
中序遍历:72 75 79 83 84 84 87 91 
二叉搜索树的深度=5
二叉搜索树的所有叶子结点数=3
按二叉搜索树的广义表:
72(,84(83(75(,79)),87(84,91)))
中序遍历:72 75 79 83 84 84 87 89 91 
查找成功!
更新成功!
中序遍历:72 75 79 83 84 84 87 89 90 
二叉搜索树的所有结点数=9
二叉搜索树的深度=5
删除不成功!
中序遍历:72 75 79 83 84 84 87 89 90 
二叉搜索树的深度=5
二叉搜索树的所有结点数=9
输出所有成绩:
  72  84  83  75  79  87  84  90  89