IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【数据结构】二叉查找树/二叉搜索树BST(附相关C++代码) -> 正文阅读

[数据结构与算法]【数据结构】二叉查找树/二叉搜索树BST(附相关C++代码)


本文内容将主要介绍二叉查找树的相关概念,与关于二叉查找树的重要操作,如添加节点、删除节点等。

BST相关概念

二叉查找树(Binary Search Tree),又被称为二叉搜索树。在二叉查找树中,根结点的值一定大于左节点的值,一定小于右节点的值,例如下图所示:

在这里插入图片描述

特点:

  1. 任意节点的左子树不空, 则左子树上所有节点的key均小于它的根节点的key
  2. 任意节点的右子树不空, 则右子树上所有节点的key均大于它的根节点的key
  3. 任意节点的左,右子树也分别为二叉查找树
  4. 没有key相等的节点
  5. 二叉查找树进行中序遍历,可以得到一个递增的有序序列

BST如何添加节点

主要思想:

  • 二叉树为空,直接插入即可
  • 二叉树不为空,则比较即将被插入的节点与根节点的大小,如果比其大,则插入右子树中,否则插入左子树中,直至找到插入位置(新插入的结点一定是一个叶子结点)

原始树为一棵空树,执行操作如图:

  1. 插入值为15的节点,如下:
    在这里插入图片描述

  2. 插入值为4的新节点
    在这里插入图片描述

  3. 插入值20为的节点
    在这里插入图片描述

  4. 插入值为17的节点

在这里插入图片描述
基本思想如上,我们给出实现代码如下:

    Node* Add(Node* node, int val){
        if(node == nullptr){
            return new Node(val);
        }
        if(val < node->val){
            node->left = Add(node->left, val);
        }else{
            node->right = Add(node->right, val);
        }
        return node;
    }

BST如何遍历

BST在本质上还是一棵二叉树,我们可以使用遍历二叉树的方式来进行遍历,如若对二叉树的遍历不是很理解,可以查看这篇博客:
数据结构】二叉树的深度优先遍历DFS和广度优先遍历BFS(含C++递归和非递归方式实现)

我们直接各给出遍历BST的代码,具体如下:

    void Print(Node* node)const{
        if(node == nullptr) return;
        if(node->left!=nullptr){
            cout << node->val << "->" << node->left->val << endl;
            Print(node->left);
        }
        if(node->right!=nullptr){
            cout << node->val << "->" << node->right->val << endl;
            Print(node->right);
        }
    }

BST如何求最值

因为BST的前序是一个有序树,这个特点就决定BST的最值位置是很特殊的,它的最大值位于树的最右下的节点,最小值位于最左下的节点,具体代码实现如下:

最大值:

    Node* Max(Node* node)const{
        if(nullptr == node) return nullptr;
        Node* p = node;
        while(nullptr != p->right){
            p = p->right;
        }
        return p;
    }

最小值:

    Node* Min(Node* node)const{
        if(nullptr == node) return nullptr;
        Node* p = node;
        while(nullptr != p->left){
            p = p->left;
        }
        return p;
    }

BST如何删除节点

BST结点的删除相较于我们刚了解的增添节点和遍历相对而言比较复杂,它不像二叉树删除结点的操作,直接将某一个叶子节点进行置换即可,在BST中,我们在删除某一个指定的节点后,还需要将该树整理为一个BST,即是让它的中序遍历有序递增。

具体思路如下:

删除节点是叶子节点:直接进行删除即可,删除之后该仍然是一棵BST;
在这里插入图片描述

删除节点的右/左子树为空,此时直接将该结点所有的右/左子树的根结点作为删除节点;
在这里插入图片描述

删除元素左右子树均不为空,我们在这里使用找到一个节点代替待删除节点即可。

  1. 这个节点其是最好是待删除节点的右子树的最小值(右子树最左下的节点),或者是左子树的最大值(左子树最右下的节点);
  2. 这样找的好处是找到的节点一定是一个叶子节点或者是一个左子树或者右子树为空的节点,我们就将删除一个左右子树为空的元素转化为删除一个要么左子树为空要么右子树为空(甚至为叶子结点)的元素。
    在这里插入图片描述

具体思想大家理解了之后,我们给出实现代码如下:

    Node* Del(Node* node, int val){
        if(nullptr == root) return nullptr;
        if(node->val == val){
            if(nullptr==node->right && nullptr==node->left){
                // 叶子节点
                delete node;
                return nullptr;
            }
            if(nullptr == node->right){
                // 右子树为空
                // 直接使用当前待删除节点的左节点代替该结点
                Node* p = node->left;
                delete node;
                return p;
            }
            if(nullptr == node->left){
                // 左子树为空
                // 直接使用当前待删除节点的右节点代替该结点
                Node* p = node->right;
                delete node;
                return p;
            }
            // 左右孩子都有时
            // 直接使用该节点为根结点的右子树的最小值代替当前节点
            Node* maxNode =  Min(node->right);
            node->val = maxNode->val;
            node->right = Del(node->right, maxNode->val);
        }else if(node->val > val){
            node->left == Del(node->left, val);
        }else{
            node->right == Del(node->right, val);
        }
        return node;
    }

BST如何查找节点

我们知道BST的中序遍历结果是一个有序递增的数列,所以在BST中进行查找的操作的效率很高,该操作的计算复杂度与该树的高度成线性相关。

其实在本质上就是进行二分查找,当查找的节点值比当前节点值小,则比较当前节点的左子树的根结点(也就是左孩子),否则比较右子树的根结点(也就是右孩子),直至找到该节点,具体代码如下:

    Node* Search(Node* node, int val)const{
        if(nullptr == node) return nullptr;
        if(node->val == val) return node;
        if(node->val > val){
                return Search(node->left, val);
        }else{
                return Search(node->right, val);
        }
    }

如何验证一棵树是BST

这里有一个易错的点,因为BST的有序性,我们很容易想到利用比较树中的任意一个结点和其左右孩子的大小是否符合要求来判断,但这种判断方式是有问题的,例如这样一棵树:

在这里插入图片描述

这棵树中的任意一个结点的左孩子都小于其父节点,右孩子都大于父节点,但是这并不是一棵BST,值为5的节点应该位于值为15的左子树上。

判断一棵树是否是BST,应该比较树中的任意一个节点的左子树中的最大值比该结点小,右子树的最小值比其大。

具体代码如下:

    int maxleft(TreeNode* root){
        TreeNode* node = root;
        while(node->right!=nullptr){
            node = node->right;
        }
        return node->val;
    }
    int minright(TreeNode* root){
        TreeNode* node = root;
         while(node->left!=nullptr){
            node = node->left;
        }
        return node->val;
    }

    bool isValidBST(TreeNode* root){
        if(root == nullptr) return true;
        if(root->left!=nullptr && root->right!=nullptr){ //左右孩子均在
            if(root->val>=minright(root->right) || root->val<=maxleft(root->left)){
                return false;
            }else{
                return isValidBST(root->left) && isValidBST(root->right);
            }
        }else if(root->left!=nullptr){        // 左孩子在
            if(root->val<=maxleft(root->left)) return false;
            else{
                return isValidBST(root->left);
            }
        }else if(root->right!=nullptr){       // 右孩子在
            if(root->val>=minright(root->right)){
                return false;
            }else{
                return isValidBST(root->right);
            }
        } else{                                // 叶子节点
            return true;
        }
        return false;
    }

以上的代码虽然看起来很长,但是思路很清晰,大家应该很容易看懂,除此以外,我们给出一种简洁的代码解决这个问题,具体如下:

    bool isValidBST(TreeNode* root, long maxVal, long minVal){
        if(nullptr == root) return true;
        if(root->val <= minVal || root->val >=maxVal){
            return false;
        }
        return isValidBST(root->right, maxVal, root->val) 
        && isValidBST(root->left, root->val, minVal);
    }
    bool isValidBST(TreeNode* root){
        return isValidBST(root, LONG_MAX, LONG_MIN);
    }

除此以外,我们还可以使用中序遍历该树,判断遍历结果是否有序,具体代码如下:

    double prevalue = -2147483649;  
    // prevalue将用于保存中序遍历过程中当前节点的前一个结点的值
    bool isValidBST(TreeNode* root) {
        if(root == NULL)  return true;
        if(!isValidBST(root->left)){
            return false;
        }
        if(prevalue >= root->val) {
            return false;
        }else{
            prevalue = root->val;
        }

        if(!isValidBST(root->right)){
            return false;
        }else{
            return true;
        }
    }
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章           查看所有文章
加:2022-05-21 19:13:41  更:2022-05-21 19:16:20 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 7:07:10-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码