二叉搜索树(BST，Binary Search Tree)，也称二叉排序树或者二叉查找树。
它或者是一棵空树，或者是具有以下性质的二叉树：
对于二叉搜索树的操作支持增删查，却不支持改。因为对节点的修改很可能破坏二叉搜索树的结构，使其失效。
template<class K>
class BSTreeNode
{
public:
BSTreeNode(const K& key)
: _key(key)
, _left(nullptr)
, _right(nullptr)
{}
K _key;
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
// 非递归查找
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
private:
Node* _root;
};
插入分两种情况：
// 非递归插入
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;
}
}
// cur走到空，代表位置找到，此时让双亲节点链接
cur = new Node(key);
if (key > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
首先查找元素是否在二叉搜索树中，不存在就返回false。
否则，对要删除的节点可以分四种情况讨论：
其实这4种情况中，第1种情况可以与第2种情况，或第3种情况合并处理。
所以最终可以得到对3种删除情况的处理：
// 非递归删除
bool Erase(const K& 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 // 找到了
{
// 左子树为空
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;
cur = nullptr;
}
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;
cur = nullptr;
}
else
{
// 左右子树都不为空
// 替换法删除
// 左子树最大节点 -- 左子树最右节点
// 右子树最小节点 -- 右子树最左节点
Node* maxParent = cur;
// 这里找左子树的最大节点
Node* leftMax = cur->_left;
while (leftMax->_right)
{
maxParent = leftMax;
leftMax = leftMax->_right;
}
cur->_key = leftMax->_key; // 最右节点赋值给cur节点
// 对最右节点进行删除处理
if (maxParent->_left == leftMax)
{
maxParent->_left = leftMax->_left;
}
else
{
maxParent->_right = leftMax->_left;
}
delete leftMax;
}
return true;
}
}
return false;
}
template<class K>
class BSTreeNode
{
public:
BSTreeNode(const K& key)
: _key(key)
, _left(nullptr)
, _right(nullptr)
{}
K _key;
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
// 构造
BSTree(Node* root = nullptr)
:_root(root)
{}
// 拷贝构造
BSTree(const BSTree<K>& bst)
{
_root = _Copy(bst._root);
}
// 赋值
BSTree<K>& operator=(BSTree<K> bst)
{
swap(_root, bst._root);
return *this;
}
// 析构
~BSTree()
{
_Destory(_root);
}
// 查找
bool Find(const K& key)
{
return _Find(_root, key);
}
// 插入
bool Insert(const K& key)
{
return _Insert(_root, key);
}
// 删除
bool Erase(const K& key)
{
return _Erase(_root, key);
}
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;
}
// 这里给&,root就不用在外面置空了
void _Destory(Node*& root)
{
if (root == nullptr)
{
return;
}
// 后序遍历
_Destory(root->_left);
_Destory(root->_right);
delete root;
root = nullptr;
}
bool _Find(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key > root->_key)
{
return _Find(root->_right, key);
}
else if (key < root->_key)
{
return _Find(root->_left, key);
}
else
{
return true;
}
}
// 必须给&
bool _Insert(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (key > root->_key)
{
return _Insert(root->_right, key);
}
else if (key < root->_key)
{
return _Insert(root->_left, key);
}
else
{
return false;
}
}
// 必须是&
bool _Erase(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key > root->_key)
{
return _Erase(root->_right, key);
}
else if (key < root->_key)
{
return _Erase(root->_left, key);
}
else
{
Node* del = 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;
}
swap(root->_key, min->_key);
return _Erase(root->_right, key);
}
delete del;
return true;
}
}
private:
Node* _root;
};
以上代码读者可以通过添加中序遍历，对其进行验证。
二叉搜索树增删查的时间复杂度是
O
(
h
)
O(h)
O(h)，h是树的高度，因此h最坏的情况下是n。
这是因为二叉搜索树并不保证它是完全二叉树或接近完全二叉树，也就并不能保证它的节点的分布是均匀的。