前言：
在数据结构中学习过
二叉树，链式二叉树，顺序二叉树，区别于二者的的一种特殊的二叉树是二叉搜索树
二叉搜索树介绍（BST）
二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树
它具有以下性质：
- 如果树非空，则左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值，且左右子树各自也是二叉搜索树。
- 二叉搜索树的特点是能够快速执行查找、插入和删除操作，其时间复杂度通常为对数级别.
如下，是一个简易的二叉搜索树
flowchart TD
8-->3
8-->10
10-->9
10-->14
14-->12
14-->13
3-->1
3-->6
6-->4
6-->7
二叉搜索树基本操作（BST）
二叉搜索树的存储结构（K模型）
- 如果构成
KV模型仅仅在加一个模板参数就好了 - 二树经典的左右指针，和存储数据声明
template<class K>
class BSTTree
{
public:
BSTTree<K>* _left;
BSTTree<K>* _right;
K _key;
BSTTree(const K& key)
: _left(nullptr)
, _right(nullptr)
, _key(key)
{
}
};
默认成员函数
拷贝构造
- 采用递归的方式
Node* _Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* copynode = new Node(root->_key);
copynode->_left = _Copy(root->_left);
copynode->_right = _Copy(root->_right);
return copynode;
}
赋值运算符号重载
- 传值拷贝，直接进行交换
BST(const BST<K>& copy)
{
_root = _copy(copy._root);
}
析构函数
- 用
~BST（）直接实现调用的递归
~BST()
{
_destory(_root);
}
void _destory(Node* root)
{
if (root == nullptr)
return;
_destory(root->_left);
_destory(root->_right);
delete root;
root = nullptr;
}
BST查找
- 二叉搜索树的查找操作从根节点开始，根据查找值与当前节点值的关系，选择向左子树或右子树递归查找。
- 如果当前节点的值等于查找值，则找到该节点；如果小于查找值，则向右子树查找；如果大于查找值，则向左子树查找。如
- 果查找过程中到达叶节点仍未找到对应值，则表明该值不存在于树中
迭代
bool Find(const K& key)
{
if (_root == nullptr)
return false;
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
递归
- 由于在类的内部，类外参数不能传this指针，采用类内传递的形式，进而实现递归
bool Find(const K& key)
{
return _Find(_root ,key);
}
bool _Find(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;
}
}
BST插入
- 插入操作首先检查树是否为空，如果为空，则新建一个包含待插入值的节点作为根节点。
- 如果树不为空，则根据二叉搜索树的性质，从根节点开始向下遍历，直至找到一个空的子节点位置，将新节点插入到该位置。
- 新节点总是作为叶节点插入，以保持树的二叉搜索树属性.
迭代
- 开始判断树是否为空树
- 建立
parent节点记录父亲节点 - 进行遍历，查找叶子节点插入
- 保存父亲的节点作用在进行，叶子节点插入的时候进行判断，新节点和叶子节点的大小关系
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return false;
}
}
if (key < parent->_key)
{
parent->_left = new Node(key);
}
else
{
parent->_right = new Node(key);
}
return true;
}
递归
- 值得注意的点是传参数的时候是指针的引用。
- 好处就是不用进行新节点与父亲节点的判断。
bool Insert(const K& key)
{
return _Insert(_root,key);
}
bool _Insert(Node*& root ,const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (key < root->_key)
{
return _Insert(root->_left, key);
}
else if(key > root->_key )
{
return _Insert(root->_right, key);
}
else
{
return false;
}
}
BST删除
- 删除操作较为复杂，因为需要考虑被删除节点可能有零个、一个或两个子节点的情况。
- 删除操作通常涉及到找到被删除节点的适当继任者（在有两个子节点的情况下，通常是其右子树中的最小节点或左子树中的最大节点），并用继任者的值替换被删除节点的值，然后删除被替换的节点
迭代
三种情况：
- 要删除的结点无孩子结点 （叶子节点）
- 要删除的结点只有左孩子结点
- 要删除的结点只有右孩子结点
- 要删除的结点有左、右孩子结点
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = _root;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}//找到键值
else
{
//左子树为空
if (cur->_left == nullptr)
{
//祖先节点为键值
if (cur == _root)
{
cur = cur->_right;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
}//右子树为空
else if (cur->_right == nullptr)
{
//祖先节点为键值
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
}
else//左右子树均存在，查找右子树最大节点
{
Node* leftMax = cur->_left;
while (leftMax->_right)
{
parent = leftMax;
leftMax = leftMax->_right;
}
swap(leftMax->_key, cur->_key);
//易错点，找到节点并不知道
if (parent->_left == leftMax)
{
parent->_left = leftMax->_left;
}
else
{
parent->_right = leftMax->_left;
}
cur = leftMax;
}
delete cur;
return true;
}
}
return false;
}
迭代
- 这里面也是指针的引用
bool Erase(const K& key)
{
return _Erase(_root, key);
}
bool _Erase(Node*& root, const K& key)
{
if (root == nullptr)
return false;
if (key < root->_key)
{
return _Erase(root->_left, key);
}
else if(key>root->_key)
{
return _Erase(root->_right, key);
}
else
{
Node* del = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
Node* leftMax = root->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
swap(root->_key, leftMax->_key);
return _Erase(root->_left, key);
}
delete del;
return true;
}
}
BST遍历
- 直接递归实现
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
源码
迭代
#pragma once
namespace MyBST
{
template<class K>
class BSTTree
{
public:
BSTTree<K>* _left;
BSTTree<K>* _right;
K _key;
BSTTree(const K& key)
: _left(nullptr)
, _right(nullptr)
, _key(key)
{
}
};
template<class K>
class BST
{
typedef BSTTree<K> Node;
public:
BST()
:_root(nullptr)
{
}
BST(const BST& t)
{
return _Copy(_root);
}
BST& operator=(const BST& t)
{
swap(_root, t._root);
return *this;
}
~BST()
{
_destory();
}
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return false;
}
}
if (key < parent->_key)
{
parent->_left = new Node(key);
}
else
{
parent->_right = new Node(key);
}
return true;
}
bool Find(const K& key)
{
if (_root == nullptr)
return false;
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = _root;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
if (cur->_left == nullptr)
{
if (cur == _root)
{
cur = cur->_right;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
}
else
{
Node* leftMax = cur->_left;
while (leftMax->_right)
{
parent = leftMax;
leftMax = leftMax->_right;
}
swap(leftMax->_key, cur->_key);
//易错点
if (parent->_left == leftMax)
{
parent->_left = leftMax->_left;
}
else
{
parent->_right = leftMax->_left;
}
cur = leftMax;
}
delete cur;
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _destory(Node* root)
{
if(root == nullptr)
{
return;
}
_destory(root->_left);
_destory(root->_right);
delete root;
root = nullptr;
}
Node* _Copy(Node* root)
{
Node* copynode = new Node(root->_key);
copynode->_left = _Copy(root->_left);
copynode->_right = _Copy(root->_right);
return copynode;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
Node* _root;
};
}
递归
#pragma once
#include<iostream>
using namespace std;
namespace MyBSTR
{
template<class K>
class BSTTree
{
public:
BSTTree<K>* _left;
BSTTree<K>* _right;
K _key;
BSTTree(const K& key)
: _left(nullptr)
, _right(nullptr)
, _key(key)
{
}
};
template<class K>
class BST
{
typedef BSTTree<K> Node;
public:
BST()
:_root(nullptr)
{
}
BST(const BST<K>& copy)
{
_root = _copy(copy._root);
}
BST& operator=(BST t)
{
swap(_root, t.root);
return *this;
}
~BST()
{
_destory(_root);
}
bool Insert(const K& key)
{
return _Insert(_root,key);
}
bool Find(const K& key)
{
return _Find(_root ,key);
}
bool Erase(const K& key)
{
return _Erase(_root, key);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _destory(Node* root)
{
if (root == nullptr)
return;
_destory(root->_left);
_destory(root->_right);
delete root;
root = nullptr;
}
Node* _Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* copynode = new Node(root->_key);
copynode->_left = _Copy(root->_left);
copynode->_right = _Copy(root->_right);
return copynode;
}
bool _Erase(Node*& root, const K& key)
{
if (root == nullptr)
return false;
if (key < root->_key)
{
return _Erase(root->_left, key);
}
else if(key>root->_key)
{
return _Erase(root->_right, key);
}
else
{
Node* del = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
Node* leftMax = root->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
swap(root->_key, leftMax->_key);
return _Erase(root->_left, key);
}
delete del;
return true;
}
}
bool _Find(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 _Insert(Node*& root ,const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (key < root->_key)
{
return _Insert(root->_left, key);
}
else if(key > root->_key )
{
return _Insert(root->_right, key);
}
else
{
return false;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
Node* _root;
};
}
