树（tree）是包含n（n>0）个节点的有限集合 
每个元素称为节点（node）
有一个特定的节点被称为根节点或树根（root）
除根节点之外的其余数据元素被分为m（m≥0）个互不相交的集合 T1 T2 ... Tm-1
其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）


操作系统 红黑树
数据库 了B+树
编译器 语法树
内存管理 堆
信息论中的哈夫曼编码
Java TreeMap TreeSet  红黑树  



二叉树 
满二叉树 完全二叉树
二叉查找树 BST 
平衡二叉树 AVL树
堆 一颗完全二叉树


二叉树 
每个结点至多只有二棵子树
左右子树

第i层至多有2^(i-1)个结点（i从1开始）
深度为k的二叉树至多有2^(k)-1)个结点
对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
具有n个结点的完全二叉树的深度为log(n+1)



满二叉树 完全二叉树

满二叉树
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点

完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数
第h层所有的结点都连续集中在最左边

满二叉树是完全二叉树的一个特例


二叉查找树

二叉查找树，又称二叉排序树或 二叉搜索树
Binary Sort Tree  BST

若左子树不空，则左子树上所有结点的值均小于其根结点的值
若右子树不空，则右子树上所有结点的值均大于或等于其根结点的值
左、右子树也分别为二叉排序树
没有键值相等的节点

中序遍历，即可得到有序的数列



平衡二叉树

平衡二叉树又称为AVL树
它是一棵空树或左右子树的高度差不超过1
解决二叉查找树不平衡导致查找效率退化为线性的问题
由 BST 的 Node 加上  height 节点高度属性 ,用于判断树是否平衡
维护树的平衡关键就在于旋转


堆
堆是一颗完全二叉树
大根堆  父节点大于等于子节点
小根堆  父节点小于等于子节点

完全二叉树 ， 从上到下，从左到右 编号
通过一个节点在数组中的索引 计算 其父节点及左右孩子节点的索引

堆的用途
堆排序，优先队列
由于调整代价较小，适合实时排序与变更