第七章 查找 五、二叉排序树

目录

一、定义

二、代码实现

1、查找

2、插入

3、构造

4、删除

三、查找效率分析

1、查找成功ASL

2、查找失败ASL

四、总结

---

一、定义

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下条件：

1. 若左子树不为空，则左子树上所有节点的值（权值）均小于它的根节点的值；

2. 若右子树不为空，则右子树上所有节点的值（权值）均大于它的根节点的值；

3. 左、右子树本身也分别为二叉排序树。

二叉排序树的结构可以在查找、插入、删除操作中发挥重要作用，具有快速查找、插入、删除的特点。

二、代码实现

可以使用Binary Search Tree Visualization进行模拟测试。

1、查找

typedef struct TreeNode{
    int data;
    struct TreeNode *lchild,*rchild;
}TreeNode,*BTree;
 
TreeNode *BST_Search(BTree T,int e){
    while(T!=NULL&&e!=T->data){
        if (e>T->data){//大于
            T = T->rchild;
        } else{//小于
            T = T->lchild;
        }
    }
    return T;
}

2、插入

//递归
int BST_Insert(BTree &T,int k){
    if (T==NULL){
        T=(BTree) malloc(sizeof(TreeNode));
        T->data=k;
        T->lchild=T->rchild=NULL;
        return 1;//插入成功
    } else if (k==T->data){
        return 0;//已存在该值，插入失败
    }
    else if (kdata){
        return (BST_Insert(T->lchild,k));//小于，插入左子树
    } else{
        return (BST_Insert(T->rchild,k));//大于，插入右子树
    }
}
 
 
//非递归
int BST_Insert1(BTree &T,int k){
    while(T!=NULL){
        if (T->data == k){//存在该值
            return 0;
        }else if (T->data < k){//小于
            if (T->lchild != NULL){//小于且不为叶子节点
                T=T->lchild;
            } else{//小于且为叶子节点
                T->data=k;
                T->lchild=T->rchild=NULL;
            }
        } else{//大于
            if (T->rchild != NULL){//大于且不为叶子节点
                T=T->rchild;
            } else{//大于且为叶子节点
                T->data=k;
                T->lchild=T->rchild=NULL;
            }
        }
    }
}

3、构造

void Creat_Tree(BTree &T,int str[],int n){
    T=NULL;
    int i = 0;
    while(i
        BST_Insert(T,str[i]);
        i++;
    }
}

4、删除

我们寻找代替被删除位置的结点时，有两种方案。

一种是找左子树中最大的值。（中序遍历最后访问的结点）

二是找右子树中最小的值。（中序遍历最先访问的结点）

三、查找效率分析

1、查找成功ASL

在上图中，

第一层的结点要查询一次；

第二层的结点要对比两次；

第三层的结点要对比三次；

第四层的结点要对比四次；

在乘以每层结点的个数，取平均值，就得到了查找成功的ASL；

2、查找失败ASL

在上图中，

查找失败要对比三次的失败节点有7个；

查找失败要对比两次的失败节点有2个；

所以ASL为它们的平均值。

四、总结