?? bstreem.txt

?? C++描述的數據結構內容,在C++builder的環境中運行,這是第二部分
?? TXT
字號:
//二叉搜索樹的類定義BSTree.h
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);
};  
//二叉搜索樹類的實現BSTree.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==BST->data) {
       	item=BST->data;
	return true;}
       	else if(item<BST->data)//遞歸查找左子樹
	  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==BST->data) {
     BST->data=newc;
     return true;}
   else if(item<BST->data)
	  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<T>;
   p->data=item;
   p->left=p->right=NULL;
   BST=p;}
 else if(item<BST->data)
       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==t->data) break;
     else if(item<t->data) {
	  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<<' ';
  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;  //輸出根結點的值
       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;}}               //置根指針為空
//二叉搜索樹相關操作的測試BSTreeM.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include "BSTree.h"
#include "BSTree.cpp"
void main()
{cout<<"BSTreeM.cpp運行結果:\n";
 char b[50]="abxycdMNefgzkl";
 BSTree<char> t,*B;
 int n,m=14;
 t.InitBSTree(B);
 t.CreateBSTree(B,b,m);
 n=t.BSTreeCount(B);
 cout<<"二叉搜索樹的所有結點數="<<n<<endl;
 if(!t.BSTreeEmpty(B))
   cout<<"二叉搜索樹非空!\n";
 else
   cout<<"二叉搜索樹為空!\n";
 cout<<"中序遍歷二叉搜索樹:\n";
 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;
 if(t.Find(B,'d')) cout<<"查找成功!\n";
 else cout<<"查找不成功!\n";
 if(t.Update(B,'d','D')) cout<<"更新成功!\n";
 else cout<<"更新不成功!\n";
 cout<<"中序遍歷二叉搜索樹:\n";
 t.Inorder(B);cout<<endl;
 t.Insert(B,'m');
 cout<<"中序遍歷二叉搜索樹:\n";
 t.Inorder(B);cout<<endl;
 t.Insert(B,'n');
 cout<<"中序遍歷二叉搜索樹:\n";
 t.Inorder(B);cout<<endl;
 n=t.BSTreeDepth(B);
 cout<<"二叉搜索樹的深度="<<n<<endl;
 if(t.Delete(B,'e')) cout<<"刪除成功!\n";
 else cout<<"刪除不成功!\n";
 cout<<"中序遍歷二叉搜索樹:\n";
 t.Inorder(B);cout<<endl;
 n=t.BSTreeDepth(B);
 cout<<"二叉搜索樹的深度="<<n<<endl;
 cin.get();}
BSTreeM.cpp運行結果:
二叉搜索樹的所有結點數=14
二叉搜索樹非空!
中序遍歷二叉搜索樹:
M N a b c d e f g k l x y z 
二叉搜索樹的深度=10
二叉搜索樹的所有葉子結點數=3
按二叉搜索樹的廣義表輸出二叉搜索樹:
a(M(,N),b(,x(c(,d(,e(,f(,g(,k(,l)))))),y(,z))))
查找成功!
更新成功!
中序遍歷二叉搜索樹:
M N a b c D e f g k l x y z 
中序遍歷二叉搜索樹:
M N a b c D e f g k l m x y z 
中序遍歷二叉搜索樹:
M N a b c D e f g k l m n x y z 
二叉搜索樹的深度=12
刪除成功!
中序遍歷二叉搜索樹:
M N a b c D f g k l m n x y z 
二叉搜索樹的深度=11
?? 文件大小 221 K
?? 上傳用戶 zxyxwd6
?? 所屬分類數據結構
??? 相關標簽

#builder #數據結構 #分 #環境
?? 快捷鍵說明

復制代碼 Ctrl + C
搜索代碼 Ctrl + F
全屏模式 F11
切換主題 Ctrl + Shift + D
顯示快捷鍵 ?
增大字號 Ctrl + =
減小字號 Ctrl + -
亚洲欧美第一页_禁久久精品乱码_粉嫩av一区二区三区免费野_久草精品视频

?? bstreem.txt

?? 快捷鍵說明
