二叉搜索树(Binary Search Tree,BST)是一种二叉树,其中每个节点都具有以下性质:
假设我们插入以下元素:5, 3, 7, 1, 4, 6, 8,可以构建如下的二叉搜索树(BST):
5
/ \
3 7
/ \ / \
1 4 6 8
O(log N)
,其中N
为树中节点的数量头文件BSTree.h:进行模拟的编写 源文件test.cpp:进行测试,检查代码逻辑是否满足期望
namespace key
{
template<class K>
struct BSTreeNode
{
BSTreeNode* _left;//左指针
BSTreeNode* _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)//拷贝构造函数
{
//....
}
~BSTree()//析构函数
{
//...
}
private:
Node* _root = nullptr;//头结点
};
}
bool Find(const K& key)
{
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;//没找到才会出循环
}
这里的思路很简单:该
key< cur的_key
,就进入到左子树;反之进入右子树
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
else
{
Node* cur = _root;
Node* parent = nullptr;//这里存父亲节点,方便后续链接上
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;//搜索二叉树里不能有相同
}
}//出来后cur是nullptr,parent是叶子节点
cur = new Node(key);//重新利用
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
}
_root == nullptr
),则创建一个新节点 _root
,其键值为 key
,并将其作为根节点。key
小于当前节点的键值,则继续在当前节点的左子树中搜索;如果大于当前节点的键值,则继续在右子树中搜索。false
。cur
,其键值为 key
。cur
插入到父节点 parent
的左子树或右子树上,具体取决于新节点的键值与父节点的键值的大小关系void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
这里因为要传入根节点,所以正常无法在外部调用。我们采用子函数的方式来解决这个问题。 顺便把子函数放在
private
里,这样更安全
#include<iostream>
using namespace std;
#include"BSTree.h"
int main()
{
key::BSTree<int> t;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)//先找到在哪里删除
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else//进来就说明找到啦,就是现在的cur
{
if (cur->_left == nullptr)//左为空,就把右给父亲节点(为空也无妨)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_right)//cur在parent右,那就接到右侧
{
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)//cur在parent右,那就接到右侧
{
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;//把值一给,现在删rightMin就行了
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
}
parent
和 cur
,分别用来记录当前节点的父节点和当前节点,初始时 cur
指向根节点 _root
。while
循环中,不断遍历二叉搜索树,直到找到要删除的节点或遍历完整棵树。key
与当前节点的键值 cur->_key
的大小关系,来确定是向左子树还是右子树继续遍历。true
表示删除成功int main()
{
key::BSTree<int> t;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
t.Erase(8);
t.InOrder();
t.Erase(14);
t.InOrder();
t.Erase(4);
t.InOrder();
t.Erase(6);
t.InOrder();
return 0;
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
private:
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;
}
}
FindR
函数是对外提供的接口函数,用于从根节点开始递归查找指定键值的节点。_FindR
函数中,首先判断当前节点是否为空,如果为空则表示在当前路径上没有找到指定键值的节点,返回 false
。key
,则递归调用 _FindR
函数查找右子树。key
,则递归调用 _FindR
函数查找左子树。key
,则表示找到了目标节点,返回 true
。bool InsertR(const K& key)//难点在于,如何与父亲节点进行链接
{
return _InsertR(_root, key);
}
private:
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;
}
}
InsertR
函数是对外提供的接口函数,用于从根节点开始递归插入新节点。_InsertR
函数中,参数 root
是一个指向节点指针的引用,这样可以在递归过程中改变节点指针的指向,从而实现与父节点的链接。root
,然后返回 true
。key
,则递归调用 _InsertR
函数插入到右子树。key
,则递归调用 _InsertR
函数插入到左子树。key
,则表示树中已经存在相同键值的节点,返回 false
。 bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
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;//保存一下,过会要delete的
//这里便是引用开始发挥的作用,可以直接进行链接
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;
}
std::swap(root->_key, rightMin->_key);
return _EraseR(root->_right, key);
}
delete del;
return true;
}
}
EraseR
函数是对外提供的接口函数,用于从根节点开始递归删除指定键值的节点。_EraseR
函数中,参数 root
是一个指向节点指针的引用,这样可以在递归过程中改变节点指针的指向,从而实现删除操作。false
。key
,则递归调用 _EraseR
函数在右子树中删除。key
,则递归调用 _EraseR
函数在左子树中删除。key
,则表示找到了目标节点,进行删除操作。true
表示删除成功 BSTree(const BSTree<K>& t)//拷贝构造函数
{
_root = copy(_root);
}
Node* copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newnode = new Node(root->_key);
if (root->_left)
{
newnode->_left = copy(root->_left);
}
if (root->_right)
{
newnode->_right = copy(root->_right);
}
return newnode;
}
BSTree(const BSTree<K>& t)
中,调用了 copy
函数来复制传入二叉搜索树 t
的根节点及其所有子节点。copy
函数接收一个节点指针 root
,用于递归复制以该节点为根的子树。nullptr
。newnode
,键值为当前节点 root
的键值,表示复制当前节点。_left
。_right
。newnode
,表示复制当前节点及其所有子节点。(也是起到链接的作用)copy
函数复制传入二叉搜索树的根节点,从而完成整棵树的复制。 ~BSTree()//析构函数
{
Destory(_root);
}
void Destory(Node* root)//走个后序
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。 但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为:
最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为:
为了改进这种情况,可以使用自平衡二叉搜索树,如AVL树和红黑树。这些树在插入和删除操作时会通过旋转和重新平衡操作来保持树的平衡,从而确保树的高度较低,提高了搜索效率。
我后面也会继续学习,分享给大家!!!