【C++】模拟实现一颗二叉搜索树

❤️欢迎来到我的博客❤️

---

前言

搜索二叉树是在二叉树的基础上加了一个特征：左子树的所有节点都小于根，右子树的所有节点都大于根（每一颗子树都要满足）
因为这个特性的存在，使得他特别擅长搜索数据
比如我要寻找10，如果当前根为6，比10小，根据这个特征我们就可以排除左子树的节点（都是比6小的数），直接去右子树中寻找
如果当前根为11，比10大，那么我们就可以排除右子树当中所有的数据，直接去左子树中寻找
搜索二叉树也叫二叉搜索树、二叉排序树：当搜索二叉树走中序遍历，他就是一个有序的状态->左->根->右

---

时间复杂度

以上都是二叉搜索树，但他们的时间复杂度却是不一样的，所以时间复杂度为最多找高度次（最坏的情况）：O(N)
后续的AVL树和红黑树都是针对这种情况做出的优化：O(logN)

---

二叉搜索树的模拟实现

整体框架 / insert / inorder

普通二叉树的增删查改是没有价值的，因为数据没有固定的插入位置，所以普通二叉树可以用链表替代
但是二叉搜索树插入的数据就有意义了，因为他们需要插入到他们需要到的位置

插入模式：
比如我们要插入一个11，那我们的顺序就是：根->右->右->左->左插入
如果要插入一个13，顺序是：根->右->右->左，发现已经存在13（目前阶段不允许出现重复数据），插入失败
插入一个16，那我们的顺序就是：根->右->右->右插入

#include <iostream>
using namespace std;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
{typedef BSTreeNode<K> Node;
public:BSTree():_root(nullptr){ }bool Insert(const K& key){//如果是空树if (_root == nullptr){//直接new一个_root = new Node(key);return true;}//循环插入版本Node* parent = nullptr;Node* cur = _root;//如果cur不为空，则去找位置while (cur){// 当前节点值 < 插入值 → 向右子树查找if (cur->_key < key){// 记录父节点parent = cur;//走右子树cur = cur->_right;}else if (cur->_key > key)	// 当前节点值 > 插入值 → 向左子树查找{// 记录父节点parent = cur;//走左子树cur = cur->_left;}else{//如果值存在则插入失败return false;}}//走到指定位置cur = new Node(key);// 判断插入方向if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}//类外面拿不到私有成员//单独写一个函数来调用void InOrder(){_InOrder(_root);}//中序遍历void _InOrder(Node* root){if (root == nullptr){return;}// 递归中序遍历_InOrder(root->_left);		  //左cout << root->_key << " ";	 //根_InOrder(root->_right);	    //右}
private:Node* _root; // 根节点指针
};int main()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.Insert(e);}t.InOrder();// 输出：1 3 4 6 7 8 10 13 14（有序验证BST正确性）return 0;
}

运行结果：

---

查找

bool Find(const K& key)
{Node* cur = _root;// 从根节点开始查找while (cur){if (cur->_key < key)// 目标值 > 当前节点 → 向右子树查找{cur = cur->_right;}else if (cur->_key > key)// 目标值 < 当前节点 → 向左子树查找{cur = cur->_left;}else{return true;	// 找到目标值 → 返回存在}}return false;
}int main()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.Insert(e);}cout << t.Find(13) << endl;cout << t.Find(15) << endl;return 0;
}

运行结果：

---

删除

如果我们要删除7，是属于直接删除的场景，实现起来比较容易（特征：没有孩子）
如果要删除14，也是比较好实现的删除之后，只需要链接一下即可（特征：只有一个孩子）
但是如果我们要删除的是8呢，那要考虑的就多了（特征：两个孩子）这时候就要用替换法（左子树的最大节点（最右节点），或者右子树的最小节点（最左节点））来实现

bool Erase(const K& key)
{Node* parent = nullptr;	 // 记录当前节点的父节点Node* cur = _root;      // 从根节点开始查找//查找while (cur){//使用Find函数做起来会比较麻烦//不考虑服用Findif (cur->_key < key)		// 目标值在右子树{parent = cur;cur = cur->_right;}else if (cur->_key > key)	// 目标值在左子树{parent = cur;cur = cur->_left;}else //找到了{//情况1：左子树为空（含叶子节点）if (cur->_left == nullptr){//处理根节点情况if (cur == _root){// 根指向右子树_root = cur->_right;}else{// 判断当前节点是父节点的左/右孩子if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}//情况2：右子树为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}//情况3：左右子树均不为空（替换法）else{// 查找左子树最大节点作为替代节点Node* parent = cur;				// 记录替代节点的父节点Node* leftMax = cur->_left;		// 进入左子树// 一直向右找到最右节点（左子树最大值）while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}// 交换当前节点与替代节点的值swap(cur->_key, leftMax->_key);// 删除替代节点（此时maxLeft右子树必为空）if (parent->_left == leftMax){// 若替代节点是父的左孩子，链接其左子树parent->_left = leftMax->_left;}else{// 若替代节点是父的右孩子，链接其左子树parent->_right = leftMax->_left;}cur = leftMax;}delete cur;		// 释放替代节点return true;	// 删除成功}}return false; // 未找到目标节点
}int main()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.Insert(e);}t.InOrder();t.Erase(4);t.InOrder();t.Erase(6);t.InOrder();t.Erase(7);t.InOrder();//删空for (auto e : a){t.Erase(e);}cout << "当前树：";t.InOrder();return 0;
}

运行结果：

删除总结

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
实际情况a可以与情况b或者c合并起来，因此真正的删除过程
如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

---

删除逻辑分布解析

二叉搜索树删除操作分步解析

1. 查找待删除节点

核心逻辑：从根节点出发，根据BST特性向左或向右搜索目标值。
终止条件：

• 找到目标节点（cur->_key == key）
• 遍历到空节点（cur == nullptr），说明目标不存在

---

2. 处理删除的三种情况

情况1：左子树为空

特征：待删节点无左孩子（可能为叶子节点或仅有右子树）
操作步骤：

1. 根节点处理：

   • 若删除的是根节点，直接让根指向右子树
   • _root = cur->_right;

2. 非根节点处理：

   • 若待删节点是父节点的右孩子：
   • parent->_right = cur->_right;
   • 若待删节点是父节点的左孩子：
   • parent->_left = cur->_right;

---

情况2：右子树为空

特征：待删节点无右孩子（仅有左子树）
操作步骤（与情况1对称）：

1. 根节点处理：
   • _root = cur->_left;

2.非根节点处理：

• 若待删节点是父节点的右孩子：
• parent->_right = cur->_left;
• 若待删节点是父节点的左孩子：
• parent->_left = cur->_left;

---

情况3：左右子树均不为空

核心思想：找到替代节点替换待删节点的值，再删除替代节点
步骤详解：
步骤1：查找替代节点：两种方案选一即可

方案一：左子树最大节点

Node* parent = cur;				// 记录替代节点的父节点
Node* leftMax = cur->_left;		// 进入左子树// 一直向右找到最右节点（左子树最大值）
while (leftMax->_right)
{parent = leftMax;leftMax = leftMax->_right;
}

方案二：右子树最小节点

Node* minParent = cur;        // 初始化替代节点的父节点为当前节点
Node* minRight = cur->_right; // 进入右子树// 找到右子树的最左节点（最小值节点）
while (minRight->_left) 
{     minParent = minRight;minRight = minRight->_left;
}

步骤2：值替换

// 交换当前节点与替代节点的值
swap(cur->_key, leftMax->_key);

步骤3：删除替代节点

// 删除替代节点（此时maxLeft右子树必为空）
if (parent->_left == leftMax)
{// 若替代节点是父的左孩子，链接其左子树parent->_left = leftMax->_left;
}
else
{// 若替代节点是父的右孩子，链接其左子树parent->_right = leftMax->_left;
}cur = leftMax;

---

递归版本

#include <iostream>
using namespace std;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
{typedef BSTreeNode<K> Node;
public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}void InOrder(){_InOrder(_root);cout << endl;}// 递归查找入口函数bool FindR(const K& key){return _FindR(_root, key);}// 递归插入入口函数bool InsertR(const K& key){return _InsertR(_root, key);}// 递归删除入口函数bool EraseR(const K& key){return _EraseR(_root, key);}private:// 递归删除实现（参数为节点指针的引用，确保树结构正确更新）bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;	// 空树或遍历到叶子未找到目标节点}if (root->_key < key){return _EraseR(root->_right, key);// 递归右子树查找}else if (root->_key > key){return _EraseR(root->_left, key);// 递归左子树查找}else// 找到目标节点{Node* del = root;//1、左为空//2、右为空//3、左右都不为空if (root->_left == nullptr)	//左子树为空{root = root->_right;	// 直接让父节点指针指向右子树}else if (root->_right == nullptr)	//右子树为空{root = root->_left;		//直接让父节点指针指向左子树}else	//左右子树均非空{Node* leftMax = root->_left;	//找到左子树最大节点（最右节点）while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);//交换当前节点与左子树最大节点的键值return _EraseR(root->_left, key);//递归删除左子树中的原最大节点}delete del;return true;}}//递归插入实现（参数为节点指针的引用，确保树结构正确更新）bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);	//创建新节点并链接到父节点return true;}if (root->_key < key){return _InsertR(root->_right, key); // 递归右子树插入}else if (root->_key > key){return _InsertR(root->_left, key); //递归左子树插入}else{return false;}}//递归查找实现bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _FindR(root->_right, key);//递归右子树查找}else if (root->_key > key){return _FindR(root->_left, key); //递归左子树查找}else{return true;}}//中序遍历void _InOrder(Node* root){if (root == nullptr){return;}// 递归中序遍历_InOrder(root->_left);		  //左cout << root->_key << " ";	 //根_InOrder(root->_right);	    //右}Node* _root; //根节点指针
};int main()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.InsertR(e);}t.InOrder();t.EraseR(4);t.InOrder();t.EraseR(6);t.InOrder();t.EraseR(7);t.InOrder();t.EraseR(3);t.InOrder();for (auto e : a){t.EraseR(e);}t.InOrder();return 0;
}

运行结果：

Copy和Destroy

#include <iostream>
using namespace std;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
{typedef BSTreeNode<K> Node;
public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}
private:Node* Copy(Node* root){//递归终止条件if (root == nullptr){return nullptr;}//创建当前节点的副本（深拷贝键值）Node* copyroot = new Node(root->_key);//递归拷贝左子树，并正确链接到副本节点的左指针copyroot->_left = Copy(root->_left);//递归拷贝右子树，并正确链接到副本节点的右指针copyroot->_right = Copy(root->_right);//返回当前子树副本的根节点return copyroot;}void Destroy(Node*& root) {//递归终止条件：当前节点为空，无需处理if (root == nullptr) {return;}//递归销毁左子树Destroy(root->_left);//递归销毁右子树Destroy(root->_right);//释放当前节点内存delete root;//将当前指针置空root = nullptr;}
};

---

key / value模型

节点结构：
每个节点包含Key、Value和左右子节点指针

排序规则：
树的结构依然基于key 的大小关系维护，value不参与运算
左子树所有节点的key < 当前节点的key
右子树所有节点的key > 当前节点的key

namespace key_value
{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{typedef BSTreeNode<K, V> Node;public:BSTree():_root(nullptr){}void InOrder(){_InOrder(_root);cout << endl;}Node* FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key, const V& value){return _InsertR(_root, key, value);}bool EraseR(const K& key){return _EraseR(_root, key);}private:bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_right){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}}bool _InsertR(Node*& root, const K& key, const V& value){if (root == nullptr){root = new Node(key, value);return true;}if (root->_key < key){return _InsertR(root->_right, key, value);}else if (root->_key > key){return _InsertR(root->_left, key, value);}else{return false;}}Node* _FindR(Node* root, const K& key){if (root == nullptr)return nullptr;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root;};}int main()
{key_value::BSTree<string, string> dict;dict.InsertR("insert", "插入");dict.InsertR("sort", "排序");dict.InsertR("right", "右边");dict.InsertR("date", "日期");string str;while (cin >> str){auto ret = dict.FindR(str);if (ret){cout << ret->_value << endl;}else{cout << "无此单词" << endl;}}return 0;
}

运行效果：

---

统计次数场景

修改后的InOrder:

void _InOrder(Node* root)
{if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);
}

int main()
{//统计水果出现的次数string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };key_value::BSTree<string, int> countTree;//遍历水果for (auto& str : arr){//在树中查找当前水果名称对应的节点auto ret = countTree.FindR(str);// 情况1：水果未存在于树中（首次出现）if (ret == nullptr){//插入新节点：为水果名，初始次数为1countTree.InsertR(str, 1);}else// 情况2：水果已存在于树中{//递增该水果的计数ret->_value++;}}//次数统计完成，遍历这棵树countTree.InOrder();return 0;
}

运行结果：

---

以上就是本篇文章的全部内容了，希望大家看完能有所收获

❤️创作不易，点个赞吧❤️