网站抓取压力高重庆seo技术分享
目录
一、二叉搜索树的定义
二、二叉搜索树的实现：
1、树节点的创建--BSTreeNode
2、二叉搜索树的基本框架--BSTree
3、插入节点--Insert
4、中序遍历--InOrder
5、 查找--Find
6、 删除--erase
完整代码：
三、二叉搜索树的应用
1、key的模型 ：判断在不在
2、key/value的模型：通过key找value
key/value的应用场景
应用场景1--中英文互译
应用场景2--统计水果出现次数
四、二叉搜索树性能分析
一、二叉搜索树的定义
二叉搜索树（也称为搜索二叉树）又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
二、二叉搜索树的实现：
这里最好不用递归，递归比非递归更复杂，故用非递归实现
分两个文件：
BSTree.hpp(因为要用模板实现，而模板的实现和声明要放在一起的，若用模板实现就可用.hpp为后缀和 Test.c
1、树节点的创建--BSTreeNode
树是由节点组成的，故应写个BSTreeNode用来表示每个树节点，_left表示左指针，_right表示右指针，还有一个位置用来存值_key，因为无法确定存的是什么类型的值，故用模板来实现通用，设置成struct是因为树的节点对外是公开的，外部都可以访问的
template<class K> struct BSTreeNode {BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key; };
2、二叉搜索树的基本框架--BSTree
对于树的成员变量，一个根节点即可
template<class K> class BSTree //Binary Search Tree {typedef BSTreeNode<K> Node; public:private:Node* _root = nullptr;可以直接定义,就一个成员变量，无需写个构造函数 };
3、插入节点--Insert
这个函数需要有返回值的，以bool作为返回类型，因为这棵树中不允许数据冗余，即不能出现相同的数据。
插入就是用性质：左子树的值都比当前根节点的值小，右子树的值都比当前根节点的值大
若插入一个数据key，从根节点（用cur指针来表示当前位置）开始往下比就好了
①、如果key比当前节点的值大，那就接着往右走
②、如果key比当前节点的值小，那就接着往左走
对于①②直到找到一个空位置插入即可
③、如果走的过程中遇到相等的值，说明该key值不能插入，但要注意一个条件，如果这棵树本来就为空，那就直接把数据插入到根节点中就好
链接问题：
插入一个节点，必然要与树链接，若不链接，这个节点就是个临时数据，出了作用域就没了，但若把他链接到树上就能正常访问了，故这里采用双指针法，cur表示当前节点，再定义一个parent，每次cur走之前，先把cur赋值给parent，这样最后cur走到空了，parent能记录到cur的上一位置，而这上一位置就是要找的cur要与其链接的位置，至于cur插入到parent的左还是右，若值比parent的值大，则插到右边，小，则插到左边
bool Insert(const K& key) {if (_root == nullptr){//若为空树，就给它一个节点_root = new Node(key);//new是开空间+初始化，所以要调用构造函数，你要写的return true;}Node* cur = _root;//从根节点开始比较Node* parent = nullptr;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);//向这个空位置插入数据//利用parent的位置与cur连接if (parent->_key > key)parent->_left = cur;//比根节点小，链接到左边elseparent->_right = cur;//比根节点大，链接到右边return true; }
4、中序遍历--InOrder
这里用两个成员函数实现，为什么？中序遍历你要传树的根节点，而根节点就是类的私有成员变量，而你的中序遍历一定是在类外使用的，无法直接访问_root
解决方法：
法一、写个成员函数获得一下_root是可以的
法二、用两个成员函数，即用InOrder来传这个_root，成员函数访问你_root一定是没问题的，那么_InOrder直接用来中序遍历即可，调用时直接调用InOrder即可
void InOrder() {_InOrder(_root);cout << endl; } //下面的可以放到private里面 void _InOrder(Node* root) {if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right); }下面利用写的插入和中序遍历测试下代码：
void testTree() {BSTree<int> t;int a[] = { 5,3,4,1,7,8,2,6,0,9 };for (auto e : a){//数组是可以用迭代器来遍历的t.Insert(e);//插入节点到树中}t.InOrder();//中序遍历 }
5、 查找--Find
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;//走到空还没找到，说明没有此数据 }
6、 删除--erase
1、观察现象：
删除2，让父亲指向我的右，删除8，让父亲指向我的右，5不好删，因为他有两个孩子
左为空，父亲指向我的右，右为空，父亲指向我的左，叶子节点可以归纳为左为空（右为空也行，这里就假设用左为空），因为叶子的左右都为空，它父亲的指向他的左还是右均可
左为空，
2、细节考虑
A、待删除节点左为空或右为空的情况（叶子结点可归类为左为空）
删除一个节点是让其父亲（Parent）的左指针还是右指针指向cur？
【若cur的左子树为空】看cur到底是父亲的左子树还是右子树，若是父亲的左子树，则让父亲的左指向cur右子树 ，若为右子树，则让父亲的右指向cur的右子树
【若cur的右子树为空】若是父亲的左子树，则让父亲的左指向cur左子树 ，若为右子树，则让父亲的右指向cur的左子树
B、待删除节点左右都不为空的情况
节点的左右子树都不为空，不能直接删除，直接删除会导致二叉搜索树混乱，故用替代法删除。
因为要符合左子树都比根节点小，右子树都比根节点大的性质，故要找左子树的最大节点或右子树的最小节点去替代它。（左子树最右边的节点是左子树最大节点，右子树的最左边的节点是右子树最小节点）【故假设我们下面就用右子树的最小节点】
比如删除7，可以用8（7的右子树的最左节点）来替代，那么替换完后，我删除这个7就可以直接删了，那么这个问题又转换到了被删除节点的左为空或者右为空，因为替换节点一定要么是最左边的节点要么是最右边的节点（不一定是叶子结点），那这个替换节点的左右子树一定存在左子树右子树有个为空的情况
所以删除 分三种情况
问题1：
删除一定要找到父亲，因为删完了还存在链接关系，所以单单用find去找是不行的，他找不到他的父亲节点，故还是用双指针法
因为链接问题，所以删除关键看cur是在父亲的左还是右，而不是看cur的左边为空还是右边为空，这不符合所有场景
问题2：
最左节点不一定就是叶子结点，比如这里删除7，它的右子树的最左节点是8，则8替换完7后，8要被删除，他被删除完后，parent的右指针要指向rightMin的右节点
问题3：
parent初始值不能为nullptr，若删除7【che指针指向7】，因为要删除cur，Rightmin刚上来就=8，Rightmin的左子树为空，while循环都没进去，而parent它还是nullptr，那后续的链接肯定会有问题的，所以parent应该一上来就赋值为cur，而不是nullptr
问题4：
若要删除的节点是根节点，也要特别考虑，左为空，则让根=它的右节点，右为空，则让根=它的左节点
bool Erase(const K& key)
{Node* cur = _root;Node* parent = nullptr;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->_left == cur)parent->_left = cur->_right;//cur在父亲的左边，就让父亲的左指向cur的左elseparent->_right = cur->_right;//cur在父亲的右边，就让父亲的右指向cur的右}delete cur;}//2.右为空else if (cur->_right == nullptr){if (cur == _root)_root = cur->_left;else{if (parent->_right == cur)parent->_right = cur->_left;//cur在父亲的右边，就让父亲的右指向cur的左elseparent->_left = cur->_left;//cur在父亲的左边，就让父亲的左指向cur的右}delete cur;}//3.左右都不为空else{//找左子树的最右节点或右子树的最小节点去替代//这里用右子树的最小节点来替代Node* parent = cur;Node* Rightmin = cur->_right;//若用右树的最小节点，即右树最左节点while (Rightmin->_left){//最左节点的左子树一定为空，故为判断条件parent = Rightmin;//替换节点不一定是叶子结点，故还要用parent来链接Rightmin = Rightmin->_left;}cur->_key = Rightmin->_key;//用cur的值来替代//转换成删除Rightmin//若它是parent的右子树，则父亲的右指向它的右//若它是parent的左子树，则父亲的左指向它的左if (Rightmin == parent->_left)parent->_left = Rightmin->_right;elseparent->_right = Rightmin->_right;delete Rightmin;}return true;}}return false;//cur都为空了还没找到，则该数据不存在
}完整代码：
BSTree.hpp
#pragma once
#include<iostream>
using namespace std;template<class K>
struct BSTreeNode
{BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;};
template<class K>
class BSTree //Binary Search Tree
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key){if (_root == nullptr){//若为空树，就给它一个节点_root = new Node(key);//new是开空间+初始化，所以要调用构造函数，你要写的return true;}Node* cur = _root;//从根节点开始比较Node* parent = nullptr;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);//向这个空位置插入数据//利用parent的位置与cur连接if (parent->_key > key)parent->_left = cur;//比根节点小，链接到左边elseparent->_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* cur = _root;Node* parent = nullptr;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->_left == cur)parent->_left = cur->_right;//cur在父亲的左边，就让父亲的左指向cur的左elseparent->_right = cur->_right;//cur在父亲的右边，就让父亲的右指向cur的右}delete cur;}//2.右为空else if (cur->_right == nullptr){if (cur == _root)_root = cur->_left;else{if (parent->_right == cur)parent->_right = cur->_left;//cur在父亲的右边，就让父亲的右指向cur的左elseparent->_left = cur->_left;//cur在父亲的左边，就让父亲的左指向cur的右}delete cur;}//3.左右都不为空else{//找左子树的最右节点或右子树的最小节点去替代//这里用右子树的最小节点来替代Node* parent = cur;Node* Rightmin = cur->_right;//若用右树的最小节点，即右树最左节点while (Rightmin->_left){//最左节点的左子树一定为空，故为判断条件parent = Rightmin;//替换节点不一定是叶子结点，故还要用parent来链接Rightmin = Rightmin->_left;}cur->_key = Rightmin->_key;//用cur的值来替代//转换成删除Rightmin//若它是parent的右子树，则父亲的右指向它的右//若它是parent的左子树，则父亲的左指向它的左if (Rightmin == parent->_left)parent->_left = Rightmin->_right;elseparent->_right = Rightmin->_right;delete Rightmin;}return true;}}return false;//cur都为空了还没找到，则该数据不存在}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 = nullptr;//可以直接定义,就一个成员变量，无需写个构造函数
};void testTree()
{BSTree<int> t;int a[] = { 5,3,4,1,7,8,2,6,0,9 };for (auto e : a){//数组是可以用迭代器来遍历的t.Insert(e);//插入节点到树中}t.InOrder();//中序遍历
}Test.cpp
#include"BSTree.hpp"int main()
{testTree();return 0;
}三、二叉搜索树的应用
搜索树使用场景：
1、key的模型 ：判断在不在
比如进入校园要刷校园卡，卡本质里面有芯片，芯片上存储信息，把学校所有学员的信息存到二叉搜索树（因为他的查找效率很高），然后用机器扫描卡，看你卡的信息是否在我的树中，在就让你进
2、key/value的模型：通过key找value
①、高铁刷身份证
买了票就能进站，刷身份证读的是身份证号码，【key就是身份证，value就是票的信息】然后通过身份证到后台服务器查是否有票的信息，是否是这个车站，这个车次等等，即通过身份证找value
②、中英文互译
中文就是key，英文就是value，即通过中文找英文或通过英文找中文。
③、统计次数
统计次数，即通过一个值找另一个值，用搜索树实现的原因是二叉搜索树的效率高，搜索快
key/value模型的实现只需在我们实现的二叉搜索树中改动一下代码即可，即节点里面除了有key，还有value，但是比较大小的过程还是用key来比较，和value没关系，找到了key就相当于找到了value，因为两者在同一节点中，还要修改的就是Find函数，返回值变成返回节点的指针而不是bool值，因为这样返回的节点既有key又有value
注意：
对于搜索树的修改，搜索树中key是不允许修改的
如果是kv模型的搜索树，可以修改value，但不能修改key，就是因为你改了key就不一定满足二叉搜索树的条件了
kv模型的完整代码：
BSTree.hpp :
//key/value模型
#include<iostream>
#include<string>
using namespace std;template<class K, class V>
struct BSTreeNode
{BSTreeNode(const K& key,const V& value):_key(key),_value(value), _left(nullptr), _right(nullptr){}BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _value;};
template<class K, class V>
class BSTree //Binary Search Tree
{typedef BSTreeNode<K,V> Node;
public:bool Insert(const K& key, const V& value){if (_root == nullptr){//若为空树，就给它一个节点_root = new Node(key, value);//new是开空间+初始化，所以要调用构造函数，你要写的return true;}Node* cur = _root;//从根节点开始比较Node* parent = nullptr;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,value);//向这个空位置插入数据//利用parent的位置与cur连接if (parent->_key > key)parent->_left = cur;//比根节点小，链接到左边elseparent->_right = cur;//比根节点大，链接到右边return true;}Node* 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 cur;//说明相等，则找到了，返回真}}return nullptr;}bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;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->_left == cur)parent->_left = cur->_right;//cur在父亲的左边，就让父亲的左指向cur的左elseparent->_right = cur->_right;//cur在父亲的右边，就让父亲的右指向cur的右}delete cur;}//2.右为空else if (cur->_right == nullptr){if (cur == _root)_root = cur->_left;else{if (parent->_right == cur)parent->_right = cur->_left;//cur在父亲的右边，就让父亲的右指向cur的左elseparent->_left = cur->_left;//cur在父亲的左边，就让父亲的左指向cur的右}delete cur;}//3.左右都不为空else{//找左子树的最右节点或右子树的最小节点去替代//这里用右子树的最小节点来替代Node* parent = cur;Node* Rightmin = cur->_right;//若用右树的最小节点，即右树最左节点while (Rightmin->_left){//最左节点的左子树一定为空，故为判断条件parent = Rightmin;//替换节点不一定是叶子结点，故还要用parent来链接Rightmin = Rightmin->_left;}cur->_key = Rightmin->_key;//用cur的值来替代//转换成删除Rightmin//若它是parent的右子树，则父亲的右指向它的右//若它是parent的左子树，则父亲的左指向它的左if (Rightmin == parent->_left)parent->_left = Rightmin->_right;elseparent->_right = Rightmin->_right;delete Rightmin;}return true;}}return false;//cur都为空了还没找到，则该数据不存在}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 = nullptr;//可以直接定义,就一个成员变量，无需写个构造函数
};void testTree1()
{BSTree<string, string>dict;//字典dict.Insert("sort", "排序");dict.Insert("polynomial", "多项式");dict.Insert("femininity", "女性");string str;while (cin >> str){BSTreeNode<string, string>* ret = dict.Find(str);if (ret){cout << ret->_value << endl;}else{cout << "无此单词" << endl;}}
}void testTree2()
{string strArr[] = { "西瓜","西瓜","香蕉","樱桃","西瓜","西瓜","香蕉" };BSTree<string, int> countTree;//key是string，value是intfor (auto str : strArr){BSTreeNode<string, int>* ret = countTree.Find(str);if (ret == nullptr){//第一次出现，就插入这个水果，出现一次,因为一开始树为空countTree.Insert(str, 1);}else{//出现过了，就++次数ret->_value++;}}countTree.InOrder();
}Test.cpp
#include"BSTree.hpp"int main()
{//testTree1();testTree2();return 0;
}key/value的应用场景
应用场景1--中英文互译
key/value模型测试下面代码逻辑（中英文互译）
应用场景2--统计水果出现次数
有一堆水果，请你统计水果出现的次数
四、二叉搜索树性能分析
如果插入的数据是有序的或者接近有序的，那么搜索树效率就完全没办法保障
如：1 2 3 4 5 6 7 8，对于树就变成了单支树，搜索树的效率最坏的情况下是O（N）
如何解决？平衡树1、AVLTree 2、红黑树
