二叉树搜索树
每个节点最多含有两个子树的树称为二叉树；二叉树搜索树对于任意一个节点均满足：
- 所有位于左子树的节点值均比该节点值小
- 所有位于右子树的节点值均大于等于该节点值
- 所有左子树和右子树也必须是BST
二叉树搜索树的查找比较简单，最左边的叶节点就是最小值，最右边的叶节点就是最大值，主要讲下遍历与删除。
遍历
有三种遍历二叉树的方法：前序（preorder）、中序（inorder）、后序（postorder）
-
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后在打印它的左子树，最后打印它的右子树。
前序遍历
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后打印它自己，最后打印它的右子树。
这个会使所有节点按关键字值升序被访问到。
中序遍历
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后打印它的右子树，最后打印它自己。
后序遍历
删除节点
删除节点是二叉树常用的一般操作中最复杂的，需要考虑三种情况：
- 1.该节点是叶节点
- 2.该节点有一个子节点
- 3.该节点有两个子节点
第一种与第二种比较简单，第三种比较复杂。
删除没有子节点的节点，只需要改变该节点的父节点的对应子字段的值，由指向该节点改为null就可以。
删除有一个子节点的节点，只要把该节点的子节点连接到该节点的父节点上就可以。
删除有两个子节点的节点，对于二叉搜索树，对每一个节点来说，比该节点的关键字值次高的节点是它的中序后继，可以简称为该节点的后继。那么该节点的后继不会有左子节点，最多有个右子节点。
优点
二叉树搜索树相比于其他数据结构的优势在于查找、插入的时间复杂度较低
缺点
如果树中插入的随机数据，则执行效果很好。但是，如果插入的是有序的数据或者逆序的数据，速度就会变得特别慢。因为当插入的数值有序时，二叉树就是非平衡树。而对于非平衡树，它的快速查找（插入、删除）指定数据项的能力就丧失了。为了解决这个问题，就有了红-黑树。
