//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :6  (6_4)                   *
//*PROGRAM          :二叉排序樹的綜合操作       *
//*CONTENT          :Insert,Search,Deltet       *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
enum BOOL{False,True};
typedef struct  BiTNode       //定義二叉樹節(jié)點結構
{char  data;                  //為了方便，數(shù)據(jù)域只有關鍵字一項
 struct BiTNode *lchild,*rchild; //左右孩子指針域
}BiTNode,*BiTree;
BOOL SearchBST(BiTree,char,BiTree,BiTree&); //在二叉排序樹中查找元素
BOOL InsertBST(BiTree &,char);    //在二叉排序樹中插入元素  
BOOL DeleteBST(BiTree &,char);    //在二叉排序樹中刪除元素
void Delete(BiTree &);            //刪除二叉排序樹的根結點
void InorderBST(BiTree);          //中序遍歷二叉排序樹，即從小到大顯示各元素
void main()
{BiTree T,p;
 char ch,keyword,j='y';
 BOOL temp;
/* textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();*/
 //-------------------------程序說明-------------------------------
 printf("This program will show how to operate to a Binary Sort  Tree.\n");
 printf("You can display all elems,search a elem,\ninsert a elem,delete a elem.\n");
 //----------------------------------------------------------------
 T=NULL;
 while(j!='n')
    {printf("1.display\n");
     printf("2.search\n");
     printf("3.insert\n");
     printf("4.delete\n");
     printf("5.exit\n");
     scanf(" %c",&ch); //輸入操作選項
     switch(ch)
      {case '1':if(!T) printf("The BST has no elem.\n");
		else {InorderBST(T);printf("\n");}
		break;
       case '2':printf("Input the keyword of elem to be searched(a char):");
		scanf(" %c",&keyword); //輸入要查找元素的關鍵字
		temp=SearchBST(T,keyword,NULL,p);
		if(!temp) printf("%c isn't existed!\n",keyword); //沒有找到
		else printf("%c has been found!\n",keyword); //成功找到
		break;
       case '3':printf("Input the keyword of elem to be inserted(a char):");
		scanf(" %c",&keyword); //輸入要插入元素的關鍵字
		temp=InsertBST(T,keyword);
		if(!temp) printf("%c has been existed!\n",keyword); //該元素已經(jīng)存在
		else printf("Sucess to inert %c!\n",keyword); //成功插入
		break;
       case '4':printf("Input the keyword of elem to be deleted(a char):");
		scanf(" %c",&keyword); //輸入要刪除元素的關鍵字
		temp=DeleteBST(T,keyword);
		if(!temp) printf("%c isn't existed!\n",keyword); //該元素不存在
		else printf("Sucess to delete %c\n",keyword); //成功刪除
		break;
       default: j='n';
    }
 }
 printf("The program is over!\nPress any key to shut off the window!\n");
 getchar();getchar();
}
void InorderBST(BiTree T)
{//以中序方式遍歷二叉排序樹T，即從小到大顯示二叉排序樹的所有元素
 if(T->lchild) InorderBST(T->lchild);
 printf("%2c",T->data);
 if(T->rchild) InorderBST(T->rchild);
}

BOOL SearchBST(BiTree T,char key,BiTree f,BiTree &p)
{//在根指針T所指二叉排序樹中遞歸的查找其關鍵字等于key的元素，若查找成功
 //則指針p指向該數(shù)據(jù)元素，并返回True,否則指針指向查找路徑上訪問的最后一
 //個結點并返回False,指針f指向T的雙親，其初始調(diào)用值為NULL
 BOOL tmp1,tmp2;
 tmp1=tmp2=False;
 if(!T) {p=f;return False;}  //查找不成功
 else if(key==T->data) {p=T;return True;} //查找成功
 else if(key<T->data) tmp1=SearchBST(T->lchild,key,T,p); //在左子樹中繼續(xù)查找
 else tmp2=SearchBST(T->rchild,key,T,p); //在右子樹中繼續(xù)查找
 if(tmp1||tmp2) return True; //若在子樹中查找成功，向上級返回True
 else return False;          //否則返回False
}

BOOL InsertBST(BiTree &T,char e)
{//當二叉排序樹T中不存在元素e時，插入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(e<p->data) p->lchild=s; //被插結點*s為左孩子
    else p->rchild=s;   //被插結點*s為右孩子
    return True;  //成功插入
   }
 else return False; //樹中已存在關鍵字為e的數(shù)據(jù)元素
}

BOOL DeleteBST(BiTree &T,char key)
{//若二叉排序樹T中存在關鍵字等于key的數(shù)據(jù)元素時，則刪除該數(shù)據(jù)元素結點
 //并返回True,否則返回False
 BOOL tmp1,tmp2;
 tmp1=tmp2=False;
 if(!T) return False;  //不存在關鍵字等于key的數(shù)據(jù)元素
 else
   {if(key==T->data) {Delete(T); return True;} 
       //找到關鍵字等于key的數(shù)據(jù)元素并刪除它
    else if(key<T->data) tmp1=DeleteBST(T->lchild,key); //繼續(xù)在左子樹中刪除
    else tmp2=DeleteBST(T->rchild,key);   //繼續(xù)在右子樹中刪除
    if(tmp1||tmp2) return True;    //在子樹中刪除成功，返回True
    else return False;      //不存在該元素
   }
}

void Delete(BiTree &p)
{//在二叉排序樹中刪除結點p,并重接它的左或右子樹
 BiTree s,q;
 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)
     {q=s;s=s->rchild;} //轉(zhuǎn)左，然后向右走到盡頭
   p->data=s->data;     //s指向被刪結點的“前驅(qū)”
   if(q!=p) q->rchild=s->rchild; //重接*q的右子樹
   else q->lchild=s->lchild;     //重接*q的左子樹
   free(s);
  }
}