数据结构——树
树是由N个结点（或元素）组成的有限集合。
树的逻辑表示方法有：树形表示法、文氏图表示法、凹入表示法、括号表示法
结点的度：结点子树的个数
数的度：所有结点的度中的最大值，通常把度为M的树称为M次树。
分支结点：度不为零的结点
叶子结点：度为零的结点
路径：一个结点到另外一个结点的可达序列
路径长度：路径上的结点数-1
结点层次：即结点深度，从根节点开始，根节点为第一层，以此类推，
树的高度：即树的深度，树中结点的最大层次
有序树：按照一定的次序从左到右排列的，且相对次序是不能随意变换的
无序树：没有规律的
森林：N个互不相交树的集合，把含有多个子树的根节点删掉就变成了森林，反之个M（>1)棵独立的树加上一个根节点，森林就变成了一棵树。
树的性质：
| 树中的结点树等于所有结点的度数之和+1 |
| 度为M的树中第i层最多有Mi-—1个结点（i>=1） |
| 高度为h的m次树最多有mk-1/ m-1个结点 |
| 具有n个结点的m次树的最小高度为logm(n(m-1)+1),最大高度为n-m+1 |
树的遍历：①先根遍历：根左右②后根遍历：左右根③层次遍历从根结点开始，按从上到下，从左到右的次序
二叉树：有限的结点集合、这个集合或者为空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
度为2的树中至少有一个结点的度为2，二二叉树没有这种要求
度为2的树不区分左、右子树，二叉树严格区分
满二叉树：①所有分支结点都有左右孩子结点②所有叶子结点都集中在二叉树的最下一层。一棵高度为h的树有2h-1个结点
非空满二叉树特点：①叶子结点都在最下一层②只有度为0和度为2的结点
完全二叉树：①最多只有最下面两层的结点度数可以小于2，②最下面一层的叶子结点都依次排列在最左边的位置上
非空完全二叉树特点：①叶子结点只可能在最下面两层出现②对于最大层次中的叶子结点，都依次排列在该层最左边的位置上③如果有度为1的结点只能有一个，且这个几点只有左孩子没有有孩子④按照层序编号时，一旦出现编号为i 的结点是叶子结点或者只有左孩子，则编号大于i的结点均为叶子结点⑤当结点总数为奇数时,度为1的结点有0个，结点总数为偶数时。度为1的结点有1个。
二叉树的性质：①非空二叉树的叶子结点数等于双分支结点数+1（度为0的结点数=度为2的结点数+1）②非空二叉树的第i层最多有2i-1个结点③高度为h的二叉树最多有2h-1个结点④具有结点的完全二叉树高度为log2（n+1）或者log2n+1⑤完全二叉树中层次编号为i的结点有一下性质：①若2i<=n，则编号为i的结点为分支结点，否则为叶子结点，②若n为奇数，则每个分子结点都有左右孩子，若n为偶数，则最大的分支结点只有左孩子，③若编号为i的结点有左孩子则编号为2i，有右孩子，则编号为：2i+1④除根结点外，如果一个结点编号为i ,则他的双亲结点的编号为i/2;
树转化为二叉树：①树中相邻兄弟之间加一条连线②对树中的每个结点只保留它和长子之间的连线，删除和其他孩子之间的连线，③以根结点为轴心，旋转45°
森林转换为二叉树：①将森林中的每棵树转换为二叉树②第一棵不动，后面依次称为右孩子
二叉树转换为树：①若某结点是其双亲的左孩子，则把该结点的右孩子，右孩子的右孩子等都与该结点的双亲结点连起来②删除原来的连线，③逆时针旋转45°
二叉树还原为森林：①抹掉所有的“双亲-右孩子”关系，分为若干个二叉树，②分别将这些二叉树还原为树