本期内容我们讲解二叉树的进阶知识，没有看过之前内容的小伙伴建议先看往期内容

二叉树-----补充_KLZUQ的博客-CSDN博客

目录

二叉搜索树 

代码实现

基础框架

Insert

Find

Erase

析构函数

拷贝构造

赋值

二叉搜索树的应用

全部代码

---

二叉搜索树 

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

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

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

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

 由于结构特性，二叉搜索树很适合查找数据，那它最多查找多少次呢？高度次吗？

其实不是的，二叉搜索树是可能会有右边这种情况的，时间复杂度是O(N)

 这其实是不好的，后面我们会讲AVL树和红黑树，他们的时间复杂度是O(longN)

话不多说，下面我们来实现二叉搜索树

代码实现

基础框架

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){}
private:Node* _root;
};

我们先写出基本框架，接着我们来实现插入

Insert

假设我们有这样一棵树，我们要插入11，13和16，该怎么办呢？我们将11和root节点对比，11比8大，应该在右边，继续对比11和10，比10大，在右边，11比14小，在左边，比13小，在左边

就成了这个样子，再看13，我们对比后发现树里面已经有13了，所以插入失败，最后看16，16比14大，链接在14的右边即可

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

我们先用循环来实现

下面为了测试，我们写一个中序遍历

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

我们写成子函数是因为我们在调用时还得传root，比如封装写成子函数，这样我们就不用传了，下面进行测试

 没有问题，中序遍历出来是有序的

bool InsertR(const K& key){return _InsertR(_root, key);}
private:bool _InsertR(Node*& root, const K& key){if (root == nullptr)//因为引用，所以下面可以直接new{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;}}

我们再看递归版本的，递归版本里参数加了引用，这个引用可以让我们在插入节点时不用找该节点的父亲节点，可谓是神之一手 

Find

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

find也非常简单

bool FindR(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->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;}}

还有递归版本的，我们再把子函数写成私有的 

Erase

删除是一个重点，我们有这样一棵树，假设我们要删除7，14和3

7是叶子节点，删除后再把6的右置为空即可，14也还好说，它只有一个孩子，我们可以让10的右节点指向13，最麻烦的是3，我们该如何删除3呢？这里就要用到替换法，用3的左子树的最大节点或者右子树的最小节点来替换，一棵树的最大节点是这棵树的最右边的节点，所以左子树的最大节点很好找，最小的节点就是最左边的，所以右子树的最小节点也很好找

bool Erase(const K& key){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//找到了{//左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}		}//右为空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;}}			}//左右都不为空else{//找替代节点Node* parent = cur;//这里不能给空，防止leftMax是根节点的左子树的第一个节点Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_left;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;}

删除要考虑的情况非常多，大家一定要画图才能理解

 大家用这几张图画一画，结合代码，里面的坑是非常多的 

下面我们测试一下

没有问题，大家测试时再把整棵树删空测试一下

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

我们再看递归版本，这里同样使用了引用，可以方便很多，大家画图对照一下就可以理解

下面我们再完成一下析构函数

析构函数

~BSTree(){Destroy(_root);}
void Destroy(Node*& root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}

也是同样使用引用，为了方便置空

拷贝构造

BSTree(const BSTree<K>& t){_root = Copy(t._root);}
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;}

拷贝构造这里是不能调用insert的，因为任何顺序的插入都不能保证和原来树的一样，大家可以试一试，而我们这样写拷贝构造就可以解决问题

赋值

BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}

赋值的话我们直接用现代写法即可

二叉搜索树的应用

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

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

以词库中所有单词集合中的每个单词作为 key ，构建一棵二叉搜索树

在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即 <Key, Value> 的键值对 。该种方式在现实生活中非常常见：

比如 英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英

文单词与其对应的中文 <word, chinese> 就构成一种键值对；

再比如 统计单词次数 ，统计成功后，给定单词就可快速找到其出现的次数， 单词与其出

现次数就是 <word, count> 就构成一种键值对 。

 下面我们修改我们上面的程序，把它变成KV的

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)//因为引用，所以下面可以直接new{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;};

这里我删除了一些，下面我们来进行测试

这里我们模拟一个字典 

还有统计水果出现的次数，没有出现的水果我们存进去，出现的让value++

全部代码

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{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->_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;}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;}bool Erase(const K& key){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//找到了{//左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}//右为空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;}}}//左右都不为空else{//找替代节点Node* parent = cur;//这里不能给空，防止leftMax是根节点的左子树的第一个节点Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_left;}swap(cur->_key, leftMax->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;}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: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;}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){if (root == nullptr)//因为引用，所以下面可以直接new{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 == NULL){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root;};void Test(){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.Erase(e);}t.InOrder();}void Test2(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t;for (auto e : a){t.Insert(e);}t.InOrder();BSTree<int> t1(t);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{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)//因为引用，所以下面可以直接new{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 test(){BSTree<string, string> dict;dict.InsertR("insert", "插入");dict.InsertR("right", "右边");dict.InsertR("sort", "排序");dict.InsertR("left", "左边");dict.InsertR("date", "日期");string str;while (cin >> str){BSTreeNode<string, string>* ret = dict.FindR(str);if (ret){cout << ret->_value << endl;}else{cout << "无此单词" << endl;}}}void test2(){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();}
}

以上即为本期全部内容，希望大家可以有所收获

如有错误，还请指正