先來看這個二叉排序樹

下面是討論刪除的情況：

我們知道，如果要刪除的葉子結(jié)點，則可以直接刪除。

但如果刪除的不是葉子結(jié)點呢？

我們知道這個樹的中序遍歷如下：

也就是說，比如要刪除105，則我們可以把104，或108提上去覆蓋掉，這樣實現(xiàn)了刪除，又不保證了他是二叉排序樹。

下面是代碼

Status DeleteBST(BiTree *T, int key) {if( !*T ){return FALSE;}else{if( key == (*T)->data ){return Delete(T);}else if( key < (*T)->data ){return DeleteBST(&(*T)->lchild, key);}else{return DeleteBST(&(*T)->rchild, key);}} }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 = s->data;if( q != *p ){q->rchild = s->lchild;}else{q->lchild = s->lchild;}free(s);}return TRUE; }

總結(jié)

以上是生活随笔為你收集整理的二叉排序树的删除操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。