目录
第一节：基本介绍
1-1.代替法
第二节：基本代码实现
2-1.节点类
2-2.搜索树类
2-2-1.构造函数
2-2-2.析构函数
2-2-3.Insert
2-2-4.Erase
第三节：搜索树的迭代器
3-1.迭代器类
3-2.搜索树类
3-3.测试迭代器
第四节：下期预告
第一节：基本介绍
搜索二叉树是一种二叉树，其特征是左节点一定比根小，右节点一定比根大，即左节点<根<右节点。
这样一来寻找每个值时，当前节点小就向右走，当前节点大了就往左走，一次比较可以排除一层的节点，效率是很高的，时间复杂度为O(LogN)。
搜索二叉树可以很简单的增加节点，但是不允许保存相等的数据，也可以使用代替法删除节点。
1-1.代替法
若被删除节点的左右节点都不为空，则找左子树的最大节点，或者右子树的最小节点代替被删除的节点。
若被删除节点的左子树为空，就让其父节点指向其右子树。
若被删除节点的右子树为空，就让其父节点指向其左子树。
第二节：基本代码实现
2-1.节点类
节点类不仅需要保存左右节点，还需要保存父亲节点，因为在删除节点时需要修改父亲的左节点(或右节点)。
将节点类设置成模板使它可以按需保存不同类型的数据：
template<class T>
class Node {
public:Node(T val = 0, Node* left = nullptr, Node* right = nullptr) :_val(val),_left(left),_right(right){}T _val;Node<T>* _left;Node<T>* _right;Node<T>* _parent;
};2-2.搜索树类
搜索树也设置成模板，保存不同数据，同时设置一个哨兵位，它的作用是在插入数据时保持根节点与其他节点的一致性(即都有父亲节点)：
template<class T>
class SearchBinaryTree
{
private:Node<T>* _root = nullptr; // 哨兵位，规定它的左孩子为根
};2-2-1.构造函数
接收一个vector<T>数组，将数组中的每个元素分别插入搜索树中：
SearchBinaryTree(std::vector<T>& arr)
{_root = new Node<T>(); // 初始化哨兵位for (const T& num : arr) {Insert(num); // 插入函数，后面实现}
}如果像使用原生的数组，例如 int arr[]或者字符串，则需要接收两个参数：一个指针和该数组的元素个数。
2-2-2.析构函数
析构函数可以通过递归来一个一个释放空间，从叶子开始释放空间：
void DeleteTree(Node<T>* root) {if (root == nullptr)return;DeleteTree(root->_left);DeleteTree(root->_right);delete root;
}~SearchBinaryTree()
{DeleteTree(_root);
}2-2-3.Insert
这个函数用来插入某一个值，不会插入重复的值：
void _Insert(Node<T>* root,T num)
{// 二叉搜索树的特点是左<根<右// 所以根据num与当前节点的值的大小关系来决定递归左边还是右边// 只要下一个位置为空就将num放到下一个位置if (root->_val > num) {if (root->_left)_Insert(root->_left, num);else {Node<T>* newNode = new Node<T>(num);root->_left = newNode;newNode->_parent = root;return;}}else if (root->_val < num) {if(root->_right)_Insert(root->_right, num);else {Node<T>* newNode = new Node<T>(num);root->_right = newNode;newNode->_parent = root;return;}}else { // num与_root->_val相同，不插入重复值return;}
}// 插入节点
void Insert(T num)
{// 因为规定_root的左一定为根，所以需要特殊处理// 防止哨兵位的右也保存一些值if (_root->_left == nullptr){_root->_left = new Node<T>(num);_root->_left->_parent = _root;}_Insert(_root->_left,num);
}2-2-4.Erase
该函数用来删除某个值，如果该值不存在就不处理。
删除就需要上面讲到的代替法了：
void _Erase(Node<T>* node)
{Node<T>* subNode = nullptr; // 记录去替换的节点if (node->_left && node->_right) // 左右子树不为空，找左子树的最大节点{ // 或者找右子树的最小节点subNode = node->_left;while (subNode->_right) {subNode = subNode->_right;}/*subNode = node->_right;while (subNode->_left) {subNode = subNode->_left;}*/// 找到后将node替换// 1.把subNode解绑// subNode最大，它一定没有右子树，可能有左子树if (subNode->_parent->_left == subNode){subNode->_parent->_left = subNode->_left;}else{subNode->_parent->_right = subNode->_left;}// 如果有左子树，则左子树的根的父亲更新为subNode的父亲if(subNode->_left) subNode->_left->_parent = subNode->_parent;// 2.替换node// 替换值即可，然后将subNode删除Node<T>* Parent = node->_parent;node->_val = subNode->_val;delete subNode;}else if (node->_left) // 右子树为空，父亲指向左{Node<T>* Parent = node->_parent;if (Parent->_left == node) // node是父亲的左节点{Parent->_left = node->_left;}else // node是父亲的右节点{Parent->_right = node->_left;}node->_left->_parent = Parent;delete node;}else if (node->_right) // 左子树为空，父亲指向右{Node<T>* Parent = node->_parent;if (Parent->_left == node) // node是父亲的左节点{Parent->_left = node->_right;}else // node是父亲的右节点{Parent->_right = node->_right;}node->_right->_parent = Parent;delete node;}else // 左右子树都为空，使父亲指向空并删除{Node<T>* Parent = node->_parent;if (Parent->_left == node) // node是父亲的左节点{Parent->_left = nullptr;}else // node是父亲的右节点{Parent->_right = nullptr;}delete node;}
}
// 删除节点
void Erase(T num)
{Node<T>* root = _root->_left;while (root) {if (num > root->_val)root = root->_right;else if (num < root->_val)root = root->_left;else {_Erase(root);break;}}
}可以看见，当删除的是根节点时，因为它有一个哨兵位_root作为父亲，而父亲需要连接subNode，这样它被代替时也可以使用与普通节点一样的代码。
如果单纯使用nullptr作为根的父节点，还需要分类讨论。
第三节：搜索树的迭代器
完成上述的代码之后，就可以开始写迭代器了。
3-1.迭代器类
将迭代器单独封装成一个类，迭代器也需要设置成模板：
template<class T>
class Iterator {
public:Node<T>* _it = nullptr;
};其中的 _it 就是迭代器实际指向的节点。
迭代器需要得到后面一个值，就需要进行++操作，这需要4个大步骤，在代码中体现：
Iterator<T> operator++(int) // 后置++
{Node<T>* prev_it = _it;++(*this);return Iterator<T>(prev_it);
}Iterator<T>& operator++() // 前置++
{Node<T>* prev_it = _it;// 1.先看：当前迭代器指向的节点有右孩子，就找右子树的最左节点if (_it->_right){Node<T>* maxLeft = _it->_right;while (maxLeft->_left)maxLeft = maxLeft->_left;_it = maxLeft;}// 2.再看：当前迭代器是左孩子，则迭代器指向父亲else if (_it->_parent->_left == _it){// 如果当前节点是根节点，指向nullptr作为end()// 因为根节点是中序遍历的最后一个节点if (_it->_parent->_parent == nullptr) {_it = nullptr;return *this;}_it = _it->_parent;}// 3.最后：当前迭代器是右孩子，迭代器指向父亲，直到迭代器指向左孩子(或者根节点)，然后再次指向父亲结束else{while (_it->_parent->_right == _it) {_it = _it->_parent;}// 若当前节点是根节点if (_it->_parent->_parent == nullptr){_it = nullptr;return *this;}_it = _it->_parent;}return *this;
}// --的操作与++相反，不再演示 //
然后还需要重载其他函数：
Iterator(Node<T>* it = nullptr)
{_it = it;
}
bool operator!=(const Iterator<T>& t)
{return _it != t._it;
}Node<T>* operator->()
{return _it;
}Node<T>& operator*()
{return *_it;
}其中operator*是迭代器必要的，因为范围for：for(auto& it:bst)中的 it 就是bst的迭代器解引用而来。
3-2.搜索树类
搜索树类中，声明并重定义迭代器类：
template<class T>
class SearchBinaryTree
{
public:typedef Iterator<T> iterator;// .....省略.....
};规定迭代器走到空为结束，又因为左<根<右，所以中序遍历才能得到升序，故规定搜索树的最左节点为起始。
在搜索树类中添加以下两个函数：
// 中序遍历:左->根->右
iterator begin() // 返回最左节点
{Node<T>* maxLeft = _root;while (maxLeft->_left)maxLeft = maxLeft->_left;return iterator(maxLeft);
}iterator end()
{return iterator(nullptr);
}3-3.测试迭代器
完成上述代码后就可以用范围for来测试迭代器了：
#include"SearchBinaryTree.h"
#include<iostream>int main() {std::vector<int> arr = {3,2,4,5,9,6,-1,-1,-2,-3,-4,-4,100,10000,1000002};SearchBinaryTree<int> BST(arr);for (auto& it : BST)std::cout << it._val << " ";return 0;
} 
第四节：完整代码
gitee：转调的C++仓库
第五节：下期预告
下一次是有序容器map和set的介绍。