本文主要是介绍C++ BinarySercahTree recursion version,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
for循环版本的:C++ BinarySercahTree for version-CSDN博客
Inorder()在c++ BinarySerschTree for verison写了。
还是按照那种嵌套的方式来写递归。
现在来写查找
FindR()
bool FindR(){return _FindR(_root);}
然后_FindR()函数写递归具体实现:
假设要找13,就让13和root比,key大root就往右,key小就往左,找到空就不找了,找到了
bool _FindR(Node* root,const K& key){
while(cur)
{Node* cur = root;if (root == nullptr)return false;if (key > cur->_key) return _FindR(cur->_right, key);else if (key < cur->_key) return _FindR(cur->_left, key);return true;
}}
假设要找12,那找到空都找不到,那就返回false
bool _FindR(Node* root,const K& key)
{while (cur){Node* cur = root;if (root == nullptr)return false;if (key > cur->_key) return _FindR(cur->_right, key);else if (key < cur->_key) return _FindR(cur->_left, key);return true;return true}return false;}
InsertR()
bool InsertR(){return _Insert(root,key);}
bool _InsertR(Node* _root,const K& key){if (key > root->_key) return _InsertR(root->_right, key);else if (key < root->_key) return _InsertR(root->_left, key);else return false;//相等不让插入}
push
在root为空的时候插入
if (root == nullptr) { root = new Node(key); return true; }
链接
还可以用快慢指针的方式链接。
也可以用下面这种方式:引用
bool _InsertR(Node*& _root,const K& key)
画图解析:
要插入9,root最后会走到空节点:
root又是一个引用,是10节点的别名:
root = new Node(key);
把key值给给root就是给root->letf
这样就链起来了:
测试:
EraserR
基本架构
bool EraserR(const K& key){return _EraserR(_root, key);}
bool _EraserR(Node* root,const K& key){if (root == nullptr) return false;if (key > root->_key) return _EraserR(root->_right, key);else if (key < root->_key) return _EraserR(root->_left, key);else{//否则就是找到了//开始删除}}
下面有3种情况要处理
左为空,右为空,左右都不为空
先看左为空的情况:
假设我们要删除10,10比8小,root往右走,走到10,找到了,root->left==nullptr
然后删除10,再把8和14链起来
bool _EraserR(Node*& root,const K& key){if (root == nullptr) return false;if (key > root->_key) return _EraserR(root->_right, key);else if (key < root->_key) return _EraserR(root->_left, key);else{//否则就是找到了//开始删除Node* del = root;if (root->_left == nullptr)root= root->_right;delete del;}}
这里仍然用到了引用:
&root=root->right
例如10是8的别名:
然后 root= root->_right;
root是root->right的别名,也就是10,10的right是14,把14给给8:
把3给给1,就是把14给给8,就把8和14链起来了。
再把10给删掉:
右边为空也一样:
if (root->_right == nullptr){root = root->_left;delete del;}
如果要删除的节点为root,比如要删除8:
这篇关于C++ BinarySercahTree recursion version的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!