《二叉排序树的删除.docx》由会员分享，可在线阅读，更多相关《二叉排序树的删除.docx（3页珍藏版）》请在三一文库上搜索。
1、二叉排序树的删除对于一般的二叉树来说，删去树中的一个结点是没有意义的，因为它将使以被删除的结点为根的子树变成森林，破坏了整棵树的结构但是，对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点后不改变二叉排序树的特性即可。在二叉排序树上删除一个结点的算法如下：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);elseb
2、->rchild = DeleteBST(b->rchild, x);return b;其中删除过程有两种方法。第一种过程如下：1。 若p有左子树，找到其左子树的最右边的叶子结点r,用该叶子结点r来替代p ,把r的左孩子作为r的父亲的右孩子。2。若p没有左子树，直接用 p的右孩子取代它。第二种过程如下：1。 若p有左子树，用p的左孩子取代它；找到其左子树的最右边的叶子结点r,把p的右子树作为r的右子树。2。若p没有左子树，直接用 p的右孩子取代它。两种方法各有优劣，第一种操作简单一点点，但均衡性不如第二种，因为它将结点p的右子树全部移到左边来了。下面将分别以两种种思路编写代码。第一
3、种:btree * DelNode(btree *p)(if (p->lchild)(指向其左子树；搜索左子树的最右边的叶子结点r指向其左子树；btree *r = p->lchild; /r while(r->rchild != NULL)/ (r = r->rchild;r->rchild = p->rchild;btree *q = p->lchild; /q free(p);return q;else(指向其右子树指向其左子树；指向其左子树；搜索左子树的最右边的叶子结点btree *q = p->rchild; /q free(p);re
4、turn q;第二种：btree * DelNode(btree *p)(if (p->lchild)(btree *r = p->lchild; /rbtree *prer = p->lchild; /prer while(r->rchild != NULL)/ (prer = r;r = r->rchild; if(prer != r)/ 若r不是p的左孩子，把r的左孩子作为r的父亲的右孩子 (prer->rchild = r->lchild;r->lchild = p->lchild; /被删结点p的左子树作为r的左子树r->r
5、child = p->rchild; /被删结点p的右子树作为 r的右子树free(p);return r;else(btree *q = p->rchild; /q指向其右子树；free(p);return q;但是上面这种方法，把 r移来移去，很容易出错，其实在这里我们删除的只是p的元素值，而不是它的地址，所以完全没有必要移动指针。仔细观察，发现我们删除的地址实际上是p的左子树的最右边的叶子结点r的地址,所以我们只要把r的数据填到p中，然后把r删除即可。算法如下：btree * DelNode(btree *p)(if (p->lchild)(btree *r = p-&
6、gt;lchild; /r指向其左子树；btree *prer = p->lchild; /prer指向其左子树 ;while(r->rchild != NULL)/搜索左子树的最右边的叶子结点r(prer = r;r = r->rchild;p->data = r->data;if(prer != r)/ 若r不是p的左孩子，把r的左孩子作为r的父亲的右孩子 prer->rchild = r->lchild;elsep->lchild = r->lchild; /否则结点p的左子树指向 r的左子树free(r);return p;elsebtree *q = p->rchild; /q指向其右子树；free(p);return q;