二叉搜索树
什么是二叉搜索树?
二叉搜索树(Binary Search Tree 简称BST)又称二叉排序树,是一种二叉树的特殊形式,它在每个节点上存储的键值满足以下性质:
- 若它的左子树不为空,则左子树上的所有节点的 值都小于根节点的值
- 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
根据这个性质,我们可以利用二叉搜索树进行高效的插入,删除和搜索操作。
二叉搜索树的操作
查找
- 从根节点开始比较,如果比根节点大则往右查找,反之往左查找。
- 最多查找高度次,走到空,还没找到,这个值不存在。
上面的图,比如果要查找4.
4 < 8,往左走,找到3,4大于3,往右走,找到6,6大于4,往左走,找到4,4 == 4,查找成功。
重复上面的操作,直到走到4,4小于5,往右走,为nullptr,不存在这个值,返回false。
void Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
插入
- 树为空,则直接新增节点,赋值给root指针
- 树非空,按二叉搜索树性质查找插入位置,插入新节点。
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 if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
如果要插入的值(val)比当前节点的key大,则往右子树移动;反之往左子树移动,直到找到合适的插入位置。
在找到插入位置的时候,不要直接 cur = new Node(val)
,这样创建的是临时变量,出了作用域会销毁,可以用一个临时变量(parent)记录查找过程中cur的上一个位置,在找到合适的位置的时候,与parent节点的key进行比较之后,在进行链接。
删除
删除有点麻烦,
看这棵树,把7删了,很简单,delete了就行了,把14给删了呢?右子树的所有节点一定大于根节点,把13链接在10的右子树即可,就算13下面还有子树,也不会导致这个树混乱。那么删3呢?3有两个孩子,这个时候可以找人把3给替代了,从左子树找最大的节点,或者找右子树的最小节点完成替代。
删除分三种情况
- 没有孩子
- 一个孩子
- 两个孩子 (找左子树的最大节点 or 右子树的最小节点)
首先要找到要删除节点的位置(cur),但光找到一个节点的位置不够,还要找到当前节点的父节点(parent)。如果说cur的左子树为空,并且要删除的节点为根节点。
也就是当前cur位于8的位置,此时要删除,把根节点移动到cur的右子树位置即可。
若要删的不是根节点。
此时cur=6,parent=3,要先判断cur与parent的关系,然后直接将parent与cur的子树链接在一起即可。这是要删除节点的左子树为空的情况,右子树为空与这个一样。
若要删除的节点有两个孩子。
要先找到左子树中最大的节点(leftMax),将根节点的key与leftMax的key交换。在找leftMax的过程中记录下来其父节点(parent),判断parent和leftMax的关系。最后将parent与leftMax的左右节点(都为空)链接一下即可。
当然还有一种特殊情况。
这里要删除8,而3就是左子树中最大的节点。所以这种情况下的parent初始值不能设为nullptr,而是初始化为cur。leftMax还是初始化为cur->left文章来源:https://www.toymoban.com/news/detail-731245.html
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 (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
{}
delete cur;
return true;
}
}
源代码
非递归版
#pragma once
template <class K>
class BSTreeNode
{
public:
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& x)
:_key(x)
,_right(nullptr)
,_left(nullptr)
{}
};
template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
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 if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
void Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
bool erase(const K& key)
{
Node* parent = _root;
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 (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* parent = cur;
Node* leftMax = cur->_left;
while (leftMax->_right)
{
parent = leftMax;
leftMax = leftMax->_right;
}
swap(leftMax->_key, _root->_key);
if (parent->_left == leftMax)
{
parent->_left = leftMax->_left;
}
else
{
parent->_right = leftMax->_right;
}
cur = leftMax;
}
delete cur;
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
Node* _root;
};
递归版文章来源地址https://www.toymoban.com/news/detail-731245.html
#pragma once
template <class K>
class BSTreeNode
{
public:
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& x)
:_key(x)
, _right(nullptr)
, _left(nullptr)
{}
};
template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
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);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
bool _erase(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key > key)
{
return _erase(root->_left,key);
}
else if (root->_key < 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;
}
return false;
}
bool _Insert(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key > key)
{
return _Insert(root->_left,key);
}
else if (root->_key < key)
{
return _Insert(root->_right,key);
}
else
{
return false;
}
}
bool _Find(Node* root, const K& key)
{
if (root == nullptr) {
return false;
}
if (root->_key > key)
{
return _Find(root->_left);
}
else if (root->_key < key)
{
return _Find(root->_right);
}
else
{
return true;
}
}
Node* _root;
};
到了这里,关于数据结构---二叉搜索树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!