总言

  二叉树进阶：主要介绍二叉搜索树相关内容。

  
  

1、基本介绍

1.1、什么是二叉搜索树

  1）、概念与性质介绍
  二叉搜索树又称二叉排序树，它可以是一棵空树，也可以是具有以下性质的二叉树:
  1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
  2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
  3、它的左右子树也分别为二叉搜索树。

  
  
  2）、二叉搜索树的这种性质为其来带什么优势？
  在查找效率方面，由于二叉搜索树左子树都比根小，右子树都比根大，这种一分为二的效果在查找方面提供了效率，时间复杂度为O(h)，其中h为高度。
  
  
  3）、一些需要注意的点
  1、二叉搜索树是不允许有重复的值出现的
  2、增删查改中，二叉搜索树不允许随意修改，因此在功能实现上，我们只进行增删查的操作。
  
  

2、相关实现

2.1、基本框架

2.1.1、如何构建二叉树单节点

  创建单个节点的结构，与之前链式二叉树中内容基本一致，每个结点由数据域和左右指针域组成，只是这里我们借助了模板。

template<class K>
class BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;
};

  
  由于后续需求，我们在这里先将其构造函数写上。注意对参数的理解：const K& key = K()。

template<class K>
struct BSTreeNode
{BSTreeNode(const K& key = K()):_left(nullptr),_right(nullptr),_key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;
};

  由后续内容，BSTreeNode会在类外调用，故而我们可将其实现为struct。
  
  

2.1.2、如何定义一个二叉搜索树

  大致框架不变，只是加入了类与模板，另外需要注意它有一个根节点Node* _root = nullptr;，这里给根节点赋了一个缺省值，实际作用于初始化列表中。

template<class K>
class BinarySearchTree
{typedef BinarySearchTree<K> BSTree;typedef BSTreeNode<K> Node;//……private:Node* _root = nullptr;};

  接下来是完善其各个成员函数。
  
  
  

2.2、非递归实现：插入、查找、删除

2.2.1、二叉搜索树·插入：Insert

  1）、基本说明
  需求说明： 在二叉搜索树中插入一个新的值，保持插入前后，仍旧满足二叉搜索树的性质（左子树比根小，右子树比根大）。
  
  根据上述需求，需要思考：
  1、如何找到相应的插入位置？
  2、如何将新增节点与原先二叉树链接上？
  
  对于问题一：
  a、若树为空，则直接新增节点，赋值给root；
  b、若树不为空，从根节点开始，依次让当前节点值与待插入值val比较，若待插入值大于当前节点值，则说明其要放在当前节点值右侧子树中；若小于，则说明其要放在当前节点值左侧子树中；若等于，则说明二叉搜索树中已存在该值，不必插入（二叉搜索树不允许）；
  c、如此重复判断比较，直到当前节点值与待插入值相同时返回，或者当前节点左孩子/右孩子为空时，插入。

  
  insert实现1.0：

	bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;while (cur){if (key > cur->_key)//当前节点值比待插入值小{cur = cur->_right;}else if (key < cur->_key)//当前节点值比待插入值大{cur = cur->_left;}else//二者相同，直接返回{return false;}}//当while循环结束时，cur==nullptr，此时插入相应值cur = new Node(key);return true;}

  
  对于问题二：
  a、观察上述代码，我们只完成在相应位置新增节点，由于cur是临时变量，出了函数作用域就销毁，故该节点与原先二叉树并没有实际链接上。这也是我们上述要思考的问题之一，如何将新增节点与原先二叉树链接上？

  解决方案如下： 记录cur的父节点。需要注意，这里要判断新增的cur对于其parent而言是左孩子还是右孩子。

  
  insert实现2.0：

template<class K>
class BinarySearchTree
{
public:typedef BinarySearchTree<K> BSTree;typedef BSTreeNode<K> Node;bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else//二者相同，直接返回{return false;}}//当while循环结束时，cur==nullptr，此时插入相应值cur = new Node(key);//与原二叉树链接if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;return true;}//……};

  注意事项：
  我们说过，最后链接时，需要注意parent和cur的关系，这里我们是用parent->_key与cur->_key进行左右子树判断的。这样判断出的结果能满足二叉搜索树。

		if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;

  一种错误写法如下：不能直接用父节点左右孩子是否为空进行判断。举例：左孩子为空不一定满足待插入值一定比父节点值小。此外，我们还有可能遇到parent左右孩子都为空时，这时候也不是说可以左右孩子任意链接，我们始终都要保持左比父小、右比父大的特性。

		if (parent->_left == nullptr)parent->_left = cur;elseparent->_right = cur;

  
  
  

2.2.2、二叉搜索树·中序遍历：InOrder

  1）、基本说明
  实现说明：为二叉搜索树写一个中序遍历函数，可以方便我们遍历查看二叉搜索树的值。

  问题：为什么选择中序遍历，而不是前序或者后续？
  回答： 一个直接原因是二叉搜索树的性质，左子树都比根小，右子树都比根大，那么我们在中序遍历时，访问顺序是左子树、根、右子树，就能直观清晰的看到一个有序的二叉搜索树，便于后续观察与检测。
  
  相关实现如下：

template<class K>
class BinarySearchTree
{
public://……void InOrder(){_InOrder(_root);}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}//……};

  说明：InOrder和_InOrder，为什么要进行一个封装操作？
  回答：假如我们直接使用_InOrder，其有一参数root需要我们传递根节点，但是_root为私有成员，我们在类外无法直接调用，所需需要想办法解决传参问题。

  
  解决方案：
  1、在类中实现一个getroot()函数，参考日期类获取年、月、日。
  2、将test01设置为BinarySearchTree的友元函数，可以访问类的私有成员。（不推荐）
  3、如上述，再封装一层，我们直接调用公有的InOerder。
  
  
  2）、验证插入Insert
  相关代码如下：

void test01()
{int a[] = { 8,3,1,10,6,4,7,14,13,14,13,7,4 };BinarySearchTree<int> tree;for (auto e : a){tree.Insert(e);}tree.InOrder();
}

  验证结果如下：事实上这里InOrder与Insert结合，有天然去重和排序的效果。

  
  
  
  

2.2.3、二叉搜索树·查找：Find

  相关实现如下：

	bool Find(const K& key){Node* cur = _root;//此处不用单独判断_root是否为空while (cur){if (key < cur->_key)cur = cur->_left;else if (key > cur->_key)cur = cur->_right;elsereturn true;}return false;}

  
  
  

2.2.4、二叉搜索树·删除：Erase

  1）、思路分析
  情况一：要删除的结点无孩子结点/单孩子结点
  处理方法：直接删除，但需要注意将待删除结点的孩子结点与其父结点建立新联系。

  要删除的结点有左、右孩子结点时：替换法，从左右子树中找出一个适合的值，进行替换，然后删除。
  1、可有以下两种处理方法：
    a、找左子树中最大值，这样能保证交换后，根节点仍旧大于其左子树、小于其右子树。左子树中最大值即其最右边的值。
    b、找右子树中最小值，这样能保证交换后，根节点仍旧大于其左子树、小于其右子树。右子树中最小值即其最左边的值。
  2、找到后与待删节点替换，这样对于待删节点，其处理方法和上述单结点/无孩子结点一致。（原因：如果替换后仍旧为双孩子，那么就不满足左子树最右、右子树最左的条件，也就不是我们要寻找的值。）

  
  
  2）、写法如下
  1、先寻找待删除结点：

	bool Erase(const K& key){//查找key值Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key)//待删除值比当前值大，向右子树找{parent = cur;cur = cur->_right;}else if (key < cur->_key)//待删除值比当前值小，向左子树找{parent = cur;cur = cur->_left;}else{//key==cur->_key,找到则删除n}}//找不到：return false;}

  
  2、对于单孩子结点、无孩子结点的情况：

				//处理单结点/无结点if (cur->_left == nullptr)//待删结点的左孩子为空，说明其只有右孩子或者无左右孩子{if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left)//cur为parent的左孩子时{parent->_left = cur->_right;}else//cur为parent的右孩子时{parent->_right = cur->_right;}}}else if (cur->_right == nullptr)//待删结点的右孩子为空，说明其只有左孩子或者无左右孩子{if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left)//cur为parent的左孩子时{parent->_left = cur->_left;}else/cur为parent的右孩子时{parent->_right = cur->_left;}}}

  细节理解： 以下情况是为了解决上述情况中，待删结点为根节点时：

					if (cur == _root){_root = cur->_right;}if (cur == _root){_root = cur->_left;}

  
  
  
  
  3、对于待删结点存在左右孩子时：

				else//左右孩子都存在时：以找右子树最小值为替换值，即先找到右子树最左结点{Node* Min = cur->_right;Node* MinParent = cur;while (Min->_left){MinParent = Min;Min = Min->_left;}//找到后，交换值std::swap(Min->_key, cur->_key);//右树最左值，其孩子结点只能是右孩子或直接无孩子结点，它不可能存在左孩子if (MinParent->_left == Min){MinParent->_left = Min->_right;}else{MinParent->_right = Min->_right;}delete Min;}

  细节理解：

					if (MinParent->_left == Min){MinParent->_left = Min->_right;}else{MinParent->_right = Min->_right;}

  
  
  
  
  3）、整体情况和测试
  整体代码实现如下：

	bool Erase(const K& key){//查找key值Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else//key==cur->_key,找到则删除{//处理单结点/无结点if (cur->_left == nullptr)//左孩子为空，右孩子有或无{if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left)//cur为parent的左孩子时{parent->_left = cur->_right;}else//cur为parent的右孩子时{parent->_right = cur->_right;}}}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}}else//左右孩子都存在时：以找右子树最小值为例，即右子树最左结点{Node* Min = cur->_right;Node* MinParent = cur;while (Min->_left){MinParent = Min;Min = Min->_left;}//找到后，交换值，std::swap(Min->_key, cur->_key);//右树最左值，其子节点只能是右孩子或直接无孩子结点，不可能是左孩子if (MinParent->_left == Min){MinParent->_left = Min->_right;}else{MinParent->_right = Min->_right;}delete Min;}return true;}}//找不到：return false;}

  测试如下：

void test02()
{int a[] = { 8,3,1,10,6,4,7,14,13};BinarySearchTree<int> tree;for (auto e : a){tree.Insert(e);}tree.InOrder();cout << endl;cout << endl;cout<< "测试Find：" << endl;cout << tree.Find(8) << endl;cout << tree.Find(13) << endl;cout << endl;cout << "测试Erase：" << endl;for (auto e : a){tree.Erase(e);tree.InOrder();cout << endl;}cout << endl;
}

  
  
  
  

2.3、递归实现：插入、查找、删除

2.3.1、二叉搜索树·递归查找：FindR

  同理，使用递归需要涉及根节点，其为私有成员，因此我们在这进行一层封装。相关实现如下：
  1、若递归到当前结点为空，则二叉树中没有该值；
  2、若目标值比当前结点值大，则到其右子树找；若目标值比当前结点小，则到其左子树找；若目标值等于当前结点值，则说明找到。
  

public:二叉树·递归查找·封装bool FindR(const K& key){return _FindR(_root,key);}private:二叉树·递归查找bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (key < root->_key)_FindR(root->_left, key);else if (key > root->_key)_FindR(root->_right, key);elsereturn true;}

  结果验证如下：

void test03()
{int a[] = { 8,3,1,10,6,4,7,14,13 };BinarySearchTree<int> tree;for (auto e : a){tree.Insert(e);}tree.InOrder();cout << endl;cout << tree.FindR(14) << endl;cout << tree.FindR(12) << endl;
}

  
  

2.3.2、二叉搜索树·递归插入：InsertR

  相关实现如下：
  1、若当前结点为空，说明我们找到了合适的插入位置；
  2、若待插入值比当前结点值大，则递归来到右子树寻找适合位置；若待插入值比当前结点值小，则递归来到左子树寻找适合位置。
  3、若待插入值和当前结点值相等，根据二叉搜索树元素不重复特性，直接返回不插入值。

	二叉树·递归插入·封装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 (key > root->_key)_InsertR(root->_right, key);else if (key < root->_key)_InsertR(root->_left, key);elsereturn false;}

  细节理解：Node*& root,，为什么这里对root进行了引用处理?
  回答： 根据上述递归，最后我们找到合适的插入位置时，root==nullptr，此时我们通过new新增结点，但这里存在一个问题，如果是bool _InsertR(Node* root, const K& key)，root形参为临时变量，在层层递归中并不能与我们实际的二叉树建立联系。因此，这里使用引用，主要目的是新增结点后，要让其与原先二叉树链接上。

  
  
  验证结果如下：

  

void test04()
{int a[] = { 8,3,1,10,6,4,7,14,13,13,14,7,4 };BinarySearchTree<int> tree;for (auto e : a){tree.InsertR(e);}tree.InOrder();cout << endl;
}

  
  
  
  

2.3.3、二叉搜索树·递归删除：EraseR

  相关实现如下：
  1、若当前结点为空，则说明该树中无待删除值；
  2、若待删除值比当前结点值大，则递归来到右子树寻找树中是否有待删除值；若待删除值比当前结点值小，则递归来到左子树寻找树中是否有待删除值。
  3、若待删除值和当前结点值相等，说明找到待删除值所在结点。此时面临的删除情况与非递归时一致。

private:二叉树·递归删除·封装bool EraseR(const K& key){return _EraseR(_root, key);}private:二叉树·递归删除·封装bool _EraseR(Node*& root,const K& key){//查找值if (root == nullptr)return false;if (key > root->_key)_EraseR(root->_right, key);else if (key < root->_key)_EraseR(root->_left, key);else//root->key==key，找到待删结点，删除面临的情况和非递归一致{Node* tmp = root;//只有单孩子结点、无孩子结点if (root->_left == nullptr)root = root->_right;else if (root->_right == nullptr)root = root->_left;else//待删结点有左右两孩子结点，替换法，此处以找右子树的最小值做替换{//右子树最小值即右子树最左值，其特点是没有左孩子，可能有右孩子Node* Min = root->_right;while (Min->_left)Min = Min->_left;std::swap(Min->_key, root->_key);return _EraseR(root->_right, key);//错误写法：Erase(key),替换后已经不符合搜索二叉树了。}delete tmp;return true;}}

  
  演示结果如下：

  
  
  
  

2.4、基本成员函数：构造、拷贝、赋值、析构

2.4.1、析构：~BinarySearchTree()、销毁：_Destory

  说明：由于二叉搜索树中，每个结点都是new动态申请出来的，因此，析构时需要对每结点都进行处理，这里我们顺便实现一个_Destory函数，其作用是释放每个结点。

public：二叉树·析构~BinarySearchTree(){_Destory();}private://二叉树·销毁void _Destory(Node*& root){if (root == nullptr)return;_Destory(root->_left);//销毁孩子结点_Destory(root->_right);delete root;//销毁根结点root = nullptr;}

  Node*& root，这里传递引用，是因为后续root = nullptr;，实参root要置空，则不能只是传值传参。

  若不对其做处理，情况如下：

	void _Destory(Node* root){if (root == nullptr)return;_Destory(root->_left);//销毁孩子结点_Destory(root->_right);delete root;//销毁根结点}

  
  

2.4.2、拷贝构造、构造：BinarySearchTree

  说明：如何用已经生成的二叉搜索树去构造一个新的二叉搜索树呢？首先，如果使用InOerder+Insert结合，遍历被拷贝的二叉搜索树，然后将其每一个值插入，这种方法行不通，因为二叉搜索树的生成依赖于其顺序。

  那么是否还有其它方法？此处我们只能遍历已经二叉搜索树，根据其每个结点，依次new新结点，并确定其左右孩子关系。
  

public:二叉树·拷贝构造BinarySearchTree(const BinarySearchTree<K>& tree){_root = _Copy(tree._root);}private://二叉树·前序拷贝Node* _Copy(Node* root){if (root == nullptr)return nullptr;Node* copyRoot = new Node(root->_key);//对当前根节点new新空间，拷贝数值copyRoot->_left=_Copy(root->_left);//对其左孩子进行拷贝copyRoot->_right = _Copy(root->_right);//对其右孩子进行拷贝return copyRoot;}

  
  上述代码如果直接运行会报错：

  这是因为我们没有实现默认的构造函数。根据相关内容，如果我们显示写构造函数，那么编译器就不会生成默认构造函数。而拷贝构造也是构造函数中的一种，相当于我们显示写了构造，故而此处缺少默认构造函数，解决方法有如下两种：

	//二叉树·构造：我们自己显示写一个默认构造函数BinarySearchTree(){}//二叉树·构造：使用关键字强制生成默认构造BinarySearchTree() = default;

  
  
  
  

2.4.3、赋值

  

	二叉树·赋值运算符重载BinarySearchTree<K>& operator=(BinarySearchTree<K> tree){std::swap(_root, tree._root);return *this;}

  
  
  验证代码如下:

void test06()
{int a[] = { 8,3,1,10,6,4,7,14,13 };BinarySearchTree<int> tree;for (auto e : a){tree.Insert(e);}tree.InOrder();cout << endl;//验证拷贝构造BinarySearchTree<int> tree2(tree);tree2.InOrder();cout << endl;//验证赋值运算符重载BinarySearchTree<int> tree3;tree3 = tree;tree3.InOrder();cout << endl;
}

  验证结果如下：

  
  
  
  

3、整体预览

#pragma once
#include<iostream>
using namespace std;template<class K>
struct BSTreeNode
{BSTreeNode(const K& key = K()):_left(nullptr),_right(nullptr),_key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;
};template<class K>
class BinarySearchTree
{
public://typedef BinarySearchTree<K> BSTree;typedef BSTreeNode<K> Node;二叉树插入bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key)//当前节点值比待插入值小{parent = cur;cur = cur->_right;}else if (key < cur->_key)//当前节点值比待插入值大{parent = cur;cur = cur->_left;}else//二者相同，直接返回{return false;}}//当while循环结束时，cur==nullptr，此时插入相应值cur = new Node(key);if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;//if (parent->_left == nullptr)//error//	parent->_left = cur;//else//	parent->_right = cur;return true;}二叉树查找bool Find(const K& key){//if (_root == nullptr)//	return false;Node* cur = _root;while (cur){if (key < cur->_key)cur = cur->_left;else if (key > cur->_key)cur = cur->_right;elsereturn true;}return false;}//二叉树删除bool Erase(const K& key){//查找key值Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else//key==cur->_key,找到则删除{//处理单结点/无结点if (cur->_left == nullptr)//左孩子为空，右孩子有或无{if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left)//cur为parent的左孩子时{parent->_left = cur->_right;}else//cur为parent的右孩子时{parent->_right = cur->_right;}}}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}}else//左右孩子都存在时：以找右子树最小值为例，即右子树最左结点{Node* Min = cur->_right;Node* MinParent = cur;while (Min->_left){MinParent = Min;Min = Min->_left;}//找到后，交换值，std::swap(Min->_key, cur->_key);//右树最左值，其子节点只能是右孩子或直接无孩子结点，不可能是左孩子if (MinParent->_left == Min){MinParent->_left = Min->_right;}else{MinParent->_right = Min->_right;}delete Min;}return true;}}//找不到：return false;}//void _InOrder(Node* root)//演示封装原因//{//	if (root == nullptr)//		return;//	_InOrder(root->_left);//	cout << root->_key << " ";//	_InOrder(root->_right);//}二叉树中序遍历·封装void InOrder(){_InOrder(_root);}二叉树·递归查找·封装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);}二叉树·析构~BinarySearchTree(){_Destory(_root);}//二叉树·构造//BinarySearchTree()//{}//二叉树·构造：使用关键字强制生成默认构造BinarySearchTree() = default;二叉树·拷贝构造BinarySearchTree(const BinarySearchTree<K>& tree){_root = _Copy(tree._root);}二叉树·赋值运算符重载BinarySearchTree<K>& operator=(BinarySearchTree<K> tree){std::swap(_root, tree._root);return *this;}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 _Destory(Node*& root){if (root == nullptr)return;_Destory(root->_left);//销毁孩子结点_Destory(root->_right);delete root;//销毁根结点root = nullptr;}二叉树·递归删除·封装bool _EraseR(Node*& root,const K& key){//查找值if (root == nullptr)return false;if (key > root->_key)_EraseR(root->_right, key);else if (key < root->_key)_EraseR(root->_left, key);else//root->key==key，找到待删结点，删除面临的情况和非递归一致{Node* tmp = root;//只有单孩子结点、无孩子结点if (root->_left == nullptr)root = root->_right;else if (root->_right == nullptr)root = root->_left;else//待删结点有左右两孩子结点，替换法，此处以找右子树的最小值做替换{//右子树最小值即右子树最左值，其特点是没有左孩子，可能有右孩子Node* Min = root->_right;while (Min->_left)Min = Min->_left;std::swap(Min->_key, root->_key);return _EraseR(root->_right, key);//错误写法：Erase(key),替换后已经不符合搜索二叉树了。}delete tmp;return true;}}二叉树·递归插入bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (key > root->_key)_InsertR(root->_right, key);else if (key < root->_key)_InsertR(root->_left, key);elsereturn false;}二叉树·递归查找bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (key < root->_key)_FindR(root->_left, key);else if (key > root->_key)_FindR(root->_right, key);elsereturn true;}二叉树中序遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root = nullptr;};

  
  
  
  
  

4、二叉搜索树运用说明

4.1、二叉搜索树性能简述

  1）、二叉搜索树增删查时间复杂度
  二叉搜索树增删查中，插入和删除操作都必须先查找，因此查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
  时间复杂度$O(h)$，最坏情况$h=N$（单支）。
  
  2）、针对其的改进
  平衡树：红黑树、AVL树等。
  
  

4.2、应用介绍

4.2.1、基本说明

  1）、二叉搜索树的两个模型介绍
  1、K模型：只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
  样例举例：K模型主要运用于判断关键字key在与不在。如刷卡进学校、进宿舍楼；检查一篇英文文档中单词拼写错误。
  
  
  2、KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
  样例举例：KV模型主要是通过key找对应的value。如中英字词匹配；高铁站买票刷身份证通过；统计某类事物出现次数。
  
  

4.2.2、使用举例

  1）、部分框架说明
  这里我们演示KV模型，相应的，我们需要对之前的二叉搜索树做一些修改，部分框架实现如下：简单来讲就是多加了一个模板参数value。

namespace keyvalue
{template<class K,class V>struct BSTreeNode{BSTreeNode(const K& key = K(),const V& value=V()):_left(nullptr), _right(nullptr), _key(key), _value(value){}BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _value;};template<class K,class V>class BinarySearchTree{public:typedef BSTreeNode<K,V> Node;二叉树插入bool Insert(const K& key,const V& value){if (_root == nullptr){_root = new Node(key,value);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key)//当前节点值比待插入值小{parent = cur;cur = cur->_right;}else if (key < cur->_key)//当前节点值比待插入值大{parent = cur;cur = cur->_left;}else//二者相同，直接返回{return false;}}//当while循环结束时，cur==nullptr，此时插入相应值cur = new Node(key,value);if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;return true;}二叉树查找Node* Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key)cur = cur->_left;else if (key > cur->_key)cur = cur->_right;elsereturn cur;}return cur;}//二叉树删除bool Erase(const K& key){//查找key值Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else//key==cur->_key,找到则删除{//处理单结点/无结点if (cur->_left == nullptr)//左孩子为空，右孩子有或无{if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left)//cur为parent的左孩子时{parent->_left = cur->_right;}else//cur为parent的右孩子时{parent->_right = cur->_right;}}}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}}else//左右孩子都存在时：以找右子树最小值为例，即右子树最左结点{Node* Min = cur->_right;Node* MinParent = cur;while (Min->_left){MinParent = Min;Min = Min->_left;}//找到后，交换值，std::swap(Min->_key, cur->_key);//右树最左值，其子节点只能是右孩子或直接无孩子结点，不可能是左孩子if (MinParent->_left == Min){MinParent->_left = Min->_right;}else{MinParent->_right = Min->_right;}delete Min;}return true;}}//找不到：return false;}二叉树中序遍历·封装void InOrder(){_InOrder(_root);}二叉树·析构~BinarySearchTree(){_Destory(_root);}private://二叉树·销毁void _Destory(Node*& root){if (root == nullptr)return;_Destory(root->_left);//销毁孩子结点_Destory(root->_right);delete root;//销毁根结点root = nullptr;}二叉树中序遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key <<":" << root->_value << " ";_InOrder(root->_right);}Node* _root = nullptr;};
}

  
  2）、样例演示一：输入英文，查找对应中文
  演示代码如下：

void testKV01()
{建立一个中英词典：keyvalue::BinarySearchTree<string, string> dict;dict.Insert("conceal", "v.隐藏");dict.Insert("breakdown", "n.崩溃");dict.Insert("clutch", "v.抓住");dict.Insert("philosopher", "n.哲学家");dict.Insert("stamp", "n.邮票");//查找词：给key值，获取value值string str;while (cin >> str){//记录查找的结果keyvalue::BSTreeNode<string, string>* ret = dict.Find(str);if (ret){cout << "中文: " << ret->_value << endl;}else{cout << "查无此词" << endl;}cout << endl;}
}

  
  
  
  
  2）、样例演示二：统计一段时间内不同天气出现次数
  
  演示代码如下：

void testKV02()
{//将天气存入二叉搜索树中string arr[] = { "晴","多云","晴","阴","小雨","多云","多云","阴","晴","小雨","大雨","阴","多云","晴" };keyvalue::BinarySearchTree<string, int> countTree;for (auto& str : arr){//查找countTree中有没有匹配的天气keyvalue::BSTreeNode<string, int>* ret = countTree.Find(str);if (ret){ret->_value++;//若有，直接修改计数值}else{countTree.Insert(str, 1);//若无，先将对应天气存入二叉搜索树中}}countTree.InOrder();cout << endl;
}