树和二叉树
树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并且具有层次关系的结构。
树：是n(n>=0)个结点的有限集，满足：
结点 ：有一个数据元素及若干指向其它结点的分支所组成。
度 ： 结点的度 ：所拥有的子树的数目； 树的度 ：树中所有结点的度的最大值。
叶子（终端结点） ：度为 0 的结点。
非终端结点 ：度不会 0 的结点。
孩子（子结点） ：结点的子树的根称为该结点的孩子。
双亲（父结点） ：一个结点称为该结点所有子树根的双亲。
祖先 ：结点祖先指根到此节点的一条路径上的所有结点。
子孙 ：从某节点到叶节点的分支上的所有结点称为该结点的子孙。
兄弟 ：同一双亲的孩子之间互称兄弟。（父结点相同的点）
结点的层次 ：从根开始算起，根的层次为1，其余结点的层次为双亲的层次加1。
堂兄弟 ：其双亲在同一层的结点。
树的深度（高度） ：一个树中所有结点层次数的最大值。
有序树 ：若树中各结点的子树从左到右是有次序的，不能互换，称为有序树。
无序树 ：若树中各结点的子树是无次序的，可以互换，称为无序树。
森林 ：是 m(m>=0) 棵树的集合。
二叉树是 n(n>=0) 各结点的有限集合，它或为空（n=0），或是由一个 根 及 两棵 互不相交的 左子树 和 右子树 组成，其左子树和右子树也是二叉树。
二叉树的 特点 ：
二叉树和树的比较：
完全二叉树 ：深度为 k 的二叉树中，k-1 层结点数是满的 ，k 层结点是左连续的（即结点编号是连续的）。
满二叉树 ：深度为 k(k>=1) 且有 个结点的二叉树。满二叉树是完全二叉树的特例。
在二叉树的第 i(i>=1) 上至多有 个结点；
深度为 k(k>=1) 的二叉树至多有 个结点；
对任何一棵二叉树，如果其叶结点数为 ，度为2的结点数为 ，有： ；
含有 n 个结点的 完全二叉树 的深度为 ；
如果将一棵有 n 个结点的 完全二叉树 按层编号（从上到下，从左到右进行编号），则对任一编号为 i(1 <= i <= n) 的结点 A 有：
它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，可用编号的方法。
二叉树的顺序存储结构 -- 即对二叉树按完全二叉树进行编号，然后用一维数组存储，其中 编号为i 的结点存储在数组中 下标为i 的分量中。
该方法称为 “ 以编号为地址 ” 策略。
从树根起，从上层至下层，每层从左至右的给所有结点编号， 缺点 是：
对于 完全二叉树 采用此方法，则：
对于 一般二叉树 采用此方法，首先需要用某种方法将其转换成完全二叉树，为此可增设若干个 虚拟结点 ，则：
遍历二叉树 ：是指按 某种次序访问 二叉树上的所有结点，使每个结点被 访问一次 且仅被访问一次。
先序遍历，DLR ：根 -> 左子树 -> 右子树
中序遍历，LDR ：左子树 -> 根 -> 右子树
后序遍历，LRD ：左子树 -> 右子树 -> 根
二叉树的层次遍历 ：从二叉树的 根结点 的这一层开始， 逐层向下 遍历，在每一层上按 从左到右 的顺序对结点逐个访问。
以一组连续空间存储树的结点，即一个一个数组构成，数组每个分量包含两个域：
双亲链表的类型定义，如下：
孩子链表 ：树中每个结点的孩子串成一单链表。
n 个结点 - n 个孩子链表
表头数组 ：n 个头指针用顺序表存储，数组元素存储：
孩子链表表示法的类型定义，如下：
在 孩子链表表示法 的基础上，在用一维数组顺序存储树中的各结点，数组元素存储：
双亲孩子表示法的类型定义，如下：
