一、定义
二叉排序树
二叉排序树(Binary Sort Tree)又称为二叉查找树，它或者是一颗空树，或者是具有下列性质的二叉树:
- 若它的左子树不为空，则左子树上所有结点的值均小于它的根结构的值；
- 若它的右子树不为空，则右子树上所有结点的值均大于它的根结构的值；
- 它的左、右子树也分别为二叉排序树(递归)
中序遍历二叉排序树可以得到一个有序的列表
二、二叉排序树的算法实现
定义和普通二叉树的算法相同
typedef enum Status{
success = 0,//成功
fail = 1//失败
}Status;
//二叉树结点定义
typedef struct SearchBinaryTreeNode{
int data;
struct SearchBinaryTreeNode *lChild,*rChild;
}SearchBinaryTreeNode,*SearchBinaryTree;
1.查找算法
/// 查找二叉排序树上的值为key的结点
/// @param T 二叉树的根节点
/// @param key 搜索的值
/// @param f 指向最终查找出来结点的双亲，一开始为NULL，也就是指向二叉树根节点的双亲，当然为NULL
/// @param p 查找成功则返回查找到的结点，并return success，否则指向查找路径上最后访问的结点，并返回fail
Status searchBst(SearchBinaryTree T,int key,SearchBinaryTree f,SearchBinaryTree *p){
if (!T) {
//查找不成功
*p = f;
return fail;
} else if (key == T->data){
//查找成功
*p = T;
return success;
} else if (key < T->data){
//在左子树查找 递归
searchBst(T->lChild, key, T, p);
} else if (key > T->data){
//在右子树查找 递归
searchBst(T->rChild, key, T, p);
}
return fail;
}
2.插入算法(也可以作为生成算法)
/// 插入操作 这个也可以作为二叉排序树的生成算法
/// @param T 二叉树的根节点
/// @param key 插入key并返回success，否则返回fail
Status insertBst(SearchBinaryTree *T,int key){
SearchBinaryTree p,s;
if (searchBst(*T, key, NULL, &p) == fail) {
//如果找不到，那么执行插入
s = (SearchBinaryTree)malloc(sizeof(SearchBinaryTreeNode));
s->data = key;
s->lChild = s->rChild = NULL;
if (!p) {
//在根节点就被打回来了，这时候才可能为NULL，那就是树是一颗空树
//直接让s成为根节点
*T = s;
} else if (key < p->data){
//如果是比p->data小，那么把它放到p的左子树
p->lChild = s;
} else if (key > p->data){
//如果是比p->data大，那么把它放到p的右子树
p->rChild = s;
}
return success;
} else {
//已经有了key相同值的结点，不用再插入，
return fail;
}
}
3.删除算法
删除算法是其中最复杂的，它分为多种情况：
(1) 如果删除的是叶子结点，那么直接将叶子结点删除，并将叶子的双亲结点的左子树或者右子树指向为空即可
(2) 如果删除的是结点只有左子树或者右子树，那么我们也将左子树或者右子树接到双亲结点即可
(3) 如果删除的结点既有左子树也有右子树，这时候我们删除后就复杂多了。我们知道，二叉排序树经过中序遍历后得到的是一个有序序列，那我们可以取它的直接前驱后者直接后继就可以替换到这个位置，删除的结点是直接前驱或直接后继。在二叉排序树中，要删除结点的左子树的最右子树就是这个结点的直接前驱，而结点的右子树的最左子树就是这个结点的直接后继。
Status deleteNode(SearchBinaryTree *node);
Status deleteBst(SearchBinaryTree *T,int key){
if (!*T) {
//空树，直接返回fail
return fail;
}
if (key == (*T)->data) {
//找到了，就删除掉
return deleteNode(T);
} else if (key < (*T)->data){
//比值小，从左子树上去找出来删
return deleteBst(&((*T)->lChild), key);
} else if (key > (*T)->data){
//比值大，从右子树上去找出来删除
return deleteBst(&((*T)->rChild), key);
}
return fail;
}
Status deleteNode(SearchBinaryTree *node){
//q用来标识待删除的结点的双亲结点，s用来标识每一次迭代用到的结点
SearchBinaryTree q,s;
if ((*node)->rChild == NULL) {
//右子树为空，也就是只有左子树，那么把左子树接到node结点的双亲结点上就好了
q = *node;
//这一步直接把node指针存储的值存放q的左子树的地址，也就是接上去
*node = q->lChild;
//释放结点
free(q);
} else if ((*node)->lChild == NULL){
//左子树为空，也就是只有右子树，那么把右子树接到node结点的双亲结点上就好了
q = *node;
//这一步直接把node指针存储的值存放q的右子树的地址，也就是接上去
*node = q->rChild;
free(q);
} else {
//左右子树都不为空，那么我们可以用直接前驱或者直接后继来替代该结点所在的位置
q = *node;
//下面取直接前驱或者直接后继，直接取一个就可以了
//一、直接前驱法
s = (*node)->lChild;
//直接前驱就是s最右的子树
while (s->rChild != NULL) {
q = s;
s = s->rChild;
}
//找到了直接前驱
//将数据替换过去
(*node)->data = s->data;
if (q != *node) {
//不相等，也就是至少进行一次遍历，那么直接把s->lChild接过来（因为s肯定没有右子树的）
q->rChild = s->lChild;
} else {
//找到的直接就是原有结点的左子树(因为q->lChild没有右子树，没有进行遍历)
//那么把s的左子树接到结点的左子树上
q->lChild = s->lChild;
}
//释放s结点
free(s);
//二、直接后继法
q = *node;
s = (*node)->rChild;
//直接前驱就是s最左的子树
while (s->lChild != NULL) {
q = s;
s = s->lChild;
}
//替换数据
(*node)->data = s->data;
if (q != *node) {
//不相等，至少进行了一次遍历
//那么把s的右子树接过来
q->lChild = s->rChild;
} else {
//相等，就是没有进行过遍历
//那么把s的右子树接到q的右子树上
q->rChild = s->rChild;
}
free(s);
}
return success;
}
网友评论