【C++进阶】二叉搜索树（来自二叉树的复仇）

🪐🪐🪐欢迎来到程序员餐厅💫💫💫

主厨：邪王真眼

主厨的主页：Chef‘s blog

所属专栏：c++大冒险

总有光环在陨落，总有新星在闪烁

[本节目标]

1. 二叉搜索树的介绍

2. 二叉搜索树的实现

3.二叉树搜索树应用

一.二叉树的介绍

二叉搜索树（BST,Binary Search Tree）又称二叉排序树或二叉查找树。

它是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

2. 二叉搜索树的实现

本次二叉搜索树一律是小数放左边，大数放右边。

2.1节点

结合二叉树的知识，我们只知道二叉搜索树是分别写了两个类，一个是节点的类，一个是整个二叉树的类。

template<class T>
struct BSTNode
{BSTNode(const T& val = T()):_val (val),_left(nullptr),_right(nullptr){}BSTNode<T>* _left;BSTNode<T>* _right;T _val;
};

注意事项：

无论何时调用类模板，都要把模板参数给出

2.2成员变量

template<class T>
class BSTree
{typedef BSTNode<T> Node;
private:Node* _node;
};

注意事项：

为了方便等会调用节点模板，我们先把他typedef为Node

2.3构造函数

BSTree()
:_node(nullptr)
{}

简简单单的用nullptr初始化一波

2.4拷贝构造函数

BSTree(const BSTree<T>& b)
{_root = Copy(b._node);
}
Node* Copy(Node *b)
{if (b == nullptr)return nullptr;Node* p = new Node(b->_val);p->_left = Copy(b->_left);p->_right = Copy(b->_right);return p;
}

注意事项：

为了方便用递归，我们用别的函数实现拷贝，在用拷贝构造函数调用那个函数（捡便宜属于是）。
Copy用的是前序遍历来实现的

2.5赋值操作符重载

BSTree<T>& operator=(BSTree<T>b)
{swap(b._node, _node);return *this;
}

注意事项：

这次我们依旧用摩登的实现方法，传过去一份临时拷贝，在交换根节点即可。

2.6析构函数

~BSTree()
{destory(_node);
}
void destory(Node* node)
{if (node == nullptr)return;if (node->_left)destory(node->_left);if (node->_right)destory(node->_right);delete node;
}

注意事项：

同样的道理，我们也是又写了一个函数去实现销毁功能，再让析构函数调用，主要原因还是析构函数的接口不合适
destory用的是后序遍历

2.7中序遍历二叉树

	void _InOrder(Node* node){if(node->_left)_InOrder(node->_left);cout << node->_val << endl;if(node->_right)_InOrder(node->_right);}void InOrder(){_InOrder(_node);}

注意事项：

中序遍历可以得到二叉搜索树的升序或降序排列，如图

2.8查找

查找是二叉搜索树的一大优势，毕竟这log N的速度谁不爱呢？

2.8.1迭代实现

Node* Find(const T& val)
{Node* node = _node;while (node){if (node->_val == val)return node;else if (node->_val > val)node = node->_left;elsenode = node->_right;}return nullptr;
}

注意事项：

当前节点的val大于目标val是去左边找
当前节点的val小于目标val是去右边找
结果找到了就返回节点的指针，否则返回nullptr

2.8.2递归实现

bool RFind(const T& val)
{return _RFind(_node, val);
}
bool _RFind(Node*node,const T& val)
{if (node == nullptr)return false;if (val == node->_val)return true;return _RFind(node->_left, val) || _RFind(node->_left, val);}

注意事项：

这个返回指针很困难，所以我们直接返回真假表示有无该节点

2.9插入

2.9.1迭代

bool Insert(const T& val)
{if (_node == nullptr){_node = new Node(val);}else{Node* parent = nullptr;Node* child = _node;Node* ptr = new Node(val);while (child){parent = child;if (_node->_val > val){child = child->_left;}else if (_node->_val < val){child = child->_right;}elsereturn false;}if (parent->_val > val)parent->_left = ptr;if (parent->_val < val)parent->_right = ptr;}return true;
}

注意事项：

1.我们传的是引用，当发现根节点是空时可以直接修改根节点而不用搞二级指针
2.我们定义父亲节点和孩子节点，在循环中找到要把值放到那个父亲节点的孩子里
3.判断是放到父亲的左节点还是右节点。
4.如果发现该值已经存在了，则返回false，否则插入成功，返回true

2.9.2递归

bool RInsert(const T& val)
{_RInsert(_node, val);
}
bool _RInsert(Node*& p, const T& val)
{if (p == nullptr){p = new Node(val);return true;}if (p->_val > val)return RInsert(p->_left, val);else if (p->_val < val)return RInsert(p->_right, val);elsereturn false;
}

注意事项：

1.还是函数调用另一个函数（我们成为工具人）
2.我们传的是引用，所以不需要父亲节点了，直接修改即可
3.果发现该值已经存在了，则返回false，否则插入成功，返回true

2.10删除（重难点）

2.10.1迭代

bool Erase(const T& val)
{if (_node == nullptr)return true;Node* cur = _node;Node* parent_node = nullptr;while (cur){if (cur->_val == val)break;else if (cur->_val > val){parent_node = cur;cur = cur->_left;}else{parent_node = cur;cur = cur->_right;}}if (cur == nullptr)return false;if (cur->_left == nullptr){if (parent_node == nullptr)_node = _node->_right;else if (parent_node->_left == cur)parent_node->_left = cur->_right;else if (parent_node->_right == cur)parent_node->_right = cur->_right;delete cur;}else if (cur->_right == nullptr){if (parent_node == nullptr)_node = _node->_left;else if (parent_node->_left == cur)parent_node->_left = cur->_left;elseparent_node->_right = cur->_left;delete cur;}else{Node* leftmax = cur->_left;Node* parent_leftmax = cur;while (leftmax->_right){parent_leftmax = leftmax;leftmax = leftmax->_right;}cur->_val = leftmax->_val;if (parent_leftmax->_left)parent_leftmax->_left = leftmax->_left;elseparent_leftmax->_right = leftmax->_left;delete leftmax;}
}

首先查找元素是否在二叉搜索树中，如果不存在，则返回 , 否则要删除的结点可能分下面四种情

况：

a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

看起来有待删除节点有 4 中情况，实际情况 a 可以与情况 b 或者 c 合并起来，因此真正的删除过程

如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况d：在它的左子树中寻找最大的节点a，用它的值填补到被删除节点中，再来处理结点a--替换法删除

在此基础上，我们还要对每种情况下删除节点是否为根节点进行讨论

2.10.2递归

	bool _RErase(Node*&node,const T&val){if (node == nullptr)return false;if (node->_val > val)return _RErase(node->_left, val);if (node->_val < val)return _RErase(node->_right, val);else{if (node->_left == nullptr){Node* right = node->_right;delete node;node = right;}else if (node->_right == nullptr){Node* left = node->_left;delete node;node =left;}else{Node* p = node->_left;while (p->_right){p = p->_right;}swap(node->_val , p->_val);return  _RErase(node->_left,val);}return true;}}bool RErase(const T& val){return _RErase(_node,val);}

注意事项：

1.由于使用了引用，对左子树为空或右子树为空不再需要父亲节点的帮助
2.若左右子树都不为空，则交换letfmax和node数值后，通过递归消除leftmax
3.最后递归传参不要直接传根节点，而是node->left,因为之前的交换打乱了二叉树的结构，只能确定node->_left这棵树还是结构正确的

三.二叉树搜索树应用

3.1K模型

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

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

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

3.2. KV模型：

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

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

// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode{BSTNode(const K& key = K(), const V& value = V()): _pLeft(nullptr) , _pRight(nullptr), _key(key), _Value(value){}BSTNode<T>* _pLeft;BSTNode<T>* _pRight;K _key;V _value};
template<class K, class V>
class BSTree{typedef BSTNode<K, V> Node;typedef Node* PNode;
public:BSTree(): _pRoot(nullptr){}PNode Find(const K& key);bool Insert(const K& key, const V& value)bool Erase(const K& key)
private:PNode _pRoot;};
void TestBSTree3()
{// 输入单词，查找单词对应的中文翻译BSTree<string, string> dict;dict.Insert("string", "字符串");dict.Insert("tree", "树");dict.Insert("left", "左边、剩余");dict.Insert("right", "右边");dict.Insert("sort", "排序");// 插入词库中所有单词string str;while (cin>>str){BSTreeNode<string, string>* ret = dict.Find(str);if (ret == nullptr){cout << "单词拼写错误，词库中没有这个单词:" <<str <<endl;}else{cout << str << "中文翻译:" << ret->_value << endl;}}
}
void TestBSTree4()
{// 统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", 
"苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的节点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();
}