搜索二叉树【C++】

二叉搜索树

二叉搜索树又称为二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

若它的左子树不为空，
则左子树上所有结点的值都小于根结点的值。

若它的右子树不为空，
则右子树上所有结点的值都大于根结点的值。

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

二叉搜索树的模拟实现

构造函数

	BSTree():_root(nullptr){}

拷贝构造函数

	BSTree(const  BSTree<K>& t)//BSTree(  BSTree<K>  *this ,  const  BSTree<K> & t)//t1 =t {_root = Copy(t._root);}private:Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* copyNode = new Node(root->_key);//递归 copyNode->_left = Copy(root->_left);copyNode->_right = Copy(root->_right);return  copyNode;}

赋值运算符重载函数

	//赋值重载 BSTree<K>& operator= (BSTree<K>& t)//t1 = t//深拷贝{swap(_root, t._root);return *this;}

析构函数

~BSTree(){Destroy(_root);}private:void Destroy(Node*& root) //引用的目的：将每个节点释放后同时置空{//后序遍历 if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}

Insert

核心思路：

如果是空树，则直接将插入结点作为二叉搜索树的根结点。

如果不是空树，则按照二叉搜索树的性质进行结点的插入。
如果待插入结点的值<根结点的值，则需要将结点插入到左子树当中。
如果待插入结点的值>根结点的值，则需要将结点插入到右子树当中。
如果待插入结点的值等于根结点的值，则插入失败。

循环

bool Insert(const K & key ){//空树if (_root == nullptr){_root = new Node(key);return true;}//不是空树Node* parent = nullptr;//找到父节点Node* cur = _root;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);//不知道parent在那一边,需要进一步判断if (parent->_key > key){//parent在左边parent->_left = cur;}else if (parent->_key < key){//parent在右边parent->_right = cur;}else{return false;}return true;}

递归

	bool InsertR(const K& key)//递归版本{return _InsertR(_root, key);}private:bool _InsertR(Node*& root, const K& key) //引用的目的：不用找父节点，不需要用父节点比较大小{//结束条件if (root == nullptr){root = new Node(key);return true;}//往左子树走if (root->_key > key){return _InsertR(root->_left, key);}//往右子树走else if (root->_key < key){return _InsertR(root->_right, key);}else{return false;}}

Erase

先找到需要删除的节点
需要删除的节点可能会有三种情况：
1、待删除结点的左子树为空（待删除结点的左右子树均为空包含在内）

2、待删除结点的右子树为空。

1、2 两种情况，被删除的节点都只有一个孩子

3、待删除结点的左右子树均不为空，即被删除节点有两个孩子
使用替换法处理第3中情况：
1、找替换节点：替换节点一般是左子树的最大节点（最右节点），或者是右子树的最小节点（最左节点）
2、将替换的节点删除

特殊情况：

循环

	bool Erase(const K& key){Node* parent = nullptr;//待删除节点的父节点Node* cur = _root;//待删除的节点//不是空树while (cur){//往左边走if (cur->_key > key){parent = cur;cur = cur->_left;}//往右边走else if (cur->_key < key){parent = cur;cur = cur->_right;}//找到待删除的节点else{//待删除节点的左子树为空 ,即一个孩子的情况if (cur->_left == nullptr){//待删除节点是根节点if (cur == _root){//将根节点改为待删除节点的右孩子_root = cur->_right;}//待删除节点不是根节点,并且此时parent不为nullptrelse{if (parent->_right == cur){parent->_right = cur->_right;}else//parent->_left ==cur{parent->_left = cur->_right;}}}//待删除节点的右子树为空 ,即一个孩子的情况else if (cur->_right == nullptr){//待删除节点是根节点if (cur == _root){//将根节点改为待删除节点的左孩子_root = cur->_left;}//待删除节点不是根节点,并且此时parent不为nullptrelse{if (parent->_right == cur){parent->_right = cur->_left;}else//parent->_left==cur{parent->_left = cur->_left;}}} else //待删除的节点的左右孩子都不为空 （替换法：左子树的最大节点即最右节点，或者右子树的最小节点即最左节点,并且将替换的节点删除）{//替换法//找替代节点Node* parent = cur;//找左子树的最大节点,左子树的最大节点一定没有右孩子Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax; //记录leftMax的父节点，防止删除leftMax时找不到该节点位置 //一直往右子树找leftMax = leftMax->_right;}//左子树的最大节点和待删除节点替换swap(cur->_key, leftMax->_key);//重新改变链接关系//特殊情况 if (parent->_left == leftMax){parent->_left = leftMax->_left;}else//普通情况 parent->_right== leftMax{parent->_right = leftMax->_left;}cur = leftMax;}//删除左子树的最大节点delete cur;return true;}}return false;}

递归

	bool EraseR(Node* _root, 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->_left, key);}//往右树找else if (root->_key < key){return _EraseR(root->_right, 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 (root->_left){root = root->_left;}//将左子树最大节点与被删除节点替换swap(leftMax->_key, root->_key);return _EraseR(root, key);}delete del;//?return true;}}

Find

循环

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

递归

	bool FindR(Node* _root, const K& key)//递归版本{return _FindR(_root, key);}private:bool  _FindR(Node* root, const K& key){//结束条件if (root == nullptr){return false;}if (root->_key > key){return _FindR(root->_left, key);}else if (root->_key < key){return _FindR(root->_right, key);}else{return true;}}

二叉搜索树的应用

K模型

K模型，即只有key作为关键码，结构中只需存储key即可，关键码即为需要搜索到的值。

比如：给定一个单词，判断该单词是否拼写正确。具体方式如下：

	void TestBSTree1(){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);//auto ret = dict.FindR(str);if (ret){cout << ret->_value << endl;}else{cout << "无此单词" << endl;}}}

KV模型

KV模型，对于每一个关键码key，都有与之对应的值value，即<key, value>的键值对。

英汉词典就是英文与中文的对应关系，即<word, Chinese>就构成一种键值对。具体方式如下

1、以<单词, 中文含义>为键值对，构建一棵二叉搜索树。注意：二叉搜索树需要进行比较，键值对比较时只比较key。
2、查询英文单词时，只需给出英文单词就可以快速找到与其对应的中文含义。

完整代码

普通版本

#pragma once 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){_root = new Node(key);return true;}//不是空树Node* parent = nullptr;//找到父节点Node* cur = _root;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);//不知道parent在那一边,需要进一步判断if (parent->_key > key){//parent在左边parent->_left = cur;}else if (parent->_key < key){//parent在右边parent->_right = cur;}else{return false;}return true;}bool Find(const K & key){Node* cur = _root;while (cur){if (cur->_left > key){cur = cur->_left;}else if (cur->_left < key){cur = cur->_right;}else{return false;}return true;}}bool Erase(const K& key){Node* parent = nullptr;//待删除节点的父节点Node* cur = _root;//待删除的节点//不是空树while (cur){//往左边走if (cur->_key > key){parent = cur;cur = cur->_left;}//往右边走else if (cur->_key < key){parent = cur;cur = cur->_right;}//找到待删除的节点else{//待删除节点的左子树为空 ,即一个孩子的情况if (cur->_left == nullptr){//待删除节点是根节点if (cur == _root){//将根节点改为待删除节点的右孩子_root = cur->_right;}//待删除节点不是根节点,并且此时parent不为nullptrelse{if (parent->_right == cur){parent->_right = cur->_right;}else//parent->_left ==cur{parent->_left = cur->_right;}}}//待删除节点的右子树为空 ,即一个孩子的情况else if (cur->_right == nullptr){//待删除节点是根节点if (cur == _root){//将根节点改为待删除节点的左孩子_root = cur->_left;}//待删除节点不是根节点,并且此时parent不为nullptrelse{if (parent->_right == cur){parent->_right = cur->_left;}else//parent->_left==cur{parent->_left = cur->_left;}}} else //待删除的节点的左右孩子都不为空 （替换法：左子树的最大节点即最右节点，或者右子树的最小节点即最左节点,并且将替换的节点删除）{//替换法//找替代节点Node* parent = cur;//找左子树的最大节点Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax; //记录leftMax的父节点，防止删除leftMax时找不到该节点位置 //一直往右子树找leftMax = leftMax->_right;}//左子树的最大节点和待删除节点替换swap(cur->_key, leftMax->_key);//重新改变链接关系//特殊情况 if (parent->_left == leftMax){parent->_left = leftMax->_left;}else//普通情况 {parent->_right = leftMax->_left;//parent->_right =nullptr;}cur = leftMax;}//删除左子树的最大节点delete cur;return true;}}return false;}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node *root  ){if (root == nullptr){return; }_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root;
};void TestBSTree1()
{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();t.Erase(3);t.InOrder();for (auto e : a){t.Erase(e);}t.InOrder();}

递归版本

#pragma once 
#include<string>
using namespace std;
namespace key
{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;public:BSTree():_root(nullptr){}~BSTree(){Destroy(_root);}//拷贝构造BSTree(const  BSTree<K>& t)//BSTree(  BSTree<K>  *this ,  const  BSTree<K> & t)//t1 =t {_root = Copy(t._root);}//赋值重载 BSTree<K>& operator= (BSTree<K>& t)//t1 = t{swap(_root, t._root);return *this;}bool EraseR(Node* _root, const K& key)//递归版本{return _EraseR(_root, key);}bool InsertR(const K& key)//递归版本{return _InsertR(_root, key);}bool FindR(Node* _root, const K& key)//递归版本{return _FindR(_root, key);}private:Node* Copy(Node* root){if (root == nullptr){return nullptr;}Node* copyNode = new Node(root->_key);//递归 copyNode->_left = Copy(root->_left);copyNode->_right = Copy(root->_right);return  copyNode;}void Destroy(Node*& root) //引用的目的：将每个节点释放后同时置空{//后序遍历 if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}bool _InsertR(Node*& root, const K& key) //引用的目的：不用找父节点，不需要用父节点比较大小{//结束条件if (root == nullptr){root = new Node(key);return true;}//往左子树走if (root->_key > key){return _InsertR(root->_left, key);}//往右子树走else if (root->_key < key){return _InsertR(root->_right, key);}else{return false;}}bool _EraseR(Node*& root, const K& key)//引用的目的：不用找父节点，不需要用父节点比较大小{//结束条件if (root == nullptr){return false;}//往左树找if (root->_key > key){return _EraseR(root->_left, key);}//往右树找else if (root->_key < key){return _EraseR(root->_right, 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 (root->_left){root = root->_left;}//将左子树最大节点与被删除节点替换swap(leftMax->_key, root->_key);return _EraseR(root, key);}delete del;//?return true;}}bool  _FindR(Node* root, const K& key){//结束条件if (root == nullptr){return false;}if (root->_key > key){return _FindR(root->_left, key);}else if (root->_key < key){return _FindR(root->_right, key);}else{return true;}}public://中序遍历void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}public:Node* _root;};void TestBSTree1(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.InsertR(e);}t.InOrder();//没有引用，释放了，只是指针没有置空，尤其是根节点_root，我们还能通过他找到/*t.Destroy(t._root);*/t.EraseR(t._root, 4);t.InOrder();t.EraseR(t._root, 6);t.InOrder();t.EraseR(t._root, 7);t.InOrder();t.EraseR(t._root, 3);t.InOrder();for (auto e : a){t.EraseR(t._root, e);}t.InOrder();}void TestBSTree2(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.InsertR(e);}t.InOrder();BSTree<int> t1(t);t.InOrder();t1.InOrder();}
}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{public: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;// 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, 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;};void TestBSTree1(){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);//auto ret = dict.FindR(str);if (ret){cout << ret->_value << endl;}else{cout << "无此单词" << endl;}}}void TestBSTree2(){string arr[] = {"西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int > countTree;for (auto &str : arr){auto ret = countTree.FindR(str);if (ret == nullptr){countTree.InsertR(str,1);}else{ret->_value++;}}countTree.InOrder();}}

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注你们的每一次支持都将转化为我前进的动力！！！