（一） 树

层次 ： 根为第一层 ， 最大层为树的高度 ， 深度为根到该节点的路径长度 ； 高度为叶节点到该节点最大路径

二叉树性质：

1 ，二叉树第 i 层上的结点数目最多为 2i-1(i ≥ 1) 。

2 ，深度为 k 的二叉树至多有 2^k-1 个结点 (k ≥ 1)

3 ， 在任意 - 棵二叉树中 ， 若终端结点的个数为 n0 ， 度为 2 的结点数为 n2 ， 则 no=n2 1

4 ，具有 n 个结点的完全二叉树的深度为： log2[n]( 向下） 1 或 log2[n 1]( 向上）

二叉树存储形式：

1 ，顺序存储：第 i 个结点的孩子是 2i,2i 1 ( 完全二叉树适用，如果该树不是完全二叉 树，需要添加空节点构成完全二叉树）

2 ，二叉链表结构：左右指针，中间数据 |left|data|right| 二叉树遍历： 遍历是树进行其他运算的基础 ， 前 中 ， 中 后 ， 层次 中 （ 因为前后可以推出根结点 ， 而中可以推左右） 使用递归思想来推树的结构能够快些 如：前 中 前： GDAFEMHZ 中： ADEFGHMZ 步骤：根据前知道 root 是 G ，根据中知道左子树是 ADEF, 右子树是 HMZ 分析 leftTree, 由前知道 root 是 D ， so leftTree is:A,and rightTree is :EF