// bo9-2.cpp 動態查找表(二叉排序樹)的基本操作(8個)
 typedef ElemType TElemType;
 #include"c6-2.h"

 Status InitDSTable(BiTree &DT) // 同bo6-2.cpp
 { // 操作結果: 構造一個空的動態查找表DT
   DT=NULL;
   return OK;
 }

 void DestroyDSTable(BiTree &DT) // 同bo6-2.cpp
 { // 初始條件: 動態查找表DT存在。操作結果: 銷毀動態查找表DT
   if(DT) // 非空樹
   {
     if(DT->lchild) // 有左孩子
       DestroyDSTable(DT->lchild); // 銷毀左孩子子樹
     if(DT->rchild) // 有右孩子
       DestroyDSTable(DT->rchild); // 銷毀右孩子子樹
     free(DT); // 釋放根結點
     DT=NULL; // 空指針賦0
   }
 }

 BiTree SearchBST(BiTree T,KeyType key)
 { // 在根指針T所指二叉排序樹中遞歸地查找某關鍵字等于key的數據元素，
   // 若查找成功，則返回指向該數據元素結點的指針,否則返回空指針。算法9.5(a)
   if((!T)||EQ(key,T->data.key))
     return T; // 查找結束
   else if LT(key,T->data.key) // 在左子樹中繼續查找
     return SearchBST(T->lchild,key);
   else
     return SearchBST(T->rchild,key); // 在右子樹中繼續查找
 }

 void SearchBST(BiTree &T,KeyType key,BiTree f,BiTree &p,Status &flag) // 算法9.5(b)改
 { // 在根指針T所指二叉排序樹中遞歸地查找其關鍵字等于key的數據元素，若查找
   // 成功，則指針p指向該數據元素結點，并返回TRUE，否則指針p指向查找路徑上
   // 訪問的最后一個結點并返回FALSE,指針f指向T的雙親，其初始調用值為NULL
   if(!T) // 查找不成功
   {
     p=f;
     flag=FALSE;
   }
   else if EQ(key,T->data.key) //  查找成功
   {
     p=T;
     flag=TRUE;
   }
   else if LT(key,T->data.key)
     SearchBST(T->lchild,key,T,p,flag); // 在左子樹中繼續查找
   else
     SearchBST(T->rchild,key,T,p,flag); //  在右子樹中繼續查找
 }

 Status InsertBST(BiTree &T, ElemType e)
 { // 當二叉排序樹T中不存在關鍵字等于e.key的數據元素時，插入e并返回TRUE，
   // 否則返回FALSE。算法9.6(改)
   BiTree p,s;
   Status flag;
   SearchBST(T,e.key,NULL,p,flag);
   if(!flag) // 查找不成功
   {
     s=(BiTree)malloc(sizeof(BiTNode));
     s->data=e;
     s->lchild=s->rchild=NULL;
     if(!p)
       T=s; // 被插結點*s為新的根結點
     else if LT(e.key,p->data.key)
       p->lchild=s; // 被插結點*s為左孩子
     else
       p->rchild=s; // 被插結點*s為右孩子
     return TRUE;
   }
   else
     return FALSE; // 樹中已有關鍵字相同的結點，不再插入
 }

 void Delete(BiTree &p)
 { // 從二叉排序樹中刪除結點p，并重接它的左或右子樹。算法9.8
   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) // 轉左，然后向右到盡頭（找待刪結點的前驅）
     {
       q=s;
       s=s->rchild;
     }
     p->data=s->data; // s指向被刪結點的＂前驅＂（將被刪結點前驅的值取代被刪結點的值）
     if(q!=p)
       q->rchild=s->lchild; // 重接*q的右子樹
     else
       q->lchild=s->lchild; // 重接*q的左子樹
     free(s);
   }
 }

 Status DeleteBST(BiTree &T,KeyType key)
 { // 若二叉排序樹T中存在關鍵字等于key的數據元素時，則刪除該數據元素結點，
   // 并返回TRUE；否則返回FALSE。算法9.7
   if(!T) // 不存在關鍵字等于key的數據元素
     return FALSE;
   else
   {
     if EQ(key,T->data.key) // 找到關鍵字等于key的數據元素
       Delete(T);
     else if LT(key,T->data.key)
       DeleteBST(T->lchild,key);
     else
       DeleteBST(T->rchild,key);
     return TRUE;
   }
 }

 void TraverseDSTable(BiTree DT,void(*Visit)(ElemType))
 { // 初始條件: 動態查找表DT存在，Visit是對結點操作的應用函數
   // 操作結果: 按關鍵字的順序對DT的每個結點調用函數Visit()一次且至多一次
   if(DT)
   {
     TraverseDSTable(DT->lchild,Visit); // 先中序遍歷左子樹
     Visit(DT->data); // 再訪問根結點
     TraverseDSTable(DT->rchild,Visit); // 最后中序遍歷右子樹
   }
 }