C++ 详解数据结构中的搜索二叉树
时间：2022-12-28 09:40:28|栏目：C代码|点击： 次
定义
搜索二叉树，也称有序二叉树，排序二叉树，是指一棵空树或者具有下列性质的二叉树：
1、若任意节点的左子树不空，则左子树上的所有节点的值均小于它的根节点的值
2、若任意节点的右子树不空，则右子树上的所有节点的值均大于它的根节点的值
3、任意节点的左右子树也称为二叉查找树。
4、没有键值相等的节点。
5、搜索二叉树中序遍历为有序数组。
结构代码实现
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(left)
,_right(right)
,_key(key)
{}
};
查找某个元素
在搜索二叉树b中查找x的过程
- 若树是一个空树，则搜索失败，否则：
- 若x等于b的根节点的键值，则查找成功；否则：
- 若x小于b的根节点的键值，则搜索左子树；否则：
- 若x大于b的根节点的键值，则搜索右子树。
非递归实现
typrdef BSTreeNode<K> Node;
?
Node* find(const K& key)
{
Node*cur =_root;
while(cur)
{
if(cur->_key<key)
cur=cur->right;
else if(cur->_key>key)
cur=cur->left;
else
return cur;
}
return nullptr;
}
递归实现
typrdef BSTreeNode<K> Node;
?
Node* _findr(Node* root,const K& key)
{
if(root==nullptr)
{
return nullptr;
}
if(root->_key<key)
{
return _findr(root->_right);
}
else if(root->_key>key)
{
return _findr(root->_left);
}
else
return root;
}
构造搜索二叉树
- 若树为空树，则直接插入；否则
- 若插入值大于根节点的键值，则插入到右子树中，以此递归；否则
- 若插入值小于根节点的键值，则插入到左子树中
非递归实现：
bool insert(const K& key)
{
if(_root==nullptr)
{
_root=new Node(key);
return true;
}
Node* parent=nullptr;
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
return false;
}
cur=new Node(key);
if(parent->_key<key)
{
parent->_right=cur;
}
else
parent->_left=cur;
return true;
}
递归实现：
bool _insertR(Node* &root,const K&key)
{
if(root==NULL)
{
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;
}
往搜索二叉树中插入元素
向一个二叉搜索树b中插入一个节点s的算法，过程为：
- 若b是空树，则将s所指结点作为根节点插入，否则：
- 若s->data等于b的根节点的数据域之值，则返回，否则：
- 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
- 把s所指节点插入到右子树中。（新插入节点总是叶子节点）
搜索二叉树删除节点
重难点
二叉搜索树的结点删除比插入较为复杂，总体来说，结点的删除可归结为三种情况：
- 如果结点z没有孩子节点，那么只需简单地将其删除，并修改父节点，用NULL来替换z；
- 如果结点z只有一个孩子，那么将这个孩子节点提升到z的位置，并修改z的父节点，用z的孩子替换z；
- 如果结点z有2个孩子，那么查找z的后继y，此外后继一定在z的右子树中，然后让y替换z
非递归实现
bool Erase(const K& key)
{
Node* parent=nullptr;
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->_left==cur)
{
parent->_left=cur->_right;
}
else
{
parent->_right=cur->_right;
}
}
delete cur;
}
else if(cur->_right==nullptr)
{
if(cur==_root)
{
_root=cur->_left;
}
else
{
if(parent->_left==cur)
{
parent->_left=cur->_left;
}
else
{
parent->_right=cur->_right;
}
}
}
else //左右都不为空
{
Node* minRight=cur->_right;
while(minRight->_left)
{
minRight=minRight->_left;
}
k min = minRight->_key;
this->Erase(min);
cur->_key=min;
}
return true;
}
}
return false;
}
递归实现
// 如果树中不存在key，返回false
// 存在，删除后，返回true
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
{
//找到了，root就是要删除的节点
if(root->_left == nullptr)
{
Node* del=root;
root=root->_right;
delete del;
}
else if(root->_right==nullptr)
{
Node* del = root;
root=root->_left;
delete del;
}
else
{
Node* minRight=root->_right;
while(minRight->_left)
{
minRight=minRight->_left;
}
K min=minRight->_key;
//转化为root的右子树删除min
_EraseR(root->_right,min);
root->_key=min;
}
return true;
}
}
上一篇：C语言文件操作详情(一)
栏 目：C代码
下一篇：OpenCV实现简单录屏功能
本文标题：C++ 详解数据结构中的搜索二叉树
本文地址：http://www.codeinn.net/misctech/222430.html
