二叉搜索树BST ——（C++）

2024-05-27 14:52
文章标签 c++ 搜索 二叉 bst

本文主要是介绍二叉搜索树BST ——（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        本篇将会讲解有关二叉树的搜索原理，以及关于二叉搜索树的建立，以及二叉树搜索树的插入、删除和查找等基本操作。最后我们还会对二叉搜索树进行功能扩展，介绍有关搜索二叉树的 K 模型和 KV 模型。目录如下：

目录

1. 搜索二叉树

二叉搜索树概念

二叉树类框架

搜索二叉树的插入

搜索二叉树的查找

搜索二叉树的遍历

搜索二叉树的删除

搜索二叉树所有代码

测试

 2. 搜索二叉树的扩展

中英文查找测试代码

统计单词次数测试代码

1. 搜索二叉树

二叉搜索树概念

        二叉搜索树又称二叉排序树，也可以是一棵空树。对于搜索二叉树具有以下性质：

                1. 若左子树不为空，则左子树上所有结点的值都小于根节点的值；

                2. 若右子树不为空，则右子树上所有结点的值都大于根节点的值；

                3. 它的左右子树也分别是二叉搜索树。

        关于二叉搜索树为什么叫做二叉排序树，这是因为左子树小于根节点，右子树大于根节点（二叉搜索树中的元素默认不会重复），当我们使用中序遍历（左 中 右）的时候，遍历刚好出来是有序的。

二叉树类框架

        建立一颗二叉树，首先需要一个结点的类，然后我们需要使用一个根节点将其维护起来。如下：

template <class K>
struct BSTreeNode {BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template <class K>
class BSTree {
public:typedef BSTreeNode<K> Node;private:Node* _root;
};

搜索二叉树的插入

        关于搜索二叉树的插入，我们只需要找到合适的位置将其插入即可。也就是当我们需要插入的元素大于当前元素的时候，我们就继续往右子树放，反之放在左值树，直到到空结点的时候，我们还需要记录当前搜索结点的父亲结点，便于之后将其连接起来，我们就可以插入元素了。

        注：默认搜索二叉树不含有重复元素，所以当插入重复元素的时候，插入失败。

bool insert(const K& key) {if (_root == nullptr) {_root = new Node(key);return true;}// 左子树小于根节点，右子树大于根节点Node* cur = _root;Node* parent = nullptr;while (cur) {if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else {return false;}}cur = new Node(key);if (key < parent->_key)parent->_left = cur;elseparent->_right = cur;return true;
}

搜索二叉树的查找

        查找遵循搜索二叉树的性质，当需要查找的数小于当前结点的时候，我们往左子树查找，当需要查找的数大于当前结点的时候，我们往右边查找。若直到空结点都还没有查找到，那么就查找失败了。如下：

bool find(const K& key) {Node* cur = _root;while (cur) {if (key > cur->_key) {cur = cur->_right;}else if (key < cur->_key) {cur = cur->_left;}else {return true;}}return false;
}

搜索二叉树的遍历

        搜索二叉树的遍历我们采用中序遍历，因为遍历出来的结果就是有序的。我们使用递归遍历。但是我们需要注意的一点是，我们在遍历的时候，需要访问到根节点，但是若我们在类外想要遍历的时候，我们并不能传一个被 private 保护的根节点的，所以我们需要进行如下的封装，就不需要进行传参了。如下：

template <class K>
class BSTree {
public:typedef BSTreeNode<K> Node;// 中序遍历void InOrder() {_InOrder(_root);cout << endl;}private:void _InOrder(Node* root) {// 左中右if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
private:Node* _root;
};

搜索二叉树的删除

        关于搜索二叉树结点的删除，会存在很多的情况，如：删除的位置是叶子结点，删除的位置左子树为空，删除的位置右子树为空，删除的位置左右子树都不为空，删除的位置为根节点，且左子树或右子树为空。

        所以搜索二叉树的删除实现较为复杂，首先需要找到该位置，若直到空结点都还未找到，则二叉树中并无该元素，删除失败，返回 false；

        若删除的位置是叶子结点，删除的位置左子树为空，删除的位置右子树为空：我们先讨论删除位置的左子树为空，那么删除位置右节点可能不为空，所以删除该位置之后需要将删除位置的父亲结点的指针（可能是左，也可能是右）指向删除结点的右子树。删除位置的右子树为空，那么删除位置左节点可能不为空，所以删除该位置之后需要将删除位置的父亲结点的指针（可能是左，也可能是右）指向删除结点的左子树。当我们实现以上的两种情况的时候，我们发现删除位置是叶子结点的问题也迎刃而解了。

        删除的位置左右子树都不为空：当我们删除位置的左子树和右子树都不为空的时候，我们就需要讨论一个问题，删除该位置之后，左右子树该如何进行连接？答案是找到左子树的最大节点（最右结点）或者找到右子树的最小结点（最左结点）将其替换即可，替换之后在将其删除即可，但是其中还有一个不可忽视的问题，当我们替换之后删除的位置并不是叶子结点的时候，又该如何进行连接呢？以替换删除的结点为右子树的最小结点为例子，我们需要将删除结点的父亲结点指向（可能是左指针也可能是右指针，需要判断）删除结点的右子树。

        删除的位置为根节点，且左子树或右子树为空：当需要删除的结点为根结点且一端的子树为空的时候，我们只需要将根节点往另一个相反的结点移位即可。如下：

        将会对每种情况在代码中注释：

bool erase(const K& key) {// 先寻找key，找到删除，没找到直接返回falseNode* cur = _root;Node* parent = nullptr;while (cur) {if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else {break;}}if (cur == nullptr) return false;// 需要删除位置的左子树或右子树为空if (cur->_left == nullptr) {// 删除位置为根节点if (parent == nullptr) {parent = cur;_root = cur->_right;delete parent;return true;}else {if (parent->_right == cur)parent->_right = cur->_right;elseparent->_left = cur->_right;delete cur;}}else if (cur->_right == nullptr) {if (parent == nullptr) {parent = cur;_root = cur->_left;delete parent;return true;}else {if (parent->_right == cur)parent->_right = cur->_left;elseparent->_left = cur->_left;delete cur;}}else {// 删除左右子树都有元素的结点// 找到右边最小的Node* rightMin = cur->_right;Node* rightMinParent = cur;while (rightMin->_left) {rightMinParent = rightMin;rightMin = rightMin->_left;}// 现在的rightMin为右子树最小结点元素std::swap(cur->_key, rightMin->_key);// 若要删除的结点如父亲结点的左结点，链接左边if (rightMinParent->_right == rightMin)rightMinParent->_right = rightMin->_right;elserightMinParent->_left = rightMin->_right;delete rightMin;}return true;
}

搜索二叉树所有代码

template <class K>
struct BSTreeNode {BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template <class K>
class BSTree {
public:typedef BSTreeNode<K> Node;// 构造函数BSTree() : _root(nullptr) {}// 插入、删除、查找、遍历函数bool insert(const K& key) {if (_root == nullptr) {_root = new Node(key);return true;}// 左子树小于根节点，右子树大于根节点Node* cur = _root;Node* parent = nullptr;while (cur) {if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else {return false;}}cur = new Node(key);if (key < parent->_key)parent->_left = cur;elseparent->_right = cur;return true;}bool find(const K& key) {Node* cur = _root;while (cur) {if (key > cur->_key) {cur = cur->_right;}else if (key < cur->_key) {cur = cur->_left;}else {return true;}}return false;}bool erase(const K& key) {// 先寻找key，找到删除，没找到直接返回falseNode* cur = _root;Node* parent = nullptr;while (cur) {if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else {break;}}if (cur == nullptr) return false;// 现在的 cur 是我们需要删除的结点// 若该结点为根节点if (cur->_left == nullptr) {if (parent == nullptr) {parent = cur;_root = cur->_right;delete parent;return true;}else {if (parent->_right == cur)parent->_right = cur->_right;elseparent->_left = cur->_right;delete cur;}}else if (cur->_right == nullptr) {if (parent == nullptr) {parent = cur;_root = cur->_left;delete parent;return true;}else {if (parent->_right == cur)parent->_right = cur->_left;elseparent->_left = cur->_left;delete cur;}}else {// 删除左右子树都有元素的结点// 找到右边最小的Node* rightMin = cur->_right;Node* rightMinParent = cur;while (rightMin->_left) {rightMinParent = rightMin;rightMin = rightMin->_left;}// 现在的rightMin为右子树最小结点元素std::swap(cur->_key, rightMin->_key);// 若要删除的结点如父亲结点的左结点，链接左边if (rightMinParent->_right == rightMin)rightMinParent->_right = rightMin->_right;elserightMinParent->_left = rightMin->_right;delete rightMin;}return true;}void InOrder() {_InOrder(_root);cout << endl;}private:void _InOrder(Node* root) {// 左中右if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
private:Node* _root;
};int main() {BSTree<int> bs;vector<int> v({ 8, 3, 1, 10, 6, 4, 7, 14, 13 });for (auto e : v) {bs.insert(e);}bs.InOrder();bs.erase(1);for (auto e : v) {bs.erase(e);bs.InOrder();}bs.InOrder();return 0;
}
测试

 2. 搜索二叉树的扩展

        关于搜索二叉树一共存在两种模型，一种为 K 模型，另一种为 KV 模型，如下：

        K 模型：K 模型即只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值。（也就是上文中实现的搜索二叉树）

        KV 模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
        关于 KV 模型，比如：英汉词典就是英文与中文的对应关系、统计单词次数，统计成功后，给定单词就可快速找到其出现的次数。

        关于 KV 模型的实现和 K 模型大同小异，如下：

template <class K, class V>
struct BSTreeNode {BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value):_left(nullptr),_right(nullptr),_key(key),_value(value){}
};template <class K, class V>
class BSTree {
public:typedef BSTreeNode<K, V> Node;// 构造函数BSTree() : _root(nullptr) {}// 插入、删除、查找、遍历函数bool insert(const K& key, const V& value) {if (_root == nullptr) {_root = new Node(key, value);return true;}// 左子树小于根节点，右子树大于根节点Node* cur = _root;Node* parent = nullptr;while (cur) {if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else {return false;}}cur = new Node(key, value);if (key < parent->_key)parent->_left = cur;elseparent->_right = cur;return true;}Node* find(const K& key) {Node* cur = _root;while (cur) {if (key > cur->_key) {cur = cur->_right;}else if (key < cur->_key) {cur = cur->_left;}else {return cur;}}return nullptr;}bool erase(const K& key) {// 先寻找key，找到删除，没找到直接返回falseNode* cur = _root;Node* parent = nullptr;while (cur) {if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else {break;}}if (cur == nullptr) return false;// 现在的 cur 是我们需要删除的结点// 若该结点为根节点if (cur->_left == nullptr) {if (parent == nullptr) {parent = cur;_root = cur->_right;delete parent;return true;}else {if (parent->_right == cur)parent->_right = cur->_right;elseparent->_left = cur->_right;delete cur;}}else if (cur->_right == nullptr) {if (parent == nullptr) {parent = cur;_root = cur->_left;delete parent;return true;}else {if (parent->_right == cur)parent->_right = cur->_left;elseparent->_left = cur->_left;delete cur;}}else {// 删除左右子树都有元素的结点// 找到右边最小的Node* rightMin = cur->_right;Node* rightMinParent = cur;while (rightMin->_left) {rightMinParent = rightMin;rightMin = rightMin->_left;}// 现在的rightMin为右子树最小结点元素std::swap(cur->_key, rightMin->_key);// 若要删除的结点如父亲结点的左结点，链接左边if(rightMinParent->_right == rightMin)rightMinParent->_right = rightMin->_right;elserightMinParent->_left = rightMin->_right;delete rightMin;}return true;}void InOrder() {_InOrder(_root);cout << endl;}private:void _InOrder(Node* root) {// 左中右if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << " " << root->_value << endl;_InOrder(root->_right);}
private:Node* _root;
};
中英文查找测试代码
int main() {BSTree<string, string> bs;string s1 = "insert";string v1 = "插入";string s2 = "right";string v2 = "右边";string s3 = "left";string v3 = "左边";bs.insert(s1, v1);bs.insert(s2, v2);bs.insert(s3, v3);string s;while (cin >> s) {if (bs.find(s))cout << bs.find(s)->_value << endl;elsecout << "没有该单词的含义" << endl;}return 0;
}
统计单词次数测试代码
int main() {string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> bs;for (auto& str : arr) {auto ret = bs.find(str);if (ret == nullptr)bs.insert(str, 1);elseret->_value++;}bs.InOrder();return 0;
}

这篇关于二叉搜索树BST ——（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1007797。

相关文章

C++统计函数执行时间的最佳实践

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
深入解析C++ 中std::map内存管理

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象
阅读更多...
C++ STL-string类底层实现过程

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数
阅读更多...
C++ vector越界问题的完整解决方案

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基
阅读更多...
c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...
C++中全局变量和局部变量的区别

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2