二叉搜索树基本概念与实现
2023-12-13 06:43:40
目录
基本概念
根的左节点比根小
根的右节点比根大
左右子树都满足
搜索二叉树的中序遍历是升序
模拟实现
完整代码
#pragma once
template<class K>
struct BSNode
{
BSNode<K>* _left;
BSNode<K>* _right;
K _val;
BSNode(const K& val)
:_left(nullptr)
, _right(nullptr)
, _val(val)
{
}
};
template<class K>
class BSTree
{
typedef BSNode<K> Node;
public:
bool insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_val > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_val > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
bool Find(const K& key)
{
if (_root == nullptr)
{
return false;
}
Node* cur = _root;
while (cur)
{
if (cur->_val > key)
{
cur = cur->_left;
}
else if (cur->_val < key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_val > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val < key)
{
parent = cur;
cur = cur->_right;
}
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;
}
//右为空
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;
}
//左右都不为空
else
{
Node* parent = cur;
Node* subnode = cur->_right;
while (subnode->_left!=nullptr)
{
parent = subnode;
subnode = subnode->_left;
}
swap(subnode->_val, cur->_val);
if (subnode == parent->_left)
{
parent->_left = subnode->_right;
}
else
{
parent->_right = subnode->_right;
}
delete subnode;
}
return true;
}
}
return false;
}
bool insertR(const K& key)
{
return _insertR(_root,key);
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
bool _insertR(Node*& root,const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_val < key)
{
_insertR(root->_right, key);
}
else if (root->_val > key)
{
_insertR(root->_left, key);
}
else
{
return false;
}
}
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_val > key)
{
_FindR(root->_left, key);
}
else if (root->_val < key)
{
_FindR(root->_right, key);
}
else
{
return true;
}
}
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_val > key)
{
return _EraseR(root->_left, key);
}
else if (root->_val < key)
{
return _EraseR(root->_right, key);
}
else
{//删除
if (root->_left == nullptr)
{
Node* del = root;
root = root->_right;
delete del;
return true;
}
else if (root->_right == nullptr)
{
Node* del = root;
root = root->_left;
delete del;
return true;
}
else
{
Node* subnode = root->_right;
while (subnode->_left != nullptr)
{
subnode = subnode->_left;
}
swap(root->_val, subnode->_val);
return _EraseR(root->_right, key);
}
}
}
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_val << ' ';
_Inorder(root->_right);
}
Node* _root = nullptr;
};
文章来源:https://blog.csdn.net/m0_61381297/article/details/134961562
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!