如何进行搜索二叉树分析，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。
一、搜索二叉树
1、定义：它是一棵排序二叉树，可为空树。
2、性质：
每个节点都有一个作为搜索依据的关键码（key），所有节点的关键码互不相同；
左子树上所有节点的关键码（key）都小于根节点的关键码（key）；
右子树上所有节点的关键码（key）都大于根节点的关键码（key）；
左、右子树都是二叉搜索树。
二、源代码
1、定义节点
计算
安全
数据库
网络和加速
企业服务
template<class K,class V>
struct BSTreeNode
{
BSTreeNode<K,V> *_left;//左节点
BSTreeNode<K,V> *_right;//右节点
K _key;//节点权值
V _value;
BSTreeNode(const K& key,const V& value)
:_key(key)
,_value(value)
,_left(NULL)
,_right(NULL)
{}
};2、搜索二叉树及其相关实现
template<class K,class V>
class BSTree
{
typedef BSTreeNode<K,V> Node;
public:
BSTree()
:_root(NULL)
{}
//非递归
Node* Find(const K& key)
{
return _Find(_root,key);
}
bool Insert(const K& key,const V& value)
{
return _Insert(_root,key,value);
}
bool Remove(const K& key)
{
return _Remove(_root,key);
}
//递归
bool InOrder() //中序遍历 --> 有序序列
{
return _InOrder(_root);
cout<<endl;
}
Node* FindR(const K& key)
{
return _FindR(_root,key);
}
bool InsertR(const K& key,const V& value)
{
return _InsertR(_root,key,value);
}
bool RemoveR(const K& key)
{
return _RemoveR(_root,key);
}
protected:
//非递归
Node* _Find(Node *root,const K& key)
{
if(root == NULL) return NULL;
Node *cur=root;
if(cur->_key > key)
{
cur=cur->_right;
}
else if(cur->_key < key)
{
cur=cur->_left;
}
else
{
return cur;
}
return NULL;
}
bool _Insert(Node *&root,const K& key,const V& value)
{
if(root == NULL)
{
root=new Node(key,value);
return true;
}
Node *cur=root;
Node *parent=NULL;
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->_right=new Node(key,value);
parent->_right=parent;
}
else
{
parent->_left=new Node(key,value);
parent->_left=parent;
}
return true;
}
bool _Remove(Node*& root,const K& key )
{
if(root == NULL) return false;
Node *cur=root;
Node *parent=NULL;
while(cur) //找节点
{
if(cur->_key > key)
{
parent=cur;
cur=cur->_left;
}
else if(cur->_key < key)
{
parent=cur;
cur=cur->_right;
}
else //找到节点
{
if(cur->_left == NULL)//左为空
{
if(parent == NULL)
root=cur->_right;
else if(parent->_left == cur)
parent->_left=cur->_right;
else
parent->_right=cur->_right;
}
else if(cur->_right == NULL)//右为空
{
if(parent == NULL)
root=cur->_left;
else if(parent->_left == cur)
parent->_left=cur->_left;
else
parent->_right=cur->_left;
}
else //左右都不为空
{
Node *parent=cur;
Node *left=cur->_right;//右子树的最左节点
while(left->_left)
{
left=left->_left;
}
cur->_key=left->_key;//替换结点
cur->_value=left->_value;
if(parent->_left == left)
parent->_left=left->_left;
else
parent->_right=left->_right;
delete left;
}
}
return true;
}
return false;
}
//递归
bool _InOrder(Node *root)
{
if(root == NULL) return false;
_InOrder(root->_left);
cout<<root->_left<<" ";
_InOrder(root->_right);
return true;
}
Node* _FindR(Node *root,const K& key)
{
if(root == NULL) return NULL;
if(root->_key == key)
return root;
else if(root->_key > key)
return _FindR(root->_left,key);
else
return _FindR(root->_right,key);
}
bool _InsertR(Node *root,const K& key,const V& value)
{
if(root == NULL)
{
root=new Node(key,value);
return true;
}
if(root->_key > key)
return _InsertR(root->_left,key,value);
else if(root->_key < key)
return _InsertR(root->_right,key,value);
else
return false;
}
bool _RemoveR(Node *root,const K& key)
{
if(root == NULL) return false;
if(root->_key > key)
return _RemoveR(root->_left,key);
else if(root->_key < key)
return _RemoveR(root->_right,key);
else //找到节点
{
Node *del=NULL;
if(root->_left == NULL)
root=root->_right;
else if(root->_right == NULL)
root=root->_left;
else
{
Node *parent=NULL;
Node *left=root;
while(left->_left)
{
parent=left;
left=left->_left;
}
root->_key=left->_key;
root->_value=left->_value;
del=left;
if(parent->_left == left)
parent->_left=left->_left;
else
parent->_right=left->_right;
delete del;
return true;
}
}
return false;
}
protected:
Node *_root;
};3、总结：
搜索二叉树是一棵排序二叉树，可为空树。它的每一个节点都遵从搜索二叉树的性质。
搜索二叉树的中序遍历后为升序序列；其查找根据key值以及性质进行；其插入需先根据其key值找到插入的节点，随后添加节点，另外其key值唯一；
其删除节点时，需分3种情况：
（1）仅左为空；
（2）仅右为空；
（3）该节点左右皆不为空。
删除该节点，即需 找到 右子树的最左节点 或 左子树的最右节点，作为替换结点。
看完上述内容，你们掌握如何进行搜索二叉树分析的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注亿速云行业资讯频道，感谢各位的阅读！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
