首页 > 其他分享 >[数据结构] 二叉搜索树 (二叉排序树)

[数据结构] 二叉搜索树 (二叉排序树)

时间:2023-02-09 23:55:18浏览次数:56  
标签:排序 删除 val 二叉 leftchild 数据结构 root 节点

二叉搜索树

二叉搜索树的基本概念

二叉搜索树( Binary Search Tree )也称二叉排序树,是一种各节点值之间存在一定次序关系的二叉树。

二叉搜索树的特点

一般情况下,二叉搜索树中所有节点值是不重复的。
对于二叉搜索树中的每个节点:
(1)如果其左子树不为空,那么其左边的节点值都比当前节点值小;
(2)如果其右子树不为空,那么其右边的节点值都比当前的节点值要大。

二叉搜索树的中序遍历结果,就是所有节点值升序排序的结果。



二叉搜索树的查找

二叉搜索树查找的基本步骤

根据二叉搜索树的特点,其实二叉搜索树中的查找和二分查找非常相似。从树的根节点出发,当前节点值 val 如果等于目标值 target,那么就直接返回;如果 val 小于目标值 target,那么就要往左边去寻找;如果 val 大于目标值 target,那么就要往右边去寻找。假如最后节点为 NULL,都没有找到等于目标值的节点,那么说明此时的二叉搜索树中不存在这个等与目标值 target 的节点。

我们将使用递归函数来实现这一过程,假设函数名为 SearchBST,则大致步骤为:
(1)节点为空,没有等于目标值的节点 if(!root) return NULL
(2)当前节点值小于目标值 if(root->val < target) return SearchBST(root->left)
(3)当前节点值大于目标值 if(root->val > target) return SearchBST(root->right)
(4)找到该节点 return root

二叉搜索树查找图解

(1)

(2)

(3)

(4)

二叉搜索树查找代码

//递归 查找二叉排序树指定元素target
BinaryTree Search_BST(BinaryTree root, Elemtype target){
    if(!root)                                     //最后没有找到root为NULL
        return NULL;          
    if(target > root->val)                        //root值小于target 往其右子树查找
        return Search_BST(root->rightchild, target);
    if(target < root->val)                        //root值大于target 往其左子树查找
        return Search_BST(root->leftchild, target);
    return root;                                  //找到直接返回该节点
}


二叉搜索树的插入

二叉搜索树插入的基本步骤

二叉搜索树插入的元素,首先一定是当前二叉搜索树中不存在的元素,如果要插入的元素 val 已经存在于二叉搜索树中,那么就没有插入的必要了。

二叉搜索树插入新元素,同时还需要使整棵树保持二叉搜索树的性质。所以在插入过程中,我们依旧需要用类似于二分查找的形式来实现插入的操作。从树的根节点出发,如果当前节点为空,说明可以插入到这个位置;如果插入元素 val 与当前节点值相等,说明已经存在,直接 return;如果插入元素 val 小于当前节点值,那么递归往左寻找合适的插入位置;如果插入元素 val 大于当前节点值,那么递归往右寻找合适的插入位置。

我们还是用递归函数来实现这个插入的过程,也是创建二叉搜索树的过程。
假定函数名为 InsertBST ,则大致步骤为:
(1)当前节点位置为空,可以插入,创建一个新节点 root = new Node(val)
(2)当前节点值与插入元素值相等,直接 return
(3)插入元素 val 小于当前节点值,则进行 InsertBST(root->left, val)
(4)插入元素 val 大于当前节点值,则进行 InsertBST(root->right, val)

二叉搜索树插入图解

(1)

(2)

二叉搜索树插入代码

//二叉排序树元素的插入
void Insert_BST(BinaryTree &root, Elemtype val){
    if(!root){                           //若为当前root为空
        BinaryTree node = (BinaryTree)malloc(sizeof(BiNode));
        node->val = val;
        node->leftchild = node->rightchild = NULL;
        root = node;
        return;
    } 
    if(root->val == val) 
        return;                          //当前值已经存在 则不插入

/*                       递归写法                        */	 
    if(root->val > val)
        Insert_BST(root->leftchild, val);
    else
        Insert_BST(root->rightchild, val);
}	


二叉搜索树的删除

第一类删除的情况

删除节点为叶子结点

基本步骤

由于删除节点为叶子结点,直接置 NULL 即可,删除完之后不会对整棵树满足二叉搜索树性质产生任何影响。

图解

第二类删除的情况

这一类删除的节点的特点为其只有一个子树,另一个子树为空。这种情况往往也是比较方便处理的。

(1)删除节点只有右子树

当删除节点只有右子树时,为了维持二叉搜索树的特点,只需要将删除节点的右子树继承给其父节点就可以,并且做到了将该节点删除。

基本步骤

假定 root 为当前要删除的节点,直接 root = root->right

图解

(2)删除节点只有左子树

当删除节点只有左子树时,为了维持二叉搜索树的特点,和上一种情况也类似,将左子树继承给其父节点。

基本步骤

假定 root 为当前要删除的节点,直接 root = root->left

图解

第三类删除的情况

这一类删除的节点同时含有左子树和右子树,此时的处理是比较麻烦的,但是整理好思路就不难。

本质上,我们要找到当前删除的节点的右子树中的节点值最小的节点,也就是右边第一个大于当前删除节点的节点。我们用 s 来指向这个节点,后期我们将其作为代替当前删除的节点。

但是,s 情况的不同也会导致一些处理上的区别。

(1)右子树根节点为右边的最小节点

s 指向的是右子树中的最小的节点,如果右子树的左子树为空,也就是说右子树的根节点即右子树中最小的节点。那么此时 s 就指向这个右子树根节点,然后只需要将删除节点 root 的左子树继承给 sleft ,最后将 s 代替删除节点 root 就可以了。这样就可以保持二叉搜索树的性质。

基本步骤

(1)此时 s 就指向 root->right
(2)将 root->left 继承给 s->left
(3)s 代替删除节点, root = s

图解

(2)最后一种情况

基本步骤

s 指向的是右子树中的最小的节点,假如右子树的左子树不为空,那么我们首先要先一直向左搜索,直到右子树的最左边,即找到最左边的节点。而且这个最左边的节点一定是没有左子树的,但是可能存在右子树。为了能够顺利的让 s 代替删除节点 root,根据 s 一定是其父节点的左子树的特点,我们需要先将 s 的右子树继承给其父节点 parent,然后此时的 s 就形成一个单独的节点。最后将删除节点 root->left 赋给 s 的左子树,将 root->right 赋给 s 的右子树,将 root = s 完成代替操作。

为了将 s 的右子树继承给其父节点 parent,在右子树中一直往左寻找最左边的节点时,我们需要定义 parent 来记录其父节点。

(1)在删除节点 root 的右子树中一直往左搜索,找到最左边的节点 s
(2)将 s 的右子树继承给 parentparent->left = s->right
(3)将 root 的左右子树继承给 ss->left = root->left, s->right = root->right
(4)最后 root = s

图解

二叉搜索树删除代码

//二叉排序树元素的删除  
void Delete_BST(BinaryTree &root, Elemtype val){
    BinaryTree t = root, parent = NULL, s = NULL;

    if(!t){  //要删除节点不存在
        puts("要删除的节点不存在");
        return;
    }

    //当前的root为要删除的节点
    if(t->val == val){
        if(!t->leftchild && !t->rightchild){      //要删除的节点是一个叶子结点 直接置NULL
            root = NULL;
        }
        else if(!t->leftchild && t->rightchild){  //要删除的节点只有右子树,将其右子树的根节点代替删除节点
            root = t->rightchild;
        }
        else if(t->leftchild && !t->rightchild){  //要删除的节点只有左子树,将其左子树的根节点代替删除节点
            root = t->leftchild;
        }

        /*  **个人认为最难的地方 采用迭代法**  */
        else{                                     //要删除的节点既有左子树,又有右子树
            s = t->rightchild;                    //记录删除节点的右子树根节点
            //找到右子树中最小的节点
            if(!s->leftchild){                    //如果此时的s没有左儿子,直接把删除节点的左子树变为此时s(删除节点右儿子)的左子树
                s->leftchild = t->leftchild;
            }else{
                while(s->leftchild){              //找到删除节点的右子树中最左边的节点s 即第一个大于删除节点值的节点(后期将其代替删除节点的位置)
                    parent = s;                   //记录代替位置节点的父节点
                    s = s->leftchild;
                }

                parent->leftchild = s->rightchild;//若代替位置节点有右子树,把其右子树继承给父节点(重构删除节点的右子树)
                s->leftchild = t->leftchild;      //删除节点的左子树变为代替节点的左子树
                s->rightchild = t->rightchild;    //删除节点的右子树变为代替节点的右子树
            }

            root = s;                             //最后将当前s代替要删除的节点
        }

        free(t);
    }   
    else if(val > t->val){
        Delete_BST(t->rightchild, val);           //向其右子树寻找要删除的节点
    }
    else if(val < t->val){
        Delete_BST(t->leftchild, val);            //向其左子树寻找要删除的节点
    }
}


二叉搜索树的平均查找度

基本概念

ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数称为平均查找长度。

查找成功情况下的AVL

计算公式

其中 i 表示当前层级,numi 表示第 i 层的节点个数,nodesum 表示整颗二叉搜索树的节点个数。

图解

计算二叉树节点个数代码

//计算二叉树节点的个数
int Nodenum_of_BST(BinaryTree root){
    if(!root)
        return 0;
    return Nodenum_of_BST(root->leftchild) + Nodenum_of_BST(root->rightchild) + 1;
}

查找失败情况下的AVL

计算公式

其中 i 表示当前层级,supplei 表示第 i 层的要补全的节点个数,supplesum 表示整颗二叉搜索树的要补全的总节点个数。

图解

利用层次遍历求补全节点

double sum1 = 0, sum2 = 0;  
//全局变量 sum1 = ∑(各层节点数 × 对应层级), sum2 = ∑(各层补全节点 × (对应层级-1))
int n0 = 0, n1 = 0;       
//全局变量 分别用于计算每一层叶子节点 和 度数为1的节点
int supplesum = 0;
//全局变量 计算补全的节点总数

//层次遍历 并利用队列计算二叉树每一层的节点个数
void Show_Level_Order(BinaryTree root){
    if(!root)
	return;
    BinaryTree t = NULL;
    int level = 1;

    std::queue<BinaryTree> q;
    q.push(root);
    while(!q.empty()){
        n0 = n1 = 0;
        int n = q.size();
        for(int i = 0; i < n; i++){
            t = q.front();
            q.pop();
            printf("%d ", t->val);

            if(t->leftchild)  q.push(t->leftchild);
            if(t->rightchild)  q.push(t->rightchild);

            if(!t->leftchild && !t->rightchild)  
                n0 ++ ;  //度数为0的节点
            if(!t->leftchild && t->rightchild || t->leftchild && !t->rightchild) 
                n1 ++ ;  //度数为1的节点
        }
        printf("\n");

        sum1 += n * level;               //每一层节点个数*层级
        sum2 += (n0 * 2 + n1) * level;   //每一层下方需补全节点*层级
        supplesum += (n0 * 2 + n1);      //补全的节点个数 

        level++;
    }
}


完整程序测试

代码

标签:排序,删除,val,二叉,leftchild,数据结构,root,节点
From: https://www.cnblogs.com/MAKISE004/p/17106628.html

相关文章