二叉搜索树（C++）

在使用C语言写数据结构阶段时，对二叉树进行了讲解。本节内容是对二叉树的深入探索，也是二叉树部分的收尾

概念

二叉搜索树也称二叉排序树（BST，Binary Search Tree）：

1. 空树
2. 非空树（要具有以下性质）
   • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
   • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
   • 它的左右子树也分别为二叉搜索树

注意： 二叉搜索树的key值互不相同

eg:下图就属于二叉搜索树

二叉搜索树的应用

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

   eg: 给一个单词word，判断该单词是否拼写正确？具体步骤：1. 以词库中所有单词为基础，每个单词都是key，构建一颗搜索二叉树2. 在二叉树中搜索该单词是否存在，存在则返回true，否则返回false
  

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

   eg1: 英汉词典 - 就是中文与英文的对应关系。通过英文可以快速找到与其对应的中文，英文单词和与其对应的中文<word, chinese>就构成键值对。eg2: 统计单词次数，统计成功后，给定单词就可以找到单词出现得次数。单词与其出现次数就是<word, count>就构成一种键值对
  

二叉搜索树的实现

注意： 通过二叉搜索树的应用，了解到其有两个模型，接下来对这两个模型分别进行实现。因为两个模型的接口都相似，所以仅对一个模型的接口进行详细介绍。

K模型

K模型的实现分为递归和非递归两种，但是接口的实现逻辑是一样的。为了便于理解把基本结构和函数声明先附上，然后对接口进行讲解，最后在贴上完整的源码

基本结构和函数声明

//二叉树节点
//节点使用struct，默认public访问
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);//赋值运算符重载BSTree<K>& operator=(BSTree<K> t);//析构函数~BSTree();//插入bool Insert(const K& key);//查找bool Find(const K& key);//删除bool Erase(const K& key);//中序遍历void InOrder();private:Node* _root;
};

接口实现

①find——查找关键码

功能：查找关键码是否在树中，是返回真，否则返回假。
原理：

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

实现代码

1. 非递归版本

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

2. 递归版本

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

②Insert——插入关键码

原理：

1. 树为空，直接把要插入的节点赋值给root
2. 树不为空，通过查找的思路，找到要插入的合适位置。插入成功返回true
   注意：如果要插入的值和树中的值冲突，则返回false

实现代码

1. 非递归版本

//插入
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->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;
}

2. 递归版本

bool InsertR(const K& key)
{return _InsertR(_root, key);
}
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);elsereturn true;
}

③Erase——删除关键码（重点）

原理：

1. 查找关键码是否在二叉搜索树中，不存在直接返回false
2. 存在，则要分为四种情况

情况：
在考虑树的所有情况时，要把根节点的情况和普通情况，分离开来。哪怕最后根节点的情况和普通情况一样。（仅代表博主个人观点）

1. 要删除的节点无孩子节点
   

2. 要删除的节点无左孩子节点
   

3. 要删除的节点无右孩子节点
   

4. 要删除的节点左右都不为空 （采用的方法 一 替换法）
   替换法：找到删除节点左子树的最大值节点(leftMax)，然后与删除节点交换，再删除现在的leftMax。（也可以找删除节点右子树的最小值节点(rightMin)，原理相同）
   

实现代码

1. 非递归版本

//删除
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  //找到了要删除的值{//分情况//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{parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;cur = nullptr;return true;}}return false;
}

2. 递归版本

//删除
bool EraseR(const K& key)
{return _EraseR(_root, key);
}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;del = nullptr;return true;}
}

时间复杂度

二叉搜索树的操作时间复杂度：在O(logN)和O(N)之间。
画图解释时间复杂度：

源码（整体）

非递归

//非递归
namespace key
{//二叉树节点//节点使用struct，默认public访问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);}//插入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->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}//查找bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;}//删除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  //找到了要删除的值{//分情况//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{parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;cur = nullptr;return true;}}return false;}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}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->_tight);return copyRoot;}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root;};
}

递归

//递归
namespace keyR
{//二叉树节点//节点使用struct，默认public访问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);}//插入bool InsertR(const K& key){return _InsertR(_root, key);}//查找bool FindR(const K& key){return _FindR(_root, key);}//删除bool EraseR(const K& key){return _EraseR(_root, key);}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}private://在root添加引用很关键，要不然得是二级指针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);elsereturn false;}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;del = nullptr;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);elsereturn true;}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* copyRoot = new Node(root->_key);copyRoot->_left = CopyRoot(root->_left);copyRoot->_right = CopyRoot(root->_right);return copyRoot;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root;};
}

KV模型

直接贴出源码：

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){}BSTree(const BSTree<K, V>& t){_root = Copy(t._root);}BSTree<K, V>& operator=(BSTree<K, V> t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}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 = 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;}}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* copyRoot = new Node(root->_key, root->_value);copyRoot->_left = Copy(root->_left);copyRoot->_right = Copy(root->_right);return copyRoot;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}Node* _FindR(Node* root, const K& key){if (root == nullptr)return nullptr;if (root->_key > key){return _FindR(root->_left, key);}else if (root->_key < key){return _FindR(root->_right, key);}else{return root;}}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->_left, key, value);}else if (root->_key < key){return _InsertR(root->_right, key, value);}else{return false;}}private:Node* _root;};}