树

树是 $n$（$n \ge 0$）个结点的有限集合。当 $n = 0$ 时称为空树。

特点

• 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱
• 树中所有结点可以有零个或多个后继

基本术语

• 根结点：非空树中无前驱结点的结点
• 结点的度：结点拥有的子树数
• 树的度：树内各结点的度的最大值
• 叶子（终端结点）：度 = 0 的结点
• 分支结点（非终端结点）：度 ≠ 0 的结点
• 内部结点：根结点以外的分支结点
• 孩子 / 双亲：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲
• 兄弟结点：有共同双亲的结点
• 堂兄弟：双亲在同一层的结点
• 结点的祖先：从根到该结点所经分支上的所有结点
• 结点的子孙：以某结点为根的子树中的任一结点
• 树的深度：树中结点的最大层次
• 有序树 / 无序树：结点的各子树从左至右是否有次序
• 森林：$m$（$m \ge 0$）棵互不相交的树的集合

性质

• 树中的结点数等于所有结点的度数之和 + 1
• 度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点（$i \ge 1$）
• 高度为 $h$ 的 $m$ 叉树至多有 $\frac{m^h-1}{m-1}$ 个结点
• 具有 $n$ 个结点的 $m$ 叉树的最小高度为 $\lceil \log_m(n(m-1)+1) \rceil$

存储结构

树的存储结构有双亲表示法、孩子表示法、孩子兄弟表示法三种。

树、森林与二叉树可以相互转换。