欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 健康 > 养生 > C++_进阶:二叉搜索树

C++_进阶:二叉搜索树

2025/5/2 7:20:57 来源:https://blog.csdn.net/Lvision2/article/details/141284159  浏览:    关键词:C++_进阶:二叉搜索树

文章目录

    • 1. 二叉搜索树是什么
    • 2. 二叉搜索树的基本操作
    • 3. 二叉搜索树的实现
    • 4 二叉搜索树的性能分析

1. 二叉搜索树是什么

二叉搜索树(BST,Binary Search Tree)又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

在这里插入图片描述

2. 二叉搜索树的基本操作

二叉搜索树的查找:

  1. 从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。
  2. 最多查找高度次,走到到空,还没找到,这个值不存在

二叉搜索树的插入:
3. 当树为空(root == nullptr )时,则直接新增节点,赋值给root指针。
4. 当**树不为空(root != nullptr )**时,按二叉搜索树性质查找插入位置,插入新节点

在这里插入图片描述
二叉搜索树的删除:
先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面三种情况
在这里插入图片描述
像1,2 情况,直接删除即可,删除后依然能维持二叉搜索树的结构。
在这里插入图片描述

情况3比前两种复杂一点,需要在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题–替换法删除。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3. 二叉搜索树的实现

先要实现一个Binary Search Tree节点类模板

template<class T>
class BSTreeNode
{
public:BSTreeNode(const T&key):_val(key),left(nullptr),right(nullptr){}//成员即 值 , 左子树,右子树T _val;BSTreeNode* left;BSTreeNode* right;
};

再实现二叉搜索树本体

template<class T>
class BSTree
{typedef BSTreeNode<T> Node;
public:bool find(const T& key){Node* cur = root;while (cur){if (cur->_val > key){cur = cur->left;}else if (cur->_val < key){cur = cur->right;}else{return true;}}return false;}bool Insert(const T& key){if (root == nullptr){root = new Node(key);return true;}Node* parent = nullptr;Node* cur = root;while (cur){if (cur->_val > key){parent = cur;cur = cur->left;}else if (cur->_val < key){parent = cur;cur = cur->right;}else{return false;}}if (parent->_val < key){parent->right = new Node(key);}else{parent->left = new Node(key);}return true;}bool erase(const T& key){Node* parent = nullptr;Node* cur = root;while (cur){if (cur->_val > key){parent = cur;cur = cur->left;}else if (cur->_val < key){parent = cur;cur = cur->right;}else{//0-1孩子的情况if (cur->left == nullptr){if (parent == nullptr){root = cur->right;}else{if (cur == parent->left){parent->left = cur->right;}else{parent->right = cur->right;}}delete cur;return true;}else if(cur->right== nullptr){if (parent == nullptr){root = cur->left;}else{if (cur == parent->left){parent->left = cur->left;}else{parent->right = cur->left;}}delete cur;return true;}else{Node* rightMin = cur->right;Node* rightMinP = cur;while (rightMin->left){rightMinP = rightMin;rightMin = rightMin->left;}cur->_val = rightMin->_val;if (rightMinP->left == rightMin){cur->left = rightMin->right;}else{rightMinP->right = rightMin->right;}delete rightMin;return true;}}}return false;}
private:Node* root = nullptr;
};

4 二叉搜索树的性能分析

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能
对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多

但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
在这里插入图片描述
最优情况下,二叉搜索树为完全二叉树(或接近完全二叉树),其平均比较次为O(logN)
最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为 O(N)

本文就到这里,感谢你看到这里❤️❤️! 我知道一些人看文章喜欢静静看,不评论🤔,但是他会点赞😍,这样的人,帅气低调有内涵😎,美丽大方很优雅😊,明人不说暗话,要你手上的一个点赞😘!

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词