C++:搜索二叉树
文章目录
- 一、二叉搜索树的概念
- 二、二叉搜索树的性能分析
- 三、二叉搜索树的插入
- 四、二叉搜索树的查找
- 五、二叉搜索树的删除
- 六、二叉搜索树的代码实现
一、二叉搜索树的概念
它如果不是一颗空树，那么就要具有以下的性质：
- 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
- 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
- 它的左右子树也都满足二叉搜索树的性质
功能用来：查找，其次中序遍历可是完成排序。
类似二分查找，但二分查找有缺陷:
1、要求有序
2、底层结构要求是数组，头部或中间插入删除数据效率很低
二、二叉搜索树的性能分析
三、二叉搜索树的插入
插入过程：
1、树为空，则直接新增结点，赋值给root指针
2、树不空，按二叉搜索树性质，插入值比当前节点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
3、如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插⼊新结点。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右⾛，⼀会往左⾛）
四、二叉搜索树的查找
- 从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。
- 最多查找⾼度次，⾛到到空，还没找到，这个值不存在。
- 如果不⽀持插⼊相等的值，找到x即可返回
- 如果⽀持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。如下图，查找3，要找到1的右孩⼦的那个3返回
五、二叉搜索树的删除
首先查找要删除的元素是否存在二叉搜索树中，如果不存在，则返回false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）
1、要删除结点N左右孩子均为空
2、要删除的结点N左孩子为空，右孩子结点不为空
3、要删除的结点N右孩子为空，左孩子结点不为空
4、要删除的结点N左右孩子结点均为空
对应以上四种情况的解决方案：
1、把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成情况2或者3处理，效果是一样的）
2、把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点
3、把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点
4、无法直接删除N结点，因为N的两个孩子无处安放只能用替代法删除。找到N左子树的最大结点R（最右结点）或者N右子树的值最小结点R(最左结点）代替N，因为这两个结点任意一个放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R这两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除。
六、二叉搜索树的代码实现
#pragma once
#include <iostream>
#include <stdbool.h>
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{
}
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
parent = cur;
cur = cur->_left;
}
}
cur = new Node(key);
if (parent->_key >= key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
void Inorder()
{
Inorder(_root);
}
Node* find(const K& key)
{
Node* cur = _root;
Node* ret = nullptr;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
ret = cur;
cur = cur->_left;
}
}
return ret;
}
bool Ereas(const K& key)
{
Node* cur = _root;
Node* ret = nullptr;
Node* parent = nullptr;
Node* retparent = nullptr;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
ret = cur;
retparent = parent;
parent = cur;
cur = cur->_left;
}
}
if (ret == nullptr)
return false;
if (retparent != NULL)
{
if (ret->_left == nullptr)
{
if (retparent->_left == ret)
{
retparent->_left = ret->_right;
}
else
{
retparent->_right = ret->_right;
}
delete ret;
}
else if (ret->_right == nullptr)
{
if (retparent->_left == ret)
{
retparent->_left = ret->_left;
}
else
{
retparent->_right = ret->_left;
}
delete ret;
}
else
{
Node* minRight = ret->_right;
Node* minRightParent = nullptr;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
if (minRightParent != nullptr)
{
ret->_key = minRight->_key;
minRightParent->_left = minRight->_right;
delete minRight;
}
else
{
ret->_key = minRight->_key;
ret->_right = minRight->_right;
delete minRight;
}
}
}
else
{
if (ret->_left == nullptr)
{
_root = ret->_right;
delete ret;
}
else if (ret->_right == nullptr)
{
_root = ret->_left;
delete ret;
}
else
{
Node* minRight = ret->_right;
Node* minRightParent = nullptr;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
if (minRightParent != nullptr)
{
ret->_key = minRight->_key;
minRightParent->_left = minRight->_right;
delete minRight;
}
else
{
ret->_key = minRight->_key;
ret->_right = minRight->_right;
delete minRight;
}
}
}
return true;
}
private:
void Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
Inorder(root->_left);
std::cout << root->_key << " ";
Inorder(root->_right);
}
Node* _root = nullptr;
};