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->key right=_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->key right=_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)的实现方法,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持!