C++ 二叉搜索树(BST)的实现方法
废话不多说了，直接给大家贴代码了，具体代码如下所示：
classBST
{
public:
structNode
{
intkey;//节点的key
intvalue;//节点的value
Node*left;
Node*right;
intN;//节点的叶子节点数目
Node(int_key,int_value,int_N)
{
key=_key;
value=_value;
N=_N;
}
};
BST();
~BST();
voidput(intkey,intvalue);
intget(intkey);
intdeleteKey(intkey);
private:
Node*_deleteKey(intkey,Node*x);
Node*_deleteMin(Node*x);
intsize(Node*x);
int_get(intkey,Node*x);
Node*_put(intkey,intvalue,Node*x);
Node*min(Node*x);
Node*root;
};
inlineintBST::size(Node*x)
{
if(x==nullptr)return0;
returnx->N;
}
intBST::_get(intkey,Node*x)
{
if(x==nullptr)return0;
if(x->keyright);
elseif(x->key>key)_get(key,x->left);
else{
returnx->value;
}
return0;
}
BST::Node*BST::_put(intkey,intvalue,Node*x)
{
if(x==nullptr){
Node*tmp=newNode(key,value,1);
returntmp;
}
if(x->key>key){
x->left=_put(key,value,x->left);
}
elseif(x->keyright=_put(key,value,x->right);
}
elsex->key=key;
x->N=size(x->left)+size(x->right)+1;
returnx;
}
BST::Node*BST::min(Node*x)
{
if(x->left==nullptr)returnx;
returnmin(x->left);
}
BST::BST()
{
}
BST::~BST()
{
}
voidBST::put(intkey,intvalue)
{
root=_put(key,value,root);
}
intBST::get(intkey)
{
return_get(key,root);
}
BST::Node*BST::_deleteKey(intkey,Node*x)
{
if(x->key>key)x->left=_deleteKey(key,x->left);
elseif(x->keyright=_deleteKey(key,x->right);
else{
if(x->left==nullptr)returnx->right;
elseif(x->right==nullptr)returnx->left;
else{
Node*tmp=x;
x=min(tmp->right);
x->left=tmp->left;
x->right=_deleteMin(tmp->right);
}
}
x->N=size(x->left)+size(x->right)+1;
returnx;
}
BST::Node*BST::_deleteMin(Node*x)
{
if(x->left==nullptr)returnx->right;
x->left=_deleteMin(x->left);
x->N=size(x->left)+size(x->right)+1;
returnx;
}
intBST::deleteKey(intkey)
{
return_get(key,root);
}
以上所述是小编给大家介绍的C++二叉搜索树(BST)的实现方法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！