二叉搜索树
概念
二叉搜索树又称为二叉排序树，因为这棵树的中序遍历是有序的。二叉搜索树总结起来有以下几个性质：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于于根节点的值
- 它的左右子树都是二叉搜索树
- 这棵树中没有重复的元素
举个例子：
二叉搜索树的实现
基本框架
template <class K,class V> struct BST_Node { BST_Node<K,V>* left; BST_Node<K,V>* right; K key; V value; //构造函数 BST_Node(const K& key, const V& value):left(nullptr),right(nullptr),key(key),value(value) {} }; template <class K,class V> class BST_Tree { typedef BST_Node<K,V> Node; public: private: Node* root = nullptr; }; 要实现的接口
bool Insert(const K& key,const V& value);//二叉搜索树的插入 void InOrder();//打印功能，采用中序遍历（递归） Node* Find(const K& key);//二叉搜索树的查找 bool Erase(const K& key);//二叉搜索树的删除 二叉搜索树的插入
插入分为下面几个步骤：
- 先判断树是否为空，为空就让要插入的这个节点作为根节点，然后结束
- 确定要插入节点的位置
- 用一个cur记录当前节点，parent记录父节点
- 要插入节点的值如果比当前节点的值小，cur就往左走，如果比当前节点的值大，就往右子树走，如果等于就返回false，表面这棵树中有这个数据，不需要插入
//二叉搜索树的插入 bool Insert(const K& key,const V& value) { //没有节点的时候就是根节点 if (root == nullptr) { root = new Node(key,value); return true; } //用一个父节点记录cur的上一个节点 Node* parent = nullptr; Node* cur = root; while (cur) { parent = cur; //小于往左走 if (key < cur->key) { cur = cur->left; } else if (key > cur->key) { cur = cur->right; } else return false; } cur = new Node(key,value); //判断应该插在父节点的左边还是右边 if (cur->key < parent->key) { parent->left = cur; } else { parent->right = cur; } return true; } 打印二叉搜索树（中序遍历）
//中序遍历（递归） void InOrder() { _InOrder(root); cout << endl; } void _InOrder(Node* root) { if (root == NULL) { return; } else { _InOrder(root->left); cout << root->key << ":" << root->value << endl; _InOrder(root->right); } } 二叉搜索树的查找
查找的步骤如下：（和插入的步骤有些类似）
- 如果查找值key比当前节点的值小，就往左子树走
- 如果查找值key比当前节点的值大，就往右子树走
- 如果查找值key和当前节点的值相等，就返回当前节点的指针
//二叉搜索树的查找 Node* Find(const K& key) { if (root == nullptr) { return nullptr; } 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; } 二叉搜索树的删除（难）
分四种情况：我们一个一个来讨论
以下面这颗树为例：
情景一：
情景二：
还要分析一种特殊的情况，就是此时2没有父亲节点，也就是自己为根时，看下面如何操作
情景三：
该节点如果为根节点，就让自己的右孩子变成根节点
情景四：
总结： 一共有四种情况，但是情况1可以归为情况3，因为它也是左为空，所以整体处理下来是三种情况
//二叉搜索树的删除 bool Erase(const K& key) { //树为空，删除失败 if (root == nullptr) { return false; } //parent始终是cur的父亲节点 //cur就是要找的删除的当前节点 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.左右子树都为空，直接删除，可以归类为左为空 // 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左 // 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除 //当前情况是情景三，删除的节点它的左为空，右未知 if (cur->left == nullptr) { // 要删除节点为根节点时，直接把右子树的根节点赋值给——root // 根节点的话会导致parent为nullptr if (root == cur) { root = root->right; } else { //左为空，父亲指向我的右 //判断cur在父亲的左还是右 if (parent->left == cur) { parent->left = cur->right; } else { parent->right = cur->right; } } delete cur; cur = nullptr; } //当前情况是情景二，删除节点它的右为空，左未知 else if (cur->right == nullptr) { if (root ==cur ) { root = root->left; } else { //右为空，父亲指向我的左 //判断cur在父亲的左还是右 if (parent->left == cur) { parent->left = cur->left; } else { parent->right = cur->left; } } delete cur; cur = nullptr; } //只剩下情景四 else { //找右子树中最小的节点，当前cur就是要删除的节点 Node* rightMinParent = cur; Node* rightMin = cur->right;//去右子树找最小的节点 while (rightMin->left) { rightMinParent = rightMin; rightMin = rightMin->left; } //替代删除 cur->key = rightMin->key; //转化成了情景三，左孩子为空 if (rightMinParent->left == rightMin) rightMinParent->left = rightMin->right; else rightMinParent->right = rightMin->right; delete rightMin; rightMin = nullptr; } return true; } } return false; } 完整代码以及测试
#define _CRT_SECURE_NO_WARNINGS #include<iostream> //引入头文件 #include<string>//C++中的字符串 using namespace std; //标准命名空间 template <class K > struct BST_Node { BST_Node<K>* left; BST_Node<K>* right; K key; //构造函数 BST_Node(const K& key):left(nullptr),right(nullptr),key(key) {} }; template <class K> class BST_Tree { typedef BST_Node<K> Node; public: //二叉搜索树的插入 bool Insert(const K& key) { //没有节点的时候就是根节点 if (root == nullptr) { root = new Node(key); return true; } //用一个父节点记录cur的上一个节点 Node* parent = nullptr; Node* cur = root; while (cur) { parent = cur; //小于往左走 if (key < cur->key) { cur = cur->left; } else if (key > cur->key) { cur = cur->right; } else return false; } cur = new Node(key); //判断应该插在父节点的左边还是右边 if (cur->key < parent->key) { parent->left = cur; } else { parent->right = cur; } return true; } //中序遍历（递归） void InOrder() { _InOrder(root); cout << endl; } void _InOrder(Node* root) { if (root == NULL) { return; } else { _InOrder(root->left); cout << root->key <<" "; _InOrder(root->right); } } //二叉搜索树的查找 Node* Find(const K& key) { if (root == nullptr) { return nullptr; } 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) { //树为空，删除失败 if (root == nullptr) { return false; } //parent始终是cur的父亲节点 //cur就是要找的删除的当前节点 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.左右子树都为空，直接删除，可以归类为左为空 // 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左 // 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除 //当前情况是情景三，删除的节点它的左为空，右未知 if (cur->left == nullptr) { // 要删除节点为根节点时，直接把右子树的根节点赋值给——root // 根节点的话会导致parent为nullptr if (root == cur) { root = root->right; } else { //左为空，父亲指向我的右 //判断cur在父亲的左还是右 if (parent->left == cur) { parent->left = cur->right; } else { parent->right = cur->right; } } delete cur; cur = nullptr; } //当前情况是情景二，删除节点它的右为空，左未知 else if (cur->right == nullptr) { if (root ==cur ) { root = root->left; } else { //右为空，父亲指向我的左 //判断cur在父亲的左还是右 if (parent->left == cur) { parent->left = cur->left; } else { parent->right = cur->left; } } delete cur; cur = nullptr; } //只剩下情景四 else { //找右子树中最小的节点，当前cur就是要删除的节点 Node* rightMinParent = cur; Node* rightMin = cur->right;//去右子树找最小的节点 while (rightMin->left) { rightMinParent = rightMin; rightMin = rightMin->left; } //替代删除 cur->key = rightMin->key; //转化成了情景三，左孩子为空 if (rightMinParent->left == rightMin) rightMinParent->left = rightMin->right; else rightMinParent->right = rightMin->right; delete rightMin; rightMin = nullptr; } return true; } } return false; } private: Node* root = nullptr; }; void TestBSTree() { BST_Tree<int> bt; int arr[] = { 5,3,4,1,7,8,2,6,0,9 }; for (auto e : arr) { cout << "插入 " << e << " 后："; bt.Insert(e); bt.InOrder(); } cout << "------------------------------" << endl; for (auto e : arr) { cout << "删除 " << e << " 后："; bt.Erase(e); bt.InOrder(); } } int main() { TestBSTree(); system("pause"); return EXIT_SUCCESS; } 二叉搜索树的应用
二叉搜索树有两种模型：
- K模型： K模型只有key值，节点只存储key值。这里主要应用就是查找判断某个元素在不在。
- KV模型： KV模型每个key值都对应着一个value，主要应用就是通过key找value。（我们平时查找单词就是通过中文找英文，或者通过英文找中文）
上面的测试代码是KV模型改成了K模型，接下来我们来看看KV模型的作用
#define _CRT_SECURE_NO_WARNINGS #include<iostream> //引入头文件 #include<string>//C++中的字符串 using namespace std; //标准命名空间 template <class K,class V> struct BST_Node { BST_Node<K,V>* left; BST_Node<K,V>* right; K key; V value; //构造函数 BST_Node(const K& key, const V& value):left(nullptr),right(nullptr),key(key),value(value) {} }; template <class K,class V> class BST_Tree { typedef BST_Node<K,V> Node; public: //二叉搜索树的插入 bool Insert(const K& key,const V& value) { //没有节点的时候就是根节点 if (root == nullptr) { root = new Node(key,value); return true; } //用一个父节点记录cur的上一个节点 Node* parent = nullptr; Node* cur = root; while (cur) { parent = cur; //小于往左走 if (key < cur->key) { cur = cur->left; } else if (key > cur->key) { cur = cur->right; } else return false; } cur = new Node(key,value); //判断应该插在父节点的左边还是右边 if (cur->key < parent->key) { parent->left = cur; } else { parent->right = cur; } return true; } //中序遍历（递归） void InOrder() { _InOrder(root); cout << endl; } void _InOrder(Node* root) { if (root == NULL) { return; } else { _InOrder(root->left); cout << root->key << ":" << root->value << endl; _InOrder(root->right); } } //二叉搜索树的查找 Node* Find(const K& key) { if (root == nullptr) { return nullptr; } 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) { //树为空，删除失败 if (root == nullptr) { return false; } //parent始终是cur的父亲节点 //cur就是要找的删除的当前节点 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.左右子树都为空，直接删除，可以归类为左为空 // 2.左右子树只有一边为空，左为空，父亲指向我的右，右为空，父亲指向我的左 // 3.左右子树都不为空，取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除 //当前情况是情景三，删除的节点它的左为空，右未知 if (cur->left == nullptr) { // 要删除节点为根节点时，直接把右子树的根节点赋值给——root // 根节点的话会导致parent为nullptr if (root == cur) { root = root->right; } else { //左为空，父亲指向我的右 //判断cur在父亲的左还是右 if (parent->left == cur) { parent->left = cur->right; } else { parent->right = cur->right; } } delete cur; cur = nullptr; } //当前情况是情景二，删除节点它的右为空，左未知 else if (cur->right == nullptr) { if (root ==cur ) { root = root->left; } else { //右为空，父亲指向我的左 //判断cur在父亲的左还是右 if (parent->left == cur) { parent->left = cur->left; } else { parent->right = cur->left; } } delete cur; cur = nullptr; } //只剩下情景四 else { //找右子树中最小的节点，当前cur就是要删除的节点 Node* rightMinParent = cur; Node* rightMin = cur->right;//去右子树找最小的节点 while (rightMin->left) { rightMinParent = rightMin; rightMin = rightMin->left; } //替代删除 cur->key = rightMin->key; //转化成了情景三，左孩子为空 if (rightMinParent->left == rightMin) rightMinParent->left = rightMin->right; else rightMinParent->right = rightMin->right; delete rightMin; rightMin = nullptr; } return true; } } return false; } private: Node* root = nullptr; }; int main() { system("pause"); return EXIT_SUCCESS; } 实例1
英汉字典
void TestBSTree_KV1() { // 创建一个简易的字典 BST_Tree<string, string> dict; dict.Insert("苹果", "apple"); dict.Insert("香蕉", "banana"); dict.Insert("橘子", "orange"); dict.Insert("葡萄", "grape"); dict.Insert("apple", "苹果"); dict.Insert("banana", "香蕉"); dict.Insert("orange", "橘子"); dict.Insert("grape", "葡萄"); string str; while (cin >> str) { BST_Node<string, string>* ret = dict.Find(str); if (ret) { cout << ret->value << endl; } else { cout << "本字典无此词" << endl; } } } 实例2
统计树
void TestBSTree_KV2() { // 统计水果个数 BST_Tree<string, int> countTree; string strArr[] = { "香蕉","水蜜桃","西瓜","苹果","香蕉" ,"西瓜","香蕉" ,"苹果","西瓜","苹果","苹果","香蕉" ,"水蜜桃" }; for (auto e : strArr) { BST_Node<string, int>* ret = countTree.Find(e); if (ret == nullptr) { // 第一次插入 countTree.Insert(e, 1); } else { ret->value++; } } countTree.InOrder(); } 
