一个无序序列可以通过构建一棵二叉排序树,从而变成一个有序序列。
二叉排序树中删除关键字在查找过程中,如果在使用二叉排序树表示的动态查找表中删除某个数据元素时,需要在成功删除该结点的同时,依旧使这棵树为二叉排序树。假设要删除的为结点 p,则对于二叉排序树来说,需要根据结点 p 所在不同的位置作不同的操作,有以下 3 种可能:1、结点 p 为叶子结点,此时只需要删除该结点,并修改其双亲结点的指针即可;2、结点 p 只有左子树或者只有右子树,如果 p 是其双亲节点的左孩子,则直接将 p 节点的左子树或右子树作为其双亲节点的左子树;反之也是如此,如果 p 是其双亲节点的右孩子,则直接将 p 节点的左子树或右子树作为其双亲节点的右子树;3、结点 p 左右子树都有,此时有两种处理方式:1)令结点 p 的左子树为其双亲结点的左子树;结点 p 的右子树为其自身直接前驱结点的右子树,如图 3 所示; 图 3 二叉排序树中删除结点(1) 2)用结点 p 的直接前驱(或直接后继)来代替结点 p,同时在二叉排序树中对其直接前驱(或直接后继)做删除操作。如图 4 为使用直接前驱代替结点 p: 图 4 二叉排序树中删除结点(2)图 4 中,在对左图进行中序遍历时,得到的结点 p 的直接前驱结点为结点 s,所以直接用结点 s 覆盖结点 p,由于结点 s 还有左孩子,根据第 2 条规则,直接将其变为双亲结点的右孩子。
具体实现代码:(可运行)#include#include#define TRUE 1#define FALSE 0#define ElemType int#define KeyType int/* 二叉排序树的节点结构定义 */typedef struct BiTNode{ int data; struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;//二叉排序树查找算法int SearchBST(BiTree T, KeyType key, BiTree f, BiTree *p) { //如果 T 指针为空,说明查找失败,令 p 指针指向查找过程中最后一个叶子结点,并返回查找失败的信息 if (!T) { *p = f; return FALSE; } //如果相等,令 p 指针指向该关键字,并返回查找成功信息 else if (key == T->data) { *p = T; return TRUE; } //如果 key 值比 T 根结点的值小,则查找其左子树;反之,查找其右子树 else if (key < T->data) { return SearchBST(T->lchild, key, T, p); } else { return SearchBST(T->rchild, key, T, p); }}int InsertBST(BiTree *T, ElemType e) { BiTree p = NULL; //如果查找不成功,需做插入操作 if (!SearchBST((*T), e, NULL, &p)) { //初始化插入结点 BiTree s = (BiTree)malloc(sizeof(BiTNode)); s->data = e; s->lchild = s->rchild = NULL; //如果 p 为NULL,说明该二叉排序树为空树,此时插入的结点为整棵树的根结点 if (!p) { *T = s; } //如果 p 不为 NULL,则 p 指向的为查找失败的最后一个叶子结点,只需要通过比较 p 和 e 的值确定 s 到底是 p 的左孩子还是右孩子 else if (e < p->data) { p->lchild = s; } else { p->rchild = s; } return TRUE; } //如果查找成功,不需要做插入操作,插入失败 return FALSE;}//删除函数int Delete(BiTree *p){ BiTree q, s; //情况 1,结点 p 本身为叶子结点,直接删除即可 if (!(*p)->lchild && !(*p)->rchild) { *p = NULL; } else if (!(*p)->lchild) { //左子树为空,只需用结点 p 的右子树根结点代替结点 p 即可; q = *p; *p = (*p)->rchild; free(q); } else if (!(*p)->rchild) {//右子树为空,只需用结点 p 的左子树根结点代替结点 p 即可; q = *p; *p = (*p)->lchild;//这里不是指针 *p 指向左子树,而是将左子树存储的结点的地址赋值给指针变量 p free(q); } else {//左右子树均不为空,采用第 2 种方式 q = *p; s = (*p)->lchild; //遍历,找到结点 p 的直接前驱 while (s->rchild) { q = s; s = s->rchild; } //直接改变结点 p 的值 (*p)->data = s->data; //判断结点 p 的左子树 s 是否有右子树,分为两种情况讨论 if (q != *p) { q->rchild = s->lchild;//若有,则在删除直接前驱结点的同时,令前驱的左孩子结点改为 q 指向结点的孩子结点 } else { q->lchild = s->lchild;//否则,直接将左子树上移即可 } free(s); } return TRUE;}int DeleteBST(BiTree *T, int key){ if (!(*T)) {//不存在关键字等于key的数据元素 return FALSE; } else { if (key == (*T)->data) { Delete(T); return TRUE; } else if (key < (*T)->data) { //使用递归的方式 return DeleteBST(&(*T)->lchild, key); } else { return DeleteBST(&(*T)->rchild, key); } }}void order(BiTree t)//中序输出{ if (t == NULL) { return; } order(t->lchild); printf("%d ", t->data); order(t->rchild);}int main(){ int i; int a[5] = { 3,4,2,5,9 }; BiTree T = NULL; for (i = 0; i < 5; i++) { InsertBST(&T, a[i]); } printf("中序遍历二叉排序树: "); order(T); printf(" "); printf("删除3后,中序遍历二叉排序树: "); DeleteBST(&T, 3); order(T);}运行结果:中序遍历二叉排序树:2 3 4 5 9删除3后,中序遍历二叉排序树:2 4 5 9总结使用二叉排序树在查找表中做查找操作的时间复杂度同建立的二叉树本身的结构有关。即使查找表中各数据元素完全相同,但是不同的排列顺序,构建出的二叉排序树大不相同。例如:查找表 {45,24,53,12,37,93} 和表 {12,24,37,45,53,93} 各自构建的二叉排序树图下图所示:图 5 不同构造的二叉排序树使用二叉排序树实现动态查找操作的过程,实际上就是从二叉排序树的根结点到查找元素结点的过程,所以时间复杂度同被查找元素所在的树的深度(层次数)有关。为了弥补二叉排序树构造时产生如图 5 右侧所示的影响算法效率的因素,需要对二叉排序树做“平衡化”处理,使其成为一棵平衡二叉树。平衡二叉树是动态查找表的另一种实现方式,下一节做重点介绍。