这篇文章上次修改于 198 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
前言
我们的线性表有2种，无序线性表和有序线性表。
无序线性表正如其名，它里面的数据是无序的，因为这个表不用维护什么东西，所有它的插入和删除操作的效率也不错。。但是，正因为他是无序的，查找起来就很废时间。。
如果我们的线性表是有序的，并且是顺序存储的，查找就可以用折半、插值、斐波那契等查找算法进行查找，但是正因为要维护它的有序性，插入和删除就需要耗费大量的时间。
那么我们有没有一种数据结构，可以使得插入和删除效率不错，又可以比较高效率的实现查找算法呢？还真有。
他就是我们现在要介绍的二叉排序树。
定义
二叉排序树，又叫做二叉搜索树，它或是一颗空树又或是具有以下性质的二叉树。
- 如果它的左子树不空，则左子树上所有节点的值均小于它的根节点的值
- 如果它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
- 它的左、右子树也分别为二叉排序树。
这样子讲可能大家不明白，我们来举个例子吧。
假如我们要往一个二叉排序树里插入[8, 3, 1, 6, 10, 4, 14, 7, 13]
结果是什么呢？它长这样子：
首先8入树，因为现在树是一个空树，所有作为根节点。
然后3入树，因为 3 < 8，根据二叉排序树的定义，作为节点8的左子树
然后1入树，因为 1 < 8，到了节点3，又因为 1 < 3，所以作为节点3的左子树
然后6入树，因为 6 < 8，到了节点3，又因为 6 > 3，所以作为节点3的右子树
然后10入树，因为 10 > 8，根据二叉排序树的定义，作为节点8的右子树
然后4入树，因为 4 < 8，到了节点3，又因为 4 > 3，到了节点6，再因为 4 < 6，所以4就成了节点6的左子树
然后14入树，因为 14 > 8，到了节点10，又因为 14 > 10，所以作为节点14的右子树
然后7入树，因为 7 < 8，到了节点3，又因为 7 > 3，到了节点6，再因为7 > 6，所以作为节点6的右子树
最后13入树，因为 13 > 8，到了节点10，又因为 13 > 10，到了节点14，再因为13 < 14，所以作为节点14的左子树了
实现
我们先定义一个二叉树的二叉链表节点结构体
typedef struct BiTNode { // 节点结构
int data; // 节点数据
struct BiTNode *lchild, *rchild; // 节点左右孩子
} BiTNode, *BiTree;然后我们来看看查找怎么实现
/**
* 递归查找二叉排序中是否存在Key
* 指针f指向T的双亲，其调用初始值为NULL
* 如果查找成功，则指针p指向该数据元素节点，并返回TRUE
* 否则指针p指向查找路径上最后一个节点，并返回FLASE
**/
int search(BiTree T, int key, BiTree f, BiTree *p) {
if (!T) { // 如果传入的节点是空的，返回FLASE
*p = f;
return 0;
} else if (key == T -> data) { // 如果查找的key等于当前节点的值，返回TRUE
*p = T;
return 1;
} else if (key < T -> data) // 如果key小于当前节点的值，根据定义查找该节点的左子树
return search(T -> lchild, key, T, p);
else // 反之该节点的右子树
return search(T -> rchild, key, T, p);
}这些代码就不需要我解释了吧，我注释都写的很详细了。。。
然后是插入
/**
* 向节点添加值
* 当节点不存在Key时插入并返回TURE，反之返回FLASE
**/
int insert(BiTree *T, int key) {
BiTree p, s;
if (!search(*T, key, NULL, &p)) { // 如果该值在树中不存在
s = (BiTree) malloc(sizeof(BiTNode)); // 新建一个节点
s -> data = key; // 将key分配给新建的节点
s -> lchild = s -> rchild = NULL; // 初始化新建节点的左、右子树
if (!p) // 如果符合条件的节点不存在
*T = s; // 插入s为新的根节点
else if (key < p -> data) // 如果key小于查找路径尾的节点的值
p -> lchild = s; // 根据定义，将新建节点赋值给p的左子树
else
p -> rchild = s; // 否则将新建节点赋值给p的右子树
return 1; // 因为插入成功，所以返回TRUE
}
else
return 0; // 因为存在，无法插入所以返回FALSE
}最后就是这里最难的部分了，二叉排序树的删除操作。
删除呢，我们要分多种情况来定，
第一种情况是要删除的节点是叶子节点，这就很容易，直接删除就好了。。
第二种情况呢，是要删除的节点只有左或右子树，这种情况也很简单，把要删除的节点删除后再把她的左或右子树整个移动到被删除节点的位置就可以了，整个结构还是一个二叉排序树。
第三种就比较麻烦了，被删除的节点既有左子树又有右子树，我们有什么办法可以解决它呢？
用左或者右子树选一个来代替它，然后其他重新插入？？
这样子效率就太低了。。我们有没有什么更好的解决办法呢？
仔细想想，我们能不能在被删除的节点的左、右子树中找出一个节点来代替它呢？当然可以，但是选什么好呢？？？
我这里就直接说答案吧，选取与被删除节点的值最接近的2个节点，比较好的办法就是选取被删除节点的直接前继或者直接后继S，用S来代替节点p，然后再把S删除就好了。。代码如下：
/**
* 删除节点p，并重接它的左或右子树
**/
int deleteNode(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;
while (s -> rchild) { // 找到待删除节点的直接前驱
q = s;
s = s -> rchild;
}
(*p) -> data = s -> data; // s 指向被删节点的直接前驱
if (q != *p)
q -> rchild = s -> lchild; // 重接 q 的右子树
else
q -> lchild = s -> lchild; // 重接 q 的左子树
}
return 1;
}
/**
* 如果树T内存在值等于key的节点时，删除该节点并返回TRUE，否则返回FLASE
**/
int delete(BiTree *T, int key) {
if (!*T) // 不存在值等于key的节点
return 0;
else {
if (key == (*T) -> data) // 找到值等于key的节点
return deleteNode(T);
else if (key < (*T) -> data)
return delete(&(*T) -> lchild, key);
else
return delete(&(*T) -> rchild, key);
}
}全部代码
#include <stdlib.h>
// 二叉树的二叉链表节点结构体
typedef struct BiTNode { // 节点结构
int data; // 节点数据
struct BiTNode *lchild, *rchild; // 节点左右孩子
} BiTNode, *BiTree;
/**
* 递归查找二叉排序中是否存在Key
* 指针f指向T的双亲，其调用初始值为NULL
* 如果查找成功，则指针p指向该数据元素节点，并返回TRUE
* 否则指针p指向查找路径上最后一个节点，并返回FLASE
**/
int search(BiTree T, int key, BiTree f, BiTree *p) {
if (!T) { // 如果传入的节点是空的，返回FLASE
*p = f;
return 0;
} else if (key == T -> data) { // 如果查找的key等于当前节点的值，返回TRUE
*p = T;
return 1;
} else if (key < T -> data) // 如果key小于当前节点的值，根据定义查找该节点的左子树
return search(T -> lchild, key, T, p);
else // 反之该节点的右子树
return search(T -> rchild, key, T, p);
}
/**
* 向节点添加值
* 当节点不存在Key时插入并返回TURE，反之返回FLASE
**/
int insert(BiTree *T, int key) {
BiTree p, s;
if (!search(*T, key, NULL, &p)) { // 如果该值在树中不存在
s = (BiTree) malloc(sizeof(BiTNode)); // 新建一个节点
s -> data = key; // 将key分配给新建的节点
s -> lchild = s -> rchild = NULL; // 初始化新建节点的左、右子树
if (!p) // 如果符合条件的节点不存在
*T = s; // 插入s为新的根节点
else if (key < p -> data) // 如果key小于查找路径尾的节点的值
p -> lchild = s; // 根据定义，将新建节点赋值给p的左子树
else
p -> rchild = s; // 否则将新建节点赋值给p的右子树
return 1; // 因为插入成功，所以返回TRUE
}
else
return 0; // 因为存在，无法插入所以返回FALSE
}
/**
* 删除节点p，并重接它的左或右子树
**/
int deleteNode(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;
while (s -> rchild) { // 找到待删除节点的直接前驱
q = s;
s = s -> rchild;
}
(*p) -> data = s -> data; // s 指向被删节点的直接前驱
if (q != *p)
q -> rchild = s -> lchild; // 重接 q 的右子树
else
q -> lchild = s -> lchild; // 重接 q 的左子树
}
return 1;
}
/**
* 如果树T内存在值等于key的节点时，删除该节点并返回TRUE，否则返回FLASE
**/
int delete(BiTree *T, int key) {
if (!*T) // 不存在值等于key的节点
return 0;
else {
if (key == (*T) -> data) // 找到值等于key的节点
return deleteNode(T);
else if (key < (*T) -> data)
return delete(&(*T) -> lchild, key);
else
return delete(&(*T) -> rchild, key);
}
}
没有评论