定义：
二叉查找树要么是一棵空树，要么是一棵具有如下性质的非空二叉树：
1.若左子树非空，则左子树上的所有结点的关键字值均小于根结点的关键字值。
2.若右子树非空，则右子树上的所有结点的关键字值均大于根结点的关键字值。
3.左、右子树本身也分别是一棵二叉查找树（二叉排序树）
支持的操作：
search(x,k)， //在以x为根的BST中查找关键值k是否存在
insert(x,k)， //在以x为根的BST中插入关键字为k的结点
remove(x,k)， //在以x为根的BST中删除关键字为k的结点。
三种情况：无子（直接删掉）、有1子（将子结点和父结点相连）、有2子（将node的值设置为它后继的值，删除node的后继）
max(x)， //返回以x为根的BST中最大的关键值
min(x)， //返回以x为根的BST中最小的关键值
successor(x) （返回x结点的后继元素，中序遍历x结点之后输出的元素） //2种情况：有右子（右子树的最小结点），无右子（向上找，第一个作为左儿子的父结点）
predecessor(x) （前驱元素，中序遍历x结点之前输出的元素） //和找后继对称
所有操作时间复杂度都是O(h)，h是树的高度
随机选择输入序列的元素插入BST，可得树高度期望是O(logn)，可知随机化是接近最好情况的，不是接近最坏情况
对BST中节点按从小到大顺序遍历是对树的中序遍历
递归算法时间复杂度O(n)，空间复杂度O(n)
用栈迭代算法时间复杂度O(n)，空间复杂度O(n)
非常牛逼的遍历方式
Morris Traversal ：O(1)空间复杂度，O(n)时间复杂度，中序遍历二叉树（不用栈，不递归遍历）
步骤：
1.若当前节点r无左子，输出当前节点，当前节点变为原当前节点的右子（r = r->right）
2.若当前节点有左子，在左子树内找到当前节点的中序前驱pre。
a) 若前驱节点pre的右子为null，将pre->right设为当前节点r，当前节点变为当前节点的左子（r=r->left）
b) 若前驱节点pre的右子为当前节点r，将pre->right还原为null，输出当前节点r，当前节点变为当前节点的右子（r = r->right ）
vector < int> inorderTraversal2 (TreeNode * root ){
//Morris traversal
TreeNode * curr = root,* pre ;
while ( curr != nullptr){
if ( curr ->left == nullptr ){
sortedVect .push_back ( curr-> val );
curr = curr-> right ;
}
else {
pre = curr-> left ;
while ( pre ->right != nullptr && pre-> right != curr) pre = pre-> right ;
if ( pre ->right == nullptr ){
pre ->right = curr ;
curr = curr-> left ;
}
else {
pre ->right = nullptr ;
sortedVect .push_back ( curr-> val );
curr = curr-> right ;
}
}
}
return sortedVect ;
}