二叉搜索树【C++】

概念

二叉搜索树又称二叉排序树，它或者是一个空树，或者是具有以下性质的二叉树

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

操作

1. 查找

• 从根开始比较，查找，比根大则往右边查找，比根小则往左边查找
• 最多查找高度次，走到空时，这个值不存在

2. 插入

• 树为空，则直接新增节点，赋值给root指针
• 数不为空，按性质查找插入位置，插入新节点
• 此blog的二叉搜索树不允许插入相同值

3. 删除（下面有删除两种情况的GIF图）

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

• 要删除的节点无子节点
• 要删除的节点只有一个子节点
• 要删除的节点有两个子节点****

第一二种情况可以合并为一种情况，因为我们可以将待删除节点的父节点指向待删除节点的子节点（无子节点可指向空）

因此实际情况可分为以下过程：

情况一（待删除节点只有一个节点或没有节点）：

删除该节点且使该节点的父节点指向被删除节点的任意一个子节点，无子节点时使父节点指向子节点的空，因此可以归类为一种情况

情况二（待删除节点有两个子节点）：

在该节点的右子树寻找最左节点A（或者是左子树的最右节点A，在此选择右子树的最左节点），然后用该节点A替换别删除节点，再删除该节点，此方法称替换法

至于为什么是右子树寻找最左节点（或者是在左子树的最右节点），对于情况二，以下图的节点3为例，我们需要在节点3的右子树寻找一个节点能够替换节点3，只有右子树的最小节点（即右子树的最左节点）能够替换使二叉搜索树的性质不变，假设我们用节点6或者节点7替换节点3，节点4就会破坏这棵树是二叉搜索树的性质

代码实现

节点定义

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

插入节点

1. 需要两个指针，cur寻找待插入位置，parent保存cur的上一个位置，根据性质找到待插入位置
2. 找到位置之后，判断cur在parent的左边还是右边再插入

// 迭代的函数名不包含R
// 递归的函数名包含R// 返回值情况：
// true：插入成功
// false：已经存在值为key的节点
// 迭代版本
bool Insert(const K& key)
{// 处理空树的情况// _root是二叉搜索树类中的成员变量，是树的根节点if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;// 找到待插入位置while (cur != nullptr){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);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;
}// 递归版本
bool InsertR(const K& key)
{return _InsertR(_root, key);
}bool _InsertR(Node*& root, const K& key)
{// 参数root传引用的作用是可以直接修改待插入位置的值，不用传递二级指针if (root == nullptr){Node* cur = new Node(key);root = cur;return true;}if (root->_key < key)return _InsertR(root->_right, key);else if (root->_key > key)return _InsertR(root->_left, key);elsereturn false;
}

查找节点

插入节点步骤的思路已经包含查找节点，所以在这不过多叙述

// 返回值
// true:找到了key
// false:没找到key
// 迭代
bool Find(const K& key)
{Node* cur = _root;while (cur != nullptr){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;
}// 递归
bool FindR(const K& key)
{return _FindR(_root, key);
}bool _FindR(Node* root, const K& key)
{if (root == nullptr){return false;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;}
}

删除节点

下图是删除有两个子节点的节点的情况，三个指针的作用：

1. cur：寻找待删除节点
2. subleft：寻找cur节点的右子树的最左节点
3. parent：保存subleft的父节点

交换完cur和subleft的val后，将subleft删除（转化为情况一删除，因为subleft最多只有一个子节点）

// 迭代
bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;// 寻找待删除节点while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{// 找到了，准备删除// 待插入节点左子节点为空// 待插入节点为叶子结点的情况也归为此类if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_left;}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;}}delete cur;}else{// 左右都不为空parent = cur;Node* subleft = cur->_right;// 找到被替换节点while (subleft->_left){parent = subleft;subleft = subleft->_left;}swap(cur->_key, subleft->_key);if (subleft == parent->_left){parent->_left = subleft->_right;}else{parent->_right = subleft->_right;}delete subleft;}return true;}}// 没找到待删除节点return false;
}// 递归
bool EraseR(const K& key)
{return _EraseR(_root, key);
}bool _EraseR(Node*& root, const K& key)
{if (root == nullptr){return false;}if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{// 找到待删除节点if (root->_left == nullptr){// 左节点为空Node* del = root;root = root->_right;delete del;return true;}else if (root->_right == nullptr){// 右节点为空Node* del = root;root = root->_left;delete del;return true;}else{// 左右节点都不为空// 寻找右子树的最左节点Node* subleft = root->_right;while (subleft->_left){subleft = subleft->_left;}swap(root->_key, subleft->_key);// 转化为递归子问题删除return _EraseR(root->_right, key);}}
}

汇总代码

添加了二叉搜索树的析构函数和中序遍历（打印出来的值是有序的）

#include <iostream>using namespace std;// 节点类
template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key): _left(nullptr), _right(nullptr), _key(key){}
};// 二叉搜索树类
template<class K>
class BSTree
{
public:typedef BSTreeNode<K> Node;// 非递归版本bool Insert(const K& key){// 空树if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;// 找到待插入位置while (cur != nullptr){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);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}bool Find(const K& key){Node* cur = _root;while (cur != nullptr){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;// 寻找待删除节点while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{// 找到了，准备删除// 待插入节点左子节点为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_left;}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;}}delete cur;}// 左右都不为空else{parent = cur;Node* subleft = cur->_right;// 找到被替换节点while (subleft->_left){parent = subleft;subleft = subleft->_left;}swap(cur->_key, subleft->_key);if (subleft == parent->_left){parent->_left = subleft->_right;}else{parent->_right = subleft->_right;}delete subleft;}return true;}}// 没找到待删除节点return false;}~BSTree(){DeleteTree(_root);}void DeleteTree(Node*& root){// 后序遍历析构二叉搜索树if (root == nullptr){return;}DeleteTree(root->_left);DeleteTree(root->_right);delete root;root = nullptr;}// 上述代码的递归版本bool InsertR(const K& key){return _InsertR(_root, key);}bool FindR(const K& key){return _FindR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}void InOrder(){_InOrder(_root);cout << endl;}private:bool _InsertR(Node*& root, const K& key){if (root == nullptr){Node* cur = new Node(key);root = cur;return true;}if (root->_key < key)return _InsertR(root->_right, key);else if (root->_key > key)return _InsertR(root->_left, key);elsereturn false;}bool _FindR(Node* root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;}}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{if (root->_left == nullptr){Node* del = root;root = root->_right;delete del;return true;}else if (root->_right == nullptr){Node* del = root;root = root->_left;delete del;return true;}else{Node* subleft = root->_right;while (subleft->_left){subleft = subleft->_left;}swap(root->_key, subleft->_key);return _EraseR(root->_right, key);}}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ' ';_InOrder(root->_right);}Node* _root = nullptr;
};