##
- 0 树
- 1 二叉树
- 2 二叉查找树
- 3 平衡二叉树
0.树
树有多个节点(node)，用以储存元素。某些节点之间存在一定的关系，用连线表示，连线称为边(edge)。边的上端节点称为父节点，下端称为子节点。树像是一个不断分叉的树根。
树的深度和高度的定义:
基数为1时 树的深度=树的高度=最大层数
1.二叉树
二叉树是数据结构中重要的数据结构，也是树家族最为基础的结构。
二叉树的定义
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点).
二叉树的子树有左右之分，次序不能颠倒。
二叉树的第i层至多有2^(i-1)个结点.
深度为k的二叉树至多有2^k-1个结点.
对任何一棵二叉树T，如果其终端结点数为N，度为2的结点数为M，则N=M+1。1.1 满二叉树
就是满树呗。
1.2完全二叉树
高度为h的完全二叉树。前h-1层为满树，最后一层元素全部集中在左侧。
2.二叉查找树
定义
又称二叉排序树(Binary Sort Tree)或二叉搜索树。二叉排序树是一颗空树或者是具有以下性质的树。
- 若左子树不为空 则左子树上的所有值均小于根节点的值。
- 若右子树不为空 则右子树所有值大于根节点的值。
- 以上性质完全适用于左右子树(左右子树均为二叉查找树)。
- 没有键值相等的节点。
3.平衡二叉树
平衡二叉树的定义
Balance Binary Tree又称为AVL树。它具有以下性质：
- 1.它是一颗空树或者它的左右两个子树的高度差绝对值不超过1。
- 2.它的左右子树均是一颗平衡二叉树。
在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。