【二叉树进阶】二叉搜索树

1. 二叉搜索树概念

2. 二叉搜索树的实现

2.1 创建二叉搜索树节点

2.2 创建实现二叉搜索树

2.3 二叉搜索树的查找

2.4 二叉搜索树的插入

2.5 二叉搜索树的删除

2.6 中序遍历

2.7 完整代码加测试

3. 二叉搜索树的应用

3.1 K模型：

3.2 KV模型：

4. 二叉搜索树的性能分析

1. 二叉搜索树概念

二叉搜索树（BST，Binary Search Tree）：可以是一颗空树，满足以下性质：

根节点的值大于左子树上所有节点的值，小于右子树上所有节点的值。
它的左子树和右子树也分别为二叉搜索树。

它的中序遍历是有序的：0 1 2 3 4 5 6 7 8 9 ，所以也称为二叉排序树或二叉查找树。

2. 二叉搜索树的实现

int a[ ] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };

2.1 创建二叉搜索树节点

template<class K>
struct BSTreeNode
{BSTreeNode* _left;BSTreeNode* _right;K _key;//初始化节点BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};

2.2 创建实现二叉搜索树

template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://操作实现//查找bool Find(const K& key) { }//插入void Insert(const K& key) { }//删除bool Erase() { }//中序遍历void InOrder() { }
private:Node* _root = nullptr;
}

2.3 二叉搜索树的查找

a、从根开始查找，比根大往右边查找，比根小往左边查找。

b、最多查找高度次，走到空，还没找到，则要查找的值不存在。

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

2.4 二叉搜索树的插入

a、如果树为空，新增节点，赋值给_root指针。

b、按搜索二叉树性质查找插入位置，插入节点。

c、要插入的位置一定为为空的位置，所以要插入，还要找到要插入位置的父节点，让父节点指向新插入的节点。

bool Insert(const K& key)
{//如果树为空，新增节点if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){//比根小if (key < cur->_key){parent = cur;cur = cur->_left;}//比根大else if (key > cur->_key){parent = cur;cur = cur->_right;}//与根相等else{return false;}}cur = new Node(key);if (key < parent->_key){parent->_left = cur;}else{parent->_right = cur;}return true;
}

2.5 二叉搜索树的删除

a、先判断要删除的元素是否存在，不存在，返回false。

b、若存在，则分为以下情况:

要删除的节点（叶子节点）左右子树为空
要删除的节点左子树为空或右子树为空
要删除的节点左子树右子树都不为空

实际操作起来，情况1和情况2能合并到一起实现，只有两种情况：

要删除的节点的左子树或右子树为空：直接删除-----让父亲指向要删除节点右子树（左子树），再直接删除该节点。

如果要删除的该节点为根，则直接让它的右子树（左子树）赋值给_root让它成为新根即可。

要删除的节点的左右子树都不为空：替换法删除----在它的右子树中找到最小值（最左节点）或在左子树中找到最大值（最右节点），将它的值与要删除节点的值替换，这时就转换为该节点的删除问题。

右子树最左节点的左子树一定为空，左子树最右节点的右子树一定为空，这就转换为第一种情况的删除了。

	bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;//查找while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}//找到了 删除else{//1.要删除节点的左子树为空或者右子树为空if (cur->_left == nullptr){//如果为根if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}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* rightMinParent = cur;Node* rightMin = cur->_right;//要替换的节点while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}//替换法交换cur->_key = rightMin->_key;//转换成删除rightMinif (rightMin == rightMinParent->_right){//rightMin的左子树一定为空rightMinParent->_right = rightMin->_right;}else{rightMinParent->_left = rightMin->_right;}delete rightMin;}//这里我们去找左子树的最大值//else//{//	Node* leftMaxParent = cur;//	Node* leftMax = cur->_left;//	while (leftMax->_right)//	{//		leftMaxParent = leftMax;//		leftMax = leftMax->_right;//	}//	//替换法删除//	cur->_key = leftMax->_key;//	//转换为删除leftMax//	if (leftMax == leftMaxParent->_left)//	{//		leftMaxParent->_left = leftMax->_left;//	}//	else//	{//		leftMaxParent->_right = leftMax->_left;//	}//	delete leftMax;//}return true;}}return false;}

2.6 中序遍历

中序遍历：按照左子树根右子树的方式迭代遍历二叉树。

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

总之，我们在实现二叉搜索树的时候一定要考虑多种情况，每种情况也要多找几个节点进行分析。

2.7 完整代码加测试

BSTree.hpp:

//创建二叉树节点
template<class K>
struct BSTreeNode
{BSTreeNode* _left;BSTreeNode* _right;K _key;//初始化节点BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};
//创建实现二叉树
template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key){//如果树为空，新增节点if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){//比根小if (key < cur->_key){parent = cur;cur = cur->_left;}//比根大else if (key > cur->_key){parent = cur;cur = cur->_right;}//与根相等else{return false;}}cur = new Node(key);if (key < parent->_key){parent->_left = cur;}else{parent->_right = cur;}return true;}//中序遍历void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;//查找while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}//找到了 删除else{//1.要删除节点的左子树为空或者右子树为空if (cur->_left == nullptr){//如果为根if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}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* rightMinParent = cur;Node* rightMin = cur->_right;//要替换的节点while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}//替换法交换cur->_key = rightMin->_key;//转换成删除rightMinif (rightMin == rightMinParent->_right){//rightMin的左子树一定为空rightMinParent->_right = rightMin->_right;}else{rightMinParent->_left = rightMin->_right;}delete rightMin;}//这里我们去找左子树的最大值//else//{//	Node* leftMaxParent = cur;//	Node* leftMax = cur->_left;//	while (leftMax->_right)//	{//		leftMaxParent = leftMax;//		leftMax = leftMax->_right;//	}//	//替换法删除//	cur->_key = leftMax->_key;//	//转换为删除leftMax//	if (leftMax == leftMaxParent->_left)//	{//		leftMaxParent->_left = leftMax->_left;//	}//	else//	{//		leftMaxParent->_right = leftMax->_left;//	}//	delete leftMax;//}return true;}}return false;}bool Find(const K& key){if (_root == nullptr){return false;}Node* cur = _root;while (cur){if (key < cur->_left){cur = cur->_left;}else if (key > cur->_right){cur = cur->_right;}else{return true;}}return false;}
private:Node* _root = nullptr;
};
void TestBSTree()
{BSTree<int> t;int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };for (auto e : a){t.Insert(e);}for (auto e : a){t.Erase(e);t.InOrder();}
}

Test.cpp:

#include"BSTree.hpp"
int main()
{TestBSTree();return 0;
}

运行结果：

3. 二叉搜索树的应用

3.1 K模型：

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

比如：给一个单词，判断该单词是否正确：

以词库中所有单词集合中的每个单词作为key，构建一颗二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

其实就是上面我们实现的二叉搜索树的查找。这里不在重复实现了。

3.2 KV模型：

每一个关键码Key，都有与子对应的Value，即<Key,Value>的键值对。

比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到对应中文，英文单词与其中文构成<world，chinese>就构成一种键值对；
比如：统计单词次数，统计成功后，给定单词可以快速找到其出现次数，单词与其出现次数<world，count>就构成一种键值对。

也很简单，其实就是让二叉搜索树中的节点多存一个值Value，查找、插入、删除等操作依旧是按照key去实现的。

改造二叉搜索树为KV结构模型：

template<class K,class V>
struct BSTreeNode
{BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _value;//多存一个值valueBSTreeNode(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:bool Insert(const K& key,const V& value){ }void _InOrder(Node* root){ }void InOrder(){ }bool Erase(const K& key){ }Node* Find(const K& key)//返回节点的指针，这里不再实现{ }
private:Node* _root = nullptr;
};

应用测试1：输入英文查找对应的中文

void TestBSTree()
{BSTree<string, string> dict;dict.Insert("string", "字符串");dict.Insert("tree", "树");dict.Insert("int", "整型");dict.Insert("search", "查找");dict.Insert("insert", "插入");string str;while (cin >> str){BSTreeNode<string, string>* ret = dict.Find(str);if (ret == nullptr){cout << "词库中无此单词" << endl;}cout << ret->_value << endl;}
}

结果：

应用测试2：查找水果出现的次数

void TestBSTree()
{string arr[] = { "苹果","香蕉","西瓜","西瓜","香梨","西瓜" ,"苹果" ,"西瓜" ,"西瓜" ,"香蕉" ,"苹果" };BSTree<string, int> t;int i = 0;for (auto e : arr){BSTreeNode<string, int>* ret = t.Find(e);//ret为空说明要查找的是第一次出现if (ret == nullptr){t.Insert(e, 1);}else{ret->_value++;}}t.InOrder();
}

结果：