二叉搜索树的查找规则
从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
最多查找高度次，走到到空，还没找到，这个值不存在
二叉搜索树(二叉排序树)性质
非空左子树的所有值小于根节点的值
非空右子树的所有值大于根节点的值
左右子树都是二叉搜索树
第一个不满足，因为值为5的节点在值为10的节点的右边，正常来说10的右边都应该比10大
二叉搜索树的中序遍历
遍历，一定可以得到一个递增的序列 中序为：1 3 4 6 7 8 10 13 14
二叉搜索树的实现 (非递归)
插入
分为两种情况
若插入的值在二叉树中不存在，则通过比较进行插入
若插入11，因为11比8大，所以跟10比较，而11比10大，所以走10的右子树14，14与11比较，因14>11，所以走14的左子树13，11与13比较，因13>11，故作为13的左子树，遇见NULL指针停止
若插入的值，在二叉树中存在
因为插入值13与二叉树中的值13相等，则直接返回false
实际上创建节点后，需要与二叉搜索树进行连接，去当前创建节点的上一个节点parent，
通过判断cur节点是parent节点左子树还是右子树 进行连接
bool Insert(const K& key) { if (_root = nullptr)//若root根节点为nullptr { _root = new Node(key); return true; } Node* cur = _root; Node* parent = NULL;//用于接收cur之前的节点 while (cur != NULL) { if (cur->_key > key)//若插入的值比cur值小 { parent = cur; cur = cur->_left; } else if (cur->_key < key)//若插入的值比cur值大 { parent = cur; cur = cur->_right; } else//若相等，则直接返回false { return false; } } //遇见空指针，连接新节点 //由于不知道parent的左还是右连接key，所以需要判断 cur = new Node(key); if (parent->_key > key) { parent->_left = cur; } else { parent->_right = cur; } return true; }
中序遍历
inorder需要传根，但是由于_root是类的私有成员变量，所以没办法从.c文件传过来
若将inorder函数设为缺省值，不可以通过编译
缺省值必须是常量或者全局变量，而root不是全局变量/常量 ，所以不能用缺省值
访问成员变量需要用this指针，而此时_root并没有this指针去指向
所以采用嵌套一层函数的方式，这样调用inorder函数时，不用传参数过来也可以解决问题
查找
bool Find(const K& key) { Node* cur = _root; while (cur != NULL) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { return true; } } return false; }
删除 (重点)
删除共分为三种情况
1. 要删除节点无孩子节点
删除4后，直接将6的左子树置为NULL
2.要删除节点只有左孩子节点/右孩子节点
3.要删除节点有左孩子和右孩子节点
删除8节点，就需要寻找左子树的最大节点或者右子树最小节点 来当树的根节点
左子树的最大节点是最右节点
右子树的最小节点是最左节点
假设删除节点8，通过右子树的最小节点来进行替换，将右子树的最小节点替换掉cur节点值，删除右子树的最小节点即可
由于叶子节点的删除可以算为左为空/右为空的情况，所以只需考虑左为空/右为空 或者 删除节点有左孩子和右孩子节点 即可
左为空
左为空时，使用parent节点去接收cur的右子树，但是还需判断下cur的右子树节点在parent的左子树还是右子树
需要考虑cur节点作为根的情况，此时的parent节点为NULL，NULL->right就会报错
为了解决这个问题，把cur的右子树的节点作为根，然后直接删除cur节点
