二叉排序树的创建

二叉排序树的创建是从空的二叉排序树開始，每输入一个结点，经过查找操作。将新结点插入到当前二叉排序树的合适位置。

（1）将二叉排序树T初始化为空树

（2）读入一个keyword为key的结点，将此结点插入二叉排序树T中。

（3）反复操作，直至读入的keywordkey是输入结束标志。

Void CreatBST(BSTree &T)
{
T=NULL;
cin>>e;
while(e.key!=ENDFLAG)
{
 InsertBST(T,e);
 cin>>e;
}
}

注意:不同的的插入次序的序列生成不同形态的二叉排序树

二叉排序树的删除

在二叉排序树中删除一个结点，这是二叉排序树中最有深度的操作。

主要分三种操作：

1. 若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。因为删去叶子结点不破坏整棵树的结构。则仅仅需改动其双亲结点的指针就可以。

2. 若*p结点仅仅有左子树PL或右子树PR，此时仅仅要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）就可以。作此改动也不破坏二叉排序树的特性。

3. 若*p结点的左子树和右子树均不空。在删去*p之后。为保持其他元素之间的相对位置不变。可按中序遍历保持有序进行调整。比較好的做法是，找到*p的直接前驱（或直接后继）*s。用*s来替换结点*p。然后再删除结点*s。
   /* 若二叉排序树T中存在keyword等于key的数据元素时，则删除该数据元素结点, */
   /* 并返回TRUE。否则返回FALSE。 */

   Status DeleteBST(BiTree *T,int key)
   { 
           if(!*T) /* 不存在keyword等于key的数据元素 */ 
   return FALSE;
   else
       {
   if (key==(*T)->data) /* 找到keyword等于key的数据元素 */ 
       return Delete(T);
   else if (key<(*T)->data)
       return DeleteBST(&(*T)->lchild,key);
   else
       return DeleteBST(&(*T)->rchild,key);
   
   }
   }
   
   /* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
   Status Delete(BiTree *p)
   {
   BiTree q,s;
   if((*p)->rchild==NULL) /* 右子树空则仅仅需重接它的左子树（待删结点是叶子也走此分支) */
   {
   q=*p; *p=(*p)->lchild; free(q);
   }
   else if((*p)->lchild==NULL) /* 仅仅需重接它的右子树 */
   {
       q=*p; *p=(*p)->rchild; free(q);
   }
   else /* 左右子树均不空 */
   {
   q=*p; s=(*p)->lchild;
   while(s->rchild) /* 转左。然后向右到尽头（找待删结点的前驱） */
   {
       q=s;
       s=s->rchild;
   }
   (*p)->data=http://www.mamicode.com/s->data; /*  s指向被删结点的直接前驱（将被删结点前驱的值代替被删结点的值） */>