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：