二叉排序树

#define FALSE 0
#define TRUE 1
#define ElemType int
#define Status int
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)>(b))


#include
#include
#include
using namespace std;

typedef struct BiTNode { // 结点结构
    ElemType data;
    struct BiTNode  *lchild, *rchild;   // 左右孩子指针
} BiTNode, *BiTree;

Status SearchBST (BiTree T, ElemType key,  BiTree f, BiTree &p )
{ // 在根指针 T 所指二叉排序树中递归地查找其关键字等于 key 的数据元素，若查找成功，则返回指针 p 指向该数据元素的结点，并返回TRUE;  
  // 否则表明查找不成功，返回指针 p 指向查找路径上访问的最后一个结点，并返回函FALSE, 指针 f 指向当前访问 的结点的双亲，其初始调用值为NULL
if (!T)  { p = f;  return FALSE; }  // 查找不成功
else  if ( EQ(key, T->data) ) { p = T;  return TRUE; }  // 查找成功
else  if ( LT(key, T->data) )  SearchBST (T->lchild, key, T, p );    // 在左子树中继续查找
else  SearchBST (T->rchild, key, T, p );            // 在右子树中继续查找
} // SearchBST
void Delete ( BiTree &p )
{  // 从二叉排序树中删除结点 p， 并重接它的左子树或右子树
   BiTree q,s;
   if (!p->rchild) {   // 右子树为空树则只需重接它的左子树
  q = p;  p = p->lchild;  free(q);
   } 
   else if (!p->lchild)  {    // 左子树为空树只需重接它的右子树
  q = p;  p = p->rchild;  free(q);
   } 
   else{     //左右子树都不空
   q = p;  
s = p->lchild;   while (s->rchild)   {s = s->rchild; } // 转左,然后向右到尽头
s-> rchild = q-> rchild;// 将待删除结点的右子树重接到S上
p = p->lchild;                         
free(q);
   }
} // Delete
Status InsertBST(BiTree &T, ElemType e ) 
{  // 当二叉排序树中不存在关键字等于 e.key 的数据元素时，插入元素值为 e 的结点，并返回 TRUE; 否则，不进行插入并返回FALSE
BiTree p,s;
    if (!SearchBST ( T, e, NULL, p )){
s = (BiTree) malloc (sizeof (BiTNode));   // 为新结点分配空间
s->data = e;  s->lchild = s->rchild = NULL;  
if  ( !p )  T = s;     // 插入 s 为新的根结点
else   if ( LT(e, p->data) )   p->lchild = s;       // 插入 *s 为 *p 的左孩子
else  p->rchild = s;     // 插入 *s 为 *p 的右孩子
return TRUE;     // 插入成功
   }
   else return FALSE;
} // InsertBST
Status DeleteBST (BiTree &T,  ElemType key )
{ // 若二叉排序树 T 中存在其关键字等于 key 的数据元素，则删除该数据元素结点，并返回函数值 TRUE，否则返回函数值 FALSE
if (!T)  return FALSE; // 不存在关键字等于key的数据元素
else  {    
if ( EQ (key, T->data) ) {  Delete (T);   return TRUE;  }// 找到关键字等于key的数据元素
else if ( LT (key, T->data) ) DeleteBST ( T->lchild, key );   // 继续在左子树中进行查找
else DeleteBST ( T->rchild, key ); // 继续在右子树中进行查找
}
} // DeleteBST
void InOrderTraverse(BiTree T)
{//中序遍历二叉树，递归
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<" ";
InOrderTraverse(T->rchild);
}
}

int arr[10] = {1,5,6,4,3,2,7,8,10,9};
int main()
{
ElemType e;
int door = 1,c,flag;
BiTree T,p;
T = NULL;
for(int i=0; i<10; ++i)
InsertBST(T,arr[i]);
while(door){

cout<<endl<<"请输入要查找元素："; cin>>e;

if(SearchBST(T,e,NULL,p)) { cout<<endl<<"查找成功!"<<endl<<"是否将其从二叉排序树中删除： 1.是 2.否  "<<endl; 
cin>>flag;
if(flag) DeleteBST(T,e);
}
else { cout<<"查找失败！"<<endl<<"是否将元素插入到二叉排序树中: 1.是 2.否  "<<endl; 
cin>>flag;
if(flag) DeleteBST(T,e);   InsertBST(T,e); }

cout<<endl<<"--------1.继续查找   2.查看二叉排序树元素   0.退出----------"<<endl<<"请输入数字继续操作：";
cin>>c;
switch(c){
case 1: door =1; break;
case 2: 
cout<<"二叉排序树中序遍历为："; InOrderTraverse(T); cout<<endl<<"是否继续查找: 1.是 2.否  "<<endl; 
cin>>flag;
if(flag){ door =1; break; }
else  {  cout<<"退出程序！"<<endl;  door = 0 ; break;}
case 0: door =0; break;
default: cout<<"输入错误，退出程序！"<<endl;  door = 0;  break;
} //switch
}//while
return 0;
}