2009/12/29 9.2.1-二叉排序树：删除2 9.2.1-二叉排序树删除3 ·二叉排序树的副除 ·二叉排序树的副除 ,*p的左子树P和右子树Pπ均不为空 ■*p的左子树P和右子树P均不为空 方法L、P粳普p成为f的 33 方2、与方法1对称，P接普 到 子树，P成为P最右下结 233 33 p成为f的子树，P成为P最 3 3 点（中序塘历P,所得序列的 左下结点（中序遗历P.所得序列 ④ 的第一个结点)的左子树， 46 最后一个结点)的右子树， 3 4 38 46 40 40 50 这种方法可能会导致二 叉岸序树高度的增长1 35 40 4048 38 48 本例中高度：5→6 8 38 48 4310 44/10 合 9.2.1-二叉排序树：删除4 9.2.1-二叉排序树：删除5 ,二叉排序树的除 ·二叉排序树的副除 。*p的左子树P和右子树P均不为空 ·p的左于树P和右子树P均不为空 测除时，如何不增长树的高度？ 33 方法4、与方法3对称，令*p 33 方法老、令“p的中序遗历的直 23 4④ 的中序速历的直接后维誉代 接前驱替代p,再从二叉排 *p,再从二叉排序刺中副去 序树中副去它的直捷前驱。 37 46 它的直接后维。 这种方法不会导致二叉 35 38 35 4048 排序树高度的增长1 本例中高度：5→5 48 38 45/103 合 46/103 9.2.1-二叉排序树：删除算法 9.2.1-二叉排序树：删除算法 ·二叉排序制的则膝算法9.7 。算法9.8从二又排序树中除p教向的结点 Sta ree &T. KeyType key Status Delete BiTree) 二叉排序树T中存在关幢字等于ky的业据元素时，副除该 if(p->rchild)fq-rpp>lchild:free(q}∥右子树为空 eeif(p>ehid)q-prp>rhid:req}∥左子树为空 ∥元素结点并返回TRUE:否则氪回FAL.SE else if (T)return FALSE: q-p:s-p->lchild; ebe{ while(s>rehild){g-s;s一s>eh山：}H使物向被结点的前易 if EQ(key,T->data.key)) pdata-sdata; return Dele(T片∥找到关精字等于key的量拥元素 if(q!=p)g->rchild=s>rchild; else if (LT(key,Tdata.key)) else g->lchild-s>lchild; return DeleteBST(Tlchild,keyy: free(s): else return DeleteBST(T>rehild,key) return TRUE: 471103 48/103 画 82009/12/29 8 9.2.1 -二叉排序树:删除2  二叉排序树的删除  *p的左子树PL和右子树PR均不为空 方法1、P 33 L 接替*p成为*f 的 43/103 33 23 44 12 37 46 40 50 48 35 38 46 50 48 23 12 37 35 40 38 方法 L 接替 p 子树， PR成为PL最右下结 点(中序遍历PL所得序列的 最后一个结点)的右子树。 40 这种方法可能会导致二 叉排序树高度的增长！ 本例中高度：56 9.2.1 -二叉排序树:删除3  二叉排序树的删除  *p的左子树PL和右子树PR均不为空 方法2、与方法1对称，PR 接替 44/103 48 46 50 33 23 44 12 37 46 40 50 48 35 38 33 23 12 R *p成为*f 的子树， PL成为PR最 左下结点(中序遍历PR所得序列 的第一个结点)的左子树。 46 37 35 40 38 9.2.1 -二叉排序树:删除4  二叉排序树的删除  *p的左子树PL和右子树PR均不为空 删除时，如何不增长树的高度？ 33 45/103 方法3、令*p的中序遍历的直 接前驱替代*p，再从二叉排 序树中删去它的直接前驱。 这种方法不会导致二叉 排序树高度的增长！ 本例中高度：55 33 23 44 12 37 46 40 50 48 35 38 40 38 9.2.1 -二叉排序树:删除5  二叉排序树的删除  *p的左子树PL和右子树PR均不为空 方法4 与方法3对称 令*p 33 46/103 方法4、与方法3对称，令*p 的中序遍历的直接后继替代 *p，再从二叉排序树中删去 它的直接后继。 33 23 44 12 46 50 48 37 35 40 38 46 46 48 50 48 50 9.2.1 -二叉排序树:删除算法  二叉排序树的删除算法9.7 Status DeleteBST(BiTree &T, KeyType key){ // 当二叉排序树T中存在关键字等于key的数据元素时，删除该 数据 // 元素结点并返回TRUE 否则返回FALSE 47/103 // 元素结点并返回TRUE；否则返回FALSE if ( !T ) return FALSE; else { if ( EQ(key, T->data.key)) return Delete(T); // 找到关键字等于key的数据元素 else if ( LT(key, T->data.key)) return DeleteBST(T->lchild, key); else return DeleteBST(T->rchild, key); } } 9.2.1 -二叉排序树:删除算法  算法9.8 从二叉排序树中删除 p 指向的结点 Status Delete (BiTree &p){ if ( !p->rchild ) { q = p; p=p->lchild; free(q); } // 右子树为空 else if ( !p->lchild ){ q = p; p=p->rchild; free(q); } // 左子树为空 l { 48/103 else { q = p; s = p->lchild; while ( s->rchild ) { q=s; s=s->rchild; } // 使s 指向被删结点的前驱 p->data = s->data; if ( q!=p ) q->rchild = s->rchild; else q->lchild = s->lchild; free(s); } return TRUE; }