7、二叉搜索树

二叉搜索树：BST，binary search tree，二叉查找树、二叉排序树
二叉搜索树其实就是普通的二叉树上加了一些限制
二叉树对于结点是没有任何的限制，但是在二叉搜索树中在插入子节点的时候有一些特殊的要求：
1、非空左子树的所有键值都小于其根节点的键值
2、非空右子树的所有键值都大于其根节点的键值
3、左右子树本身也都是二叉搜索树
二叉搜索树的特点：相对较小的值总是保存在左子节点上，相对较大的值总是保存在右子节点上
二叉搜索树的遍历
二叉搜索树的遍历指：不重复的访问二叉树中所有的结点，
先序遍历，中序遍历，后序遍历（层次遍历）
1、先序遍历
    （1）访问根节点
  （2）先序遍历其左子树
  （3）先序遍历其右子树
2、中序遍历
    （1）先递归遍历其左子树
  （2）从最后一个左子树开始存入数组，然后回溯遍历双亲结点，再是右子树，递归循环。
3、后续遍历
    （1）后续遍历其左子树
  （2）后续遍历器右子树
  （3）访问根节点
删除：三种情况
    （1）没有子树
  （2）有且只有一棵子树
  （3）有两棵子树
二叉树的优点：作为数据存储的结构有重要的意义，可以快速的找到给定的关键字的数据项，并且可以快速的插入和删除数据
二叉搜索树的缺点：具有局限性，同样的数据，可以对应不同的二叉搜索树
比较好的二叉搜索树的结构：左右分布均匀，但是我们插入连续的数据时，会导致数据分布不均匀，我们就把这个分布不均匀的树称为非平衡树

二叉树的缺点

如果根节点是4，那么正常存储
如果根节点是1，会退化成链表