数据结构各种算法原代码及图形示例

				算法 8.6
				void Delete_BST (BiTree &T,  KeyType kval ) {
				      // 若二叉查找树T中存在关键字等于kval的数据元素，则删除之。
				      f = NULL;
				      if (Search_BST(T,kval,p,f)) {      // 找到其关键字等于kval的数据元素
				        if (p->lchild && p->rchild) {    // 左右子树均不空
				           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;             
				           else  q->lchild = s->lchild;  // s结点即为p结点的左子树根
				           delete s;    
				        }// if
				        else {
				          if (!p->rchild) {              // 右子树空则只需挂接它的左子树
				             q = p;  p = p->lchild; 
				          }//if 
				          else {                        // 左子树空，只需挂接它的右子树
				            q = p;  p = p->rchild;  
				          }
				          // 将指针p所指子树挂接到被删结点的双亲(指针f所指的)结点上
				          if (!f) T = p;                // 被删结点为根结点
				          else  if (q == f->lchild)  f->lchild = p; 
				                else  f->rchild = p;    // 完成子树的挂接
				          delete q;                     // 释放被删结点空间
				        }//else
				      }//if
				}//Delete_BST