当前位置：首页 > news >正文

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

news 2025/12/2 19:53:35

文章目录

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

1. 二叉搜索树是什么

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

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

在这里插入图片描述

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;
};