数据结构和算法——二叉排序树
一、二叉排序树
对于无序的序列“62，58，88，47，73，99，35，51，93，29，37，49，56，36，48，50”，是否存在一种高效的查找方案，使得能够快速判断在序列中是否存在指定的数值？二叉排序树是一种简单，高效的数据结构。
二叉排序树，又称为二叉查找树。二叉排序树或者是一棵空树，或者是具有以下性质的二叉树：若其左子树不为空，则左子树上的所有节点的值均小于它的根结点的值；若其右子树不为空，则右子树上的所有节点的值均大于它的根结点的值；左右子树又分别是二叉排序树。
对于以上的序列，我们构建如下的二叉排序树，其左子树小于根结点的值，右子树大于根结点的值：
二、二叉排序树的基本操作
二叉排序树的结构为：
typedef struct tree_node{
double value;
struct tree_node *left;
struct tree_node *right;
}*node, binode;在二叉排序树中，其最主要的特点是其左子树小于其根结点的值，右子树大于根结点的值。
1、查找
二叉排序树的查找是指在二叉排序树中查找到对应的值，如在上述的二叉排序树中查找“49”，其具体过程为：
- 与根结点的值相比：49<52，查找其左子树
- 49<58，查找其左子树
- 49>47，查找其右子树
- 49<51，查找其左子树
- 49=49，查找成功
其具体过程如下图所示：
其具体实现过程为：
int search_value(node root, double a, node *p){
if (NULL == root) {
return 1; // 查找不成功
}
else if (a == root->value) {
return 0; // 树中已经存在该节点
}else if (a < root->value) {
*p = root; // 记录父节点
return search_value(root->left, a, p); //查找左子树
}else {
*p = root;
return search_value(root->right, a, p); // 查找右子树
}
}2、插入
对于插入操作，主要分为两种情况：
- 若二叉排序树中存在该值，则不做任何操作
- 若二叉排序树中不存在该值，则插入
插入的具体操作是判断与二叉排序树中节点的值，若小于当前节点的值，则选择左子树插入，若大于当前节点的值，则选择右子树插入；对于左右子树，进行同样的操作。
其实现过程为：
int insert_tree(node *root, double a){
node p = *root;
node q = NULL;
printf("insert: %lf\n", a);
if (search_value(*root, a, &p) == 1) { // 查找树中是否存在a
q = (binode *)malloc(sizeof(binode)); // 不存在a，申请空间
q->value = a;
q->left = q->right = NULL;
if (*root == NULL){ // 树为空
*root = q;
}else {
if (a < p->value){
p->left = q; // 插入左子树
}else{
p->right = q; // 插入右子树
}
}
return 0;
}
return 1;
}3、删除
二叉排序树中节点的删除操作相比其他的操作就比较复杂一点，首先，通过查找二叉排序树中是否存在节点，若存在，主要分为如下的三种情况：
- 节点既无左子树，又无右子树
删除的方法：设置父节点指向该节点的指针为空，直接删除该节点。如删除值为“50”的节点：
- 若删除的节点只包含左子树或者只包含右子树
删除的方法：删除该节点，以其左子树或者右子树代替该节点。如删除值为“58”的节点：
- 若删除的节点既包含左子树，又包含右子树
删除的方法：
- 找到待删除的节点，选择其左子树中的最大的节点或者其右子树中最小的节点，这里选择左子树中最大的节点，以删除值为“47”的节点为例：
- 在左子树中找到最大的节点，根据二叉排序树的特点，值最大的节点要么是根结点（无右子树），要么是最右的节点，在这里，其左子树中最大的节点为“37”，以该节点替换需要删除的节点，即以“37”替换节点“47”，再将该节点的左子树作为其父节点的右子树，即将“36”作为“35”的右子树：
其具体的过程为：
int delete_node(node *root, double a){
// 判断树中书否存在a
node p = *root;
if (search_value(*root, a, &p) == 0){// 存在该节点
// 开始删除,p指向的删除节点的父节点
node q = NULL;// q指向要删除的节点
if (a < p->value){
q = p->left;
}else{
q = p->right;
}
if (q->left == NULL && q->right == NULL){ //叶子节点，直接删除
if (a < p->value) p->left = NULL;
else p->right = NULL;
}else if ((q->left == NULL && q->right != NULL) || (q->left != NULL && q->right == NULL)){
// 只有左子树或者只有右子树
node r = (q->left == NULL ? q->right : q->left); // 指向q不为空的子树
if (a < p->value) p->left = r;
else p->right = r;
}else{ // 既有左子树又有右子树
// 这里选择左子树最大的节点作为父节点
node r = q->left;
// 判断r的右子树是否为空
if (r->right == NULL){ // 右子树为空
p->left = r;
r->right = q->right;
}else{ // 右子树不为空
node r1 = r;
node r1_father = r;
// 寻找最右子树
while (r1->right != NULL){
r1_father = r1;
r1 = r1->right;
}
// 此时r1不可能存在右子树
r1_father->right = r1->left;
r1->left = r;
r1->right = q->right;
p->left = r1;
}
}
free(q);
q = NULL;
return 0;
}
return 1;
}4、中序遍历
对于二叉排序树，其中序遍历的输出结果正好是排好序的序列，其中序
void in_order(node root){
node p = root;
if (p != NULL){
in_order(p->left);
fprintf(stderr, "%lf\n", p->value);
in_order(p->right);
}
}对于上述的序列“62，58，88，47，73，99，35，51，93，29，37，49，56，36，48，50”其中序遍历的结果为：
删除“47”后的中序遍历的结果为：
参考文献
- 《大话数据结构》
- 《数据结构》(C语言版)
腾讯云开发者
