#include <iostream>
#include <iomanip>
using namespace std;

typedef struct BinaryTree
{
 int data;
 struct BinaryTree *l;
 struct BinaryTree *r;
}*BiTree,BiNode;
 
class BiSearchT
{
private:
 BiTree root;
public:
 BiSearchT() :root(NULL) {}
 int PreOrderTraverse(BiTree t,int (*Visit)(int e));
 int InOrderTraverse(BiTree t,int (*Visit)(int e));
 int InsertBST(BiTree *t,int e);
 void Delete(BiTree *p);
 bool DeleteBST(BiTree *t,int key);
 bool SearchBST(BiTree t,int key,BiTree f,BiTree *p);
};
//先序遍歷二叉樹T
int BiSearchT::PreOrderTraverse(BiTree t,int (*Visit)(int d))
{
 if(t)
 {
  if(Visit(t->data))
   if(PreOrderTraverse(t->l,Visit))
    if(PreOrderTraverse(t->r,Visit)) return 1;
    return 0;
    }else return 1;
}
//中序遍歷二叉樹T
int BiSearchT::InOrderTraverse(BiTree t,int (*Visit)(int d))
{
 if(t)
 {
  if(InOrderTraverse(t->l,Visit))
   if(Visit(t->data))
    if(InOrderTraverse(t->r,Visit)) return 1;
    return 0;
    }else return 1;
}
//二叉排序樹上的查找遞歸算法
bool BiSearchT::SearchBST(BiTree t,int key,BiTree f,BiTree *p)
{
 if(!t)
  {*p=f;return false;}
  else if(key==t->data) {*p=t;return true;}
  else if(key<t->data) SearchBST(t->l,key,t,p);
  else SearchBST(t->r,key,t,p);
}
//插入算法
int BiSearchT::InsertBST(BiTree *t,int e)
{
 BiTree p;
 BiTree s;
 if(!SearchBST(*t,e,NULL,&p))
 {
  s=(BiTree)malloc(sizeof(BiNode));
  s->data=e;s->l=s->r=NULL;
  if(!p) *t=s;
  else if(e<p->data) p->l=s;
  else p->r=s;
  return true;
 }
 else return false;
}
//在二叉樹中刪除一個結點
void BiSearchT::Delete(BiTree *p)
{
 BiTree q,s;
 if(!(*p)->r)
 {
  q=(*p);
  (*p)=(*p)->l;
  free(q);
 }
 else if(!(*p)->l)
 {
  q=(*p);
  (*p)=(*p)->r;
  free(q);
 }
 else
 {
  q=s=(*p)->l;
  while(s->r) s=s->r;
  s->r=(*p)->r;
  free(*p);
  (*p)=q;
 }
}
//二叉排序樹的刪除
bool BiSearchT::DeleteBST(BiTree *t,int key)
{
 if(*t!=NULL)
 {
  if(key==(*t)->data) Delete(t);
  else
   if(key<(*t)->data) DeleteBST(&((*t)->l),key);
   else DeleteBST(&((*t)->r),key);
   return true;
 }
   else return false;
}
//輸出二叉排序樹的數據地域值
int printelem(int d)
{
 cout<<setw(4)<<d;
 return 1;
}

void main()
{
 BiTree sroot=NULL;
 BiTree Croot=NULL;
 int q,c,d,e,f,g,h,l,m,x;
 cout<<"..............................二叉排序樹的基本操作.............................."<<endl;
 cout<<"請您輸入十個正整數作為二叉排序樹的十個結點:"<<endl;
 cin>>q>>c>>d>>e>>f>>g>>h>>l>>m>>x;
 int i,j,k,a[10]={q,c,d,e,f,g,h,l,m,x};
 int n=7,b[]={10,7,6,9,20,12,22};
 BiSearchT my;
 for(i=0;i<10;i++)
  my.InsertBST(&sroot,a[i]);
 cout<<"二叉排序樹創建成功!"<<endl;
    cout<<"先序遍歷二叉排序樹:"<<endl;
 my.PreOrderTraverse(sroot,printelem);
 cout<<endl;
 cout<<"中序遍歷二叉排序樹:"<<endl;
 my.InOrderTraverse(sroot,printelem);
 cout<<endl;
    cout<<"請輸入你要查找的元素:";
 cin>>i;
 if(i==q||i==c||i==d||i==e||i==f||i==g||i==h||i==l||i==m||i==x)
  cout<<"查找成功!"<<endl;
 else cout<<"查找失敗!"<<endl;
 cout<<"請輸入你要刪除的元素(...輸入的元素必須在二叉排序樹中...):";
 cin>>j;
 my.DeleteBST(&sroot,j);
 cout<<"先序遍歷二叉排序樹:"<<endl;
 my.PreOrderTraverse(sroot,printelem);
 cout<<endl;
 cout<<"中序遍歷二叉排序樹:"<<endl;
    my.InOrderTraverse(sroot,printelem);
 cout<<endl;
    cout<<"在此基礎上請輸入你要插入的元素:";
 cin>>k;
 my.InsertBST(&sroot,k);
    cout<<"先序遍歷二叉排序樹:"<<endl;
 my.PreOrderTraverse(sroot,printelem);
 cout<<endl;
 cout<<"中序遍歷二叉排序樹:"<<endl;
    my.InOrderTraverse(sroot,printelem);
 cout<<endl;
}