罗列术语

祖先 – 子孙， 双亲 – 孩子， 兄弟（同一个双亲） – 堂兄弟（同一层）。
树的度 = max{结点的度}，分支结点 – 叶结点，层次，高度（自底向上）= 深度（自顶向下）。
有序树（子树间的相对位置不可变）- 无序树
路径（结点ai 到 ak所经过的序列 – 包括ai,ak）, 路径长度（ai到ak边的个数）
森林 （n（n>=0）个树组成）

树性质（2个）：

• 结点数 = 边数 + 1 （根结点没有双亲）
• 具有 n 个结点的 m 叉树的最小高度 h = ⌈logm (n(m-1)+1)⌉ = ⌊logm (n(m-1))⌋ + 1

阿Q：还有一些最多结点就不写了，写了也不看。

二叉树

阿Q注：二叉树不是树的特殊情况，也不是度为2的有序树。（因为二叉树的左右位置是一直都存在的，不会因为没有子树而抛弃。而树的左右是子树间的相对位置，没有子树就没有对照了哦~） 但是可以说二叉树是有序树（左右严格区分）。

二叉树性质（除树性质外 1个）：

• n0(度为0的结点) = n2(度为2的结点) + 1 （由结点数 = 边数 + 1推的）

特殊二叉树

满二叉树

每一层都塞满了，那么孩子和双亲结点编号关系如下：

对于编号为 i 的结点（i>1）， 其双亲结点编号为 ⌊i/2⌋；

若有左孩子，则编号为 2i，若有右孩子，编号为 2i + 1。

完全二叉树

与满二叉树类似，只是最后一层没填满，但是仍然严格按照从左到右有结点。（编号连续）

n 个结点的二叉树特点：

• i <= ⌊n / 2⌋，则结点 i 为分支结点，否则为叶结点。

• n 为 奇数，每个分支结点都有俩孩子，n 为偶数，编号最大的分支结点有左孩子，无右孩子。

• 完全二叉树编号关系（和满二叉树是类似的）：

阿Q注：此外还有二叉排序树（关键字：左 < 根 < 右）、平衡二叉树（左右树深度差不超过1）
（统考不涉及，但有时间去看看）

两道练习：