前言：复习就不想用长篇大论来解释二叉搜索了，尽量用模板化的框架来帮助写二叉搜索的增删改。对于find和insert还是好记得，但是erase确实情况太多，不多写没办法记
迭代版
find
find步骤：
- 比key大往右早，比key大往左找
- 用一个cur指针像遍历链表一样去找
- 找到返回对应的Node
总结：根据二叉搜索的性质像遍历链表一样找到对应的节点。
代码：
node* find(const k& key)
{
if (root == nullptr) return nullptr;
node* cur = root;
while (cur)
{
if (key < cur->key) cur = cur->left;
else if (key > cur->key) cur = cur->right;
else return cur;
}
return nullptr;
}
insert
insert步骤：
- 在find的基础上加多一个parent指针
- 用cur和parent像遍历链表一样找到合适的位置
- 比key大就往右，比key小就往左
- 找到合适的位置new一个节点然后用parent指向它
- 如果根为空，就创建一个根
如果熟悉这个流程，就不要看流程了，没用。
直接看强调的细节
1.用parent指向新创建的节点时要比较新的key和parent的key的大小，若新节点大，用parent的right连newnode。若新节点小，用parent的left连newnode。
这个细节在写二叉搜索代码是最重要的。增和删都必须要做！！！
代码：
bool insert(const k& key, const v& val)
{
if (root == nullptr)
{
root = new node(key, val);
return true;
}
node* cur = root, * parent = nullptr;
while (cur)
{
if (key < cur->key) {
parent = cur;
cur = cur->left;
}
else if (key > cur->key) {
parent = cur;
cur = cur->right;
}
else return false;//重复不插入
}
node* newnode = new node(key, val);
if (parent->key > key) parent->left = newnode;
else parent->right = newnode;
return true;
}
erase
erase步骤：
- 先找到对应的节点
- 考虑四种情况：分别是节点左右孩子为空，左孩子为空，右孩子为空，左右孩子都不为空。前三种种情况再细分这个节点是否为根节点
- 左右孩子为空且该点是根节点的话，把root = nullptr再删除。不是根的话直接删除
- 左孩子为空且是根节点，直接让root = root -> right，并删除原先的根节点。不是根节点的话，根据insert讲的分类操作来让目标点的父亲节点继承目标点的孩子节点。并删除目标点
- 右孩子为空和4同理，记住必须分类
- 左右孩子都不为空不需要考虑是否为根。找到左子树最大的点或者右子树最小的点。然后删除它，并把它的key和value拷贝给原来要删除的节点。删除完还要继承最小/最大节点的孩子。继承的时候也要分类讨论。
- 如果点6想写成递归的话，可以找到最小或者最大节点，然后递归调用自己去删除。这样就不用处理继承问题了。删除完再把最小/最大节点的值拷贝给原来要删除的节点
bool erase(const k& key)
{
node* cur = root, * parent = nullptr;
while (cur)
{
if (key < cur->key)
{
parent = cur;
cur = cur->left;
}
else if (key > cur->key)
{
parent = cur;
cur = cur->right;
}
else
{
if (cur->left == nullptr && cur->right == nullptr)
{
if (parent == nullptr) root = nullptr;
else if (cur->key < parent->key) parent->left = nullptr;
else parent->right = nullptr;
delete cur;
cur = nullptr;
}
else if (cur->right == nullptr)
{
if (parent == nullptr && cur == root) root = root->left;
else if (cur->val < parent->val) parent->left = cur->left;
else parent->right = cur->left;
delete cur;
cur = nullptr;
}
else if (cur->left == nullptr)
{
if (parent == nullptr && cur == root) root = root->right;
else if (cur->val < parent->val) parent->left= cur->right;
else parent->right = cur->right;
delete cur;
cur = nullptr;
}
else
{
node* minNode = cur->left, *parent = cur;
while (minNode->right)
{
parent = minNode;
minNode = minNode->right;
}
//递归
/*int mk = minNode->key, mv = minNode->val;
this->erase(mk);
cur->key = mk;
cur->val = mv;*/
if (parent->key < minNode->key) parent->right = minNode->left;
else parent->left = minNode->left;
cur->key = minNode->key;
cur->val = minNode->val;
delete minNode;
minNode = nullptr;
}
return true;
}
}
return false;
}
递归版
不懂迭代的思路是写不出递归的。
find
思路
1.比key大往右找，比key小往左找
2.找不到返回null
3.找到返回root
node* _find(const k& key, node* root)
{
if (root == nullptr) return nullptr;
else if (root->key < key) return _find(key, root->right);
else if (root->key > key) return _find(key, root->left);
else return root;
}
insert
insert有两种写法：
一种是有返回值得写法，一种是没有返回值得写法。这里推荐没有返回值得写法。
有返回值的写法：
思路：
1.如果找到空的位置，直接创建一个新的节点，并返回
2.如果比key小，往左子树插入。如果比key大，往右子树插入。
3.插入完成之后返回根节点root。
总体而言就是前序遍历
node* _insert1(const k& key, const v& val, node* root)
{
if (root == nullptr)
{
root = new node(key, val);
return root;
}
else if (root->key < key) root->right = _insert1(key, val, root->right);
else if (root->key > key) root->left = _insert1(key, val, root->left);
return root;
}
没有返回值的写法：
思路：我们知道，插入节点需要知道新节点的父亲是谁。没有返回值很难做到这一点，但是有一个很好的办法，就是引用参传。
void _insert2(const k& key, const v& val, node*& root)
{
if (root == nullptr)
root = new node(key, val);
else if (root->key < key)
_insert2(key, val, root->right);
else
_insert2(key, val, root->left);
}
讲解一下这是如何把父亲节点和新节点连起来的。
root是一个引用，在传参的时候，它有可能传给了root->right,也可能传给了root->left，因此root有一个别名就是上一层的root->right/left指针。因此我们可以借助这个指针来连接父节点和新节点。（你只要记住，此时的root就是父亲节点的左指针或者右指针就行了。）
root =new node()的意思其实就是父亲节点的右/左指针指向新插入的节点
erase
erase用递归写还是先找再删的流程
1.找
2.删，分三种情况。（和迭代一样），**其中第一种和第二种由于是继承的操作，因此用引用可以直接解决问题了。**第三种情况还是得用迭代的方法来做，此时引用不起作用了，因为要找右边最小的节点，离root很远了。
void _erase(const k& key, node*& root)
{
if (root == nullptr) return;
else if (root->key < key) _erase(key, root->right);
else if (root->key > key) _erase(key, root->left);
else
{
if (root->left == nullptr)
{
node* del = root;
root = root->right;
delete del;
del = nullptr;
}
else if (root->right == nullptr)
{
node* del = root;
root = root->left;
delete del;
del = nullptr;
}
else
{
node* minNode = root->right, *parent = root;
while (minNode->left)
{
parent = minNode;
minNode = minNode->left;
}
k minkey = minNode->key;
v minval = minNode->val;
if (parent->key < minNode->key) parent->right = minNode->right;
else parent->left = minNode->right;
delete minNode;
root->key = minkey, root->val = minval;
}
}
}
说一下：第一种情况和第二种情况的root = root->right,其实就是父亲节点的右指针指向了删除节点的下一个节点。（root->right = root->right->right)
题目
复习完模板把这两道模板题分别用递归和迭代写一下
搜索二叉树插入
ac递归代码：
class Solution {
public:
void insert(TreeNode*& root, int val)
{
if(root == nullptr)
{
root = new TreeNode(val);
return;
}
if(root->val < val) insert(root->right, val);
else insert(root->left, val);
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
insert(root, val);
return root;
}
};
ac迭代代码：
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root == nullptr)
{
return new TreeNode(val);
}
TreeNode* cur = root, *parent = nullptr;
while(cur)
{
parent = cur;
if(cur->val < val) cur = cur->right;
else cur = cur->left;
}
TreeNode* newnode = new TreeNode(val);
if(parent->val < val) parent->right = newnode;
else parent->left = newnode;
return root;
}
};
删除搜索二叉树节点
ac递归代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void erase(TreeNode*& root, int key)
{
if(root == nullptr) return;
if(root->val < key) erase(root->right, key);
else if(root->val > key) erase(root->left, key);
else
{
if(root->left == nullptr)
{
TreeNode* del = root;
root = root->right;
delete del;
}
else if(root->right == nullptr)
{
TreeNode* del = root;
root = root->left;
delete del;
}
else
{
TreeNode* minNode = root->right, *parent = root;
while(minNode->left)
{
parent = minNode;
minNode = minNode->left;
}
int k = minNode->val;
if(parent->val < minNode->val) parent->right = minNode->right;
else parent->left = minNode->right;
delete minNode;
root->val = k;
}
}
}
TreeNode* deleteNode(TreeNode* root, int key) {
erase(root, key);
return root;
}
};
迭代ac代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int val) {
TreeNode* cur = root, *parent = nullptr;
while(cur)
{
if(cur->val < val)
{
parent = cur;
cur = cur->right;
}
else if(cur->val > val)
{
parent = cur;
cur = cur->left;
}
else
{
if(cur->left == nullptr)
{
if(parent == nullptr && cur == root)
{
root = root->right;
delete cur;
cur = nullptr;
}
else
{
if(parent->val < cur->val)
parent->right = cur->right;
else
parent->left = cur->right;
delete cur;
cur = nullptr;
}
}
else if(cur->right == nullptr)
{
if(parent == nullptr && cur == root)
{
root = root->left;
delete cur;
cur = nullptr;
}
else
{
if(parent->val > cur->val)
parent->left = cur->left;
else
parent->right = cur->left;
delete cur;
cur = nullptr;
}
}
else
{
TreeNode* minNode = cur->right, *parent = cur;
while(minNode->left)
{
parent = minNode;
minNode = minNode->left;
}
int v = minNode->val;
if(parent->val < minNode->val) parent->right = minNode->right;
else parent->left = minNode->right;
delete minNode;
cur->val = v;
}
}
}
return root;
}
};
