树
定义
树是n(n≥0)个结点的有限集，它或为空树(n=0)，或为非空树
非空树T满足以下条件：
(1) 有且仅有一个称为根的结点；
(2)除根结点以外的其余结点可分为m(m>0)个互补相交的有限集T1,T2,…Tm,其中每一个集合本身又是一棵树，并且称为根的子树。
空树
一般的树
基本术语
根———即根结点(没有前驱)
叶子———即终端结点(没有后继)
森林———指m棵不相交的树的集合
有序树———结点各子树从左至右有序，不能互换
无序树———结点各子树可互换位置。
双亲———即上层的那个结点(直接前驱)
孩子———即下层结点的子树的根(直接后继)
兄弟———同一双亲下的同层结点(孩子之间互称为兄弟)
堂兄弟———即双亲位于同一层的结点(但并非同一双亲)
祖先———即从根到该结点所经分支的所有结点
子孙———即该结点下层子树种的任一结点
结点———即树的数据元素
结点的度———结点挂接的子树数
结点的层次———从根到该结点的层数(根结点算第一层)
终端结点———即度为0的结点，即叶子
分支结点———即度不为0的结点(也称为内部结点)
树的度———所有结点度中的最大值
树的深度———指所有结点中最大的层数(或高度)
二叉树
二叉树是一种特殊的树结构，普通树若不转化成二叉树，则运算很难实现
为什么要重点研究二叉树呢？
二叉树的结构最简单，规律性最强
所有的树都能转为唯一对应的二叉树，不失一般性。
定义：
每个节点至多有两个子树。
基本特点：
- 结点的度小于等于2
-
有序树(子树有序，不能颠倒)
二叉树的五种形态
二叉树的性质
性质1 ： 一棵非空二叉树的第i层上最多有2^i-1个结点(i≥1)。
性质2 ：若规定空树的深度为0，则深度为k的二叉树最多有(2^k)-1个结点
(k≥0)。
性质3： 具有n个结点的完全二叉树的深度k为log2n+1。
性质4 ：对于一棵非空二叉树，如果度为0的结点数目为n0，度为2的结点数目为n2，则有n0= n2+1。
性质5 ：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对所有结点从1开始编号，则对于序号为i的结点，有：
如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i=1，则该结点是根结点，无双亲结点。
如果2i≤n，则该结点的左孩子结点的序号为2i；若2i>n，则该结点无左孩子。
如果2i+1≤n，则该结点的右孩子结点的序号为2i+1；若2i+1>n，则该结点无右孩子。
满二叉树：一棵深度为k且有2k-1个结点的二叉树。（意思是树上挂满了结点）
完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应(意思是只有最后一层叶子不满，且全部集中在左边)
Unfinished, see the next