目录
学习目标：
1.二叉搜索树
1.1二叉搜索树的概念
1.2二叉搜索树的操作
1.二叉搜索树的查找
2.二叉树的插入
3.二叉树的删除*
2.二叉搜索树的实现
3.二叉树性能分析
1.二叉搜索树
1.1二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
1.2二叉搜索树的操作
1.二叉搜索树的查找
我们根据二叉树的性质可以知道，每棵树的左子树上的节点的值都小于根，右子树上的节点的值都大于根所以我们可以这样查找
a.从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在
2.二叉树的插入
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
3.二叉树的删除*
二叉树的删除分为四种情况：
1.要删除的节点 为叶子节点，这一种我们直接删除，没有任何影响
2.要删除的节点 的左子树为空，这个时候我们需要记录一下要删除节点的父节点，让他的父节点来继承它的子树
3.要删除的节点 的右子树为空，这个时候我们需要记录一下要删除节点的父节点，让他的父节点来继承它的子树
4.要删除的节点 左右子树都不为空，这种情况最为麻烦，我们可以使用替换删除法
找到要删除节点的右子树的最左节点或者 左子树的左右节点，替换删除的节点，并记录cur的父节点。
代码如下：
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->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)//右子树为空
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
else //左右子树都为空的情况 用右子树的最左节点替代
{
// 替换法
Node* rightMinParent = cur;//不初始化为空是为了防止删除根结点
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)//被替换的节点的父节点来继承左右子树
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}2.二叉搜索树的实现
#pragma once
namespace key
{
template<class K>
struct BSTreeNode
{
typedef BSTreeNode<K> Node;
Node* _left;
Node* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree() = default;
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destroy(_root);
}
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
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
{
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)
{
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->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)//右子树为空
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
else //左右子树都为空的情况 用右子树的最左节点替代
{
// 替换法
Node* rightMinParent = cur;//不初始化为空是为了防止删除根结点
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMin == rightMinParent->_left)//被替换的节点的父节点来继承左右子树
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
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
{
Node* del = root;
if (root->_right == nullptr)
{
root = root->_left;
}
else if (root->_left == nullptr)
{
root = root->_right;
}
else
{
Node* rightMin = root->_right;
while (rightMin->_left)
{
rightMin = rightMin->_left;
}
swap(root->_key, rightMin->_key);
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return 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;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
}3.二叉树性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
如果二叉树成为了单支树，搜索和查找效率就会变得非常差。
![[Meachines][Medium]IClean](https://img-blog.csdnimg.cn/img_convert/45cb59dc61662235932716cd9cb0ba72.jpeg)
