数据结构
1. 树
n个结点构成的有限集合，对于任意一个非空树，具有以下性质：
·树中有一个称为根的特殊结点
·其余结点可分为m个互不相交的有限集合，其中每个集合也是一棵树，称为原来树的子树
·树没有回路，除了根结点，只有一个父结点
2. 二叉树
二叉树是每个结点最多有两个子树的树结构。
特殊的二叉树：平衡二叉树，每一个结点的左右子树的高度差不超过1。
二叉树的遍历：
树的遍历都是先左，再右，区别就是打印顺序不同，对该二叉树遍历结果如下：
·先序遍历
public void preOrder(TreeNode root) {
????if (root == null) //树为空的情况
??????return;
????System.out.print(root.getValue()); //先输出根
????preOrder(root.getLeft()); //再前序遍历左子树
????preOrder(root.getRight()); //再前序遍历右子树
??}遍历结果为：A->B->D->F->H->C->G
·中序遍历
public void inOrder(TreeNode root) {
????if (root == null) {
??????return;
????}
????inOrder(root.getLeft()); //先中序遍历左子树
????System.out.print(root.getValue());//再输出根
????inOrder(root.getRight()); //再中序遍历右子树
??}遍历结果为：D->B->H->F->A->C->G
后序遍历：
public void postOrder(TreeNode root) {
????if (root == null) {
??????return;
????}
????postOrder(root.getLeft()); //先后序遍历左子树
????postOrder(root.getRight()); //再后序遍历右子树
????System.out.print(root.getValue());//再输出根
??}遍历结果：D->H->F->B->G->C->A
3. 二叉搜索树
或者是一棵空树，或者是具有下列性质的二叉树
·若左子树不空，则左子树上所有结点的值均小于它的根结点的值
·若右子树不空，则右子树上所有结点的值均大于它的根结点的值
·左、右子树也分别为二叉排序树
插入操作：判断与根结点值是否相同，相同则返回已有元素，不同就判断大小，并迭代递归左右子树，直到找到相同元素或者子结点为null，把该元素插入子结点位置。
删除操作：在迭代找到要删除的点的位置之后，需要考虑三种情况
·要删除的结点没有子节点，也就是叶子结点，那就可以直接删除，如上图5、9号点
·要删除的结点只有一个子节点，就将其子结点换到要删除的结点的位置上，如要删除6号结点，就可以把6号删除，再把5号放到这个位置上
·要删除的结点有左右两个子节点，用另一结点代替被删除的结点，有两种方式，用左子树的最大值或右子树的最小值。如要删除上图7号结点，有两种方式，第一种可以用右子树最小值8来代替7；第二种是用左子树最大值6来替换7，再把5补回空缺的位置。
优点：结构上实现了二分查找，提高了查找效率，插入删除操作简单
缺点：由于每次插入都是在叶子结点处插入，如果插入顺序不合适，可能出现链式结构或者非常不平衡，使查找效率降低
4. 二叉平衡树（AVL树）
为了解决二叉查找树的不平衡问题，就有了二叉平衡树，二叉平衡树就是在二叉查找树的基础上，再要求左子树与右子树的高度差最大为1。
插入删除操作：与二叉搜索树一样，但是在插入删除之后，由于还需要保持平衡的性质，所以还需要有一步调整。
调整：不平衡的位置只有四种可能，LL、RR、LR和RL
调整方式有四种：LL旋转、RR旋转、LR旋转和RL旋转
·LL（左左）旋转
如上图的LL不平衡图，LL旋转就是将3号点上移一层，7号点下移一层，此时再检查，6号点不满足二叉树性质，就需要放到6号点的左子树上，调整完成。RR旋转也类似。
·LR（左右）旋转
如上图LR不平衡图，LR旋转就是先
LR旋转要分两步，首先对3、6号点进行RR调整，调整过程和RR旋转一样，再对上面6、7号点进行调整，调整过程和LL旋转一样。