goal00001111

對于一般的二叉樹來說，刪去樹中的一個結(jié)點是沒有意義的，因為它將使以被刪除的結(jié)點為根的子樹變成森林，破壞了整棵樹的結(jié)構(gòu)
但是，對于二叉排序樹，刪去樹上的一個結(jié)點相當于刪去有序序列中的一個記錄，只要在刪除某個結(jié)點后不改變二叉排序樹的特性即可。
??????在二叉排序樹上刪除一個結(jié)點的算法如下：
btree?*?DeleteBST(btree?*b,?ElemType?x)
{
??????if?(b)
??????{
????????????if?(b->data?==?x)
??????????????????b?=?DelNode(b);
????????????else?if?(b->data?>?x)
??????????????????b->lchild?=?DeleteBST(b->lchild,?x);
????????????else
??????????????????b->rchild?=?DeleteBST(b->rchild,?x);
??????}
??????return?b;
}
其中刪除過程有兩種方法。
第一種過程如下：
1。若p有左子樹，找到其左子樹的最右邊的葉子結(jié)點r，用該葉子結(jié)點r來替代p，把r的左孩子
作為r的父親的右孩子。
2。若p沒有左子樹，直接用p的右孩子取代它。

第二種過程如下：
1。若p有左子樹，用p的左孩子取代它；找到其左子樹的最右邊的葉子結(jié)點r，把p的右子樹作為r
的右子樹。
2。若p沒有左子樹，直接用p的右孩子取代它。
????兩種方法各有優(yōu)劣，第一種操作簡單一點點，但均衡性不如第二種，因為它將結(jié)點p的右子樹
全部移到左邊來了。下面將分別以兩種種思路編寫代碼。


第一種：
btree?*?DelNode(btree?*p)
{
??????if?(p->lchild)
??????{
????????????btree?*r?=?p->lchild;???//r指向其左子樹;
????????while(r->rchild?!=?NULL)//搜索左子樹的最右邊的葉子結(jié)點r
????????{
????????????r?=?r->rchild;
????????}
????????????r->rchild?=?p->rchild;

????????????btree?*q?=?p->lchild;???//q指向其左子樹;
????????????free(p);
????????????return?q;
??????}
??????else
??????{
????????????btree?*q?=?p->rchild;???//q指向其右子樹;
????????????free(p);
????????????return?q;
??????}
}

第二種：
btree?*?DelNode(btree?*p)
{
??????if?(p->lchild)
??????{
????????????btree?*r?=?p->lchild;???//r指向其左子樹;
????????????btree?*prer?=?p->lchild;???//prer指向其左子樹;
????????while(r->rchild?!=?NULL)//搜索左子樹的最右邊的葉子結(jié)點r
????????{
??????????????????prer?=?r;
????????????r?=?r->rchild;
????????}

????????if(prer?!=?r)//若r不是p的左孩子，把r的左孩子作為r的父親的右孩子
????????{
??????????????????prer->rchild?=?r->lchild;
??????????????????r->lchild?=?p->lchild;?//被刪結(jié)點p的左子樹作為r的左子樹
????????????}
????????r->rchild?=?p->rchild;?//被刪結(jié)點p的右子樹作為r的右子樹

????????????free(p);
????????????return?r;
??????}
??????else
??????{
????????????btree?*q?=?p->rchild;???//q指向其右子樹;
????????????free(p);
????????????return?q;
??????}
}
????但是上面這種方法，把r移來移去，很容易出錯，其實在這里我們刪除的只是p的元素值，而不是它的地址，所以完全沒有必要移動指針。仔細觀察，發(fā)現(xiàn)我們刪除的地址實際上是p的左子樹的最右邊的葉子結(jié)點r的地址，所以我們只要把r的數(shù)據(jù)填到p中，然后把r刪除即可。
算法如下：
btree?*?DelNode(btree?*p)
{
??????if?(p->lchild)
??????{
????????????btree?*r?=?p->lchild;???//r指向其左子樹;
????????????btree?*prer?=?p->lchild;???//prer指向其左子樹;
????????while(r->rchild?!=?NULL)//搜索左子樹的最右邊的葉子結(jié)點r
????????{
??????????????????prer?=?r;
????????????r?=?r->rchild;
????????}
????????????p->data?=?r->data;

????????if(prer?!=?r)//若r不是p的左孩子，把r的左孩子作為r的父親的右孩子
??????????????????prer->rchild?=?r->lchild;
????????????else
????????????p->lchild?=?r->lchild;?//否則結(jié)點p的左子樹指向r的左子樹

????????????free(r);
????????????return?p;
??????}
??????else
??????{
????????????btree?*q?=?p->rchild;???//q指向其右子樹;
????????????free(p);
????????????return?q;
??????}
}