无向树

无向树、树叶、分支点、平凡树（只有一个顶点）

无向树的判定充要条件：

• 图连通，无回路
• 任意两点之间有唯一通路
• 图连通，任意边都是桥
• 图无回路，且任意不相邻顶点间加一条新边，得到唯一回路
• 图无回路，且 $m = n - 1$
• 图连通，且 $m = n - 1$

根树

有向树、根树、叶子、内部顶点

父亲、儿子、兄弟、祖先、后代、子树、顶点层数、树高

$m$ 元树：每个点出度不大于 $m$

平衡 $m$ 元树：叶子高度最多差 $1$ 的 $m$ 元树

满 $m$ 元树：每个内部顶点出度为 $m$

完全 $m$ 元树：每个叶子的层数等于树高的满 $m$ 元树

有序根树：儿子节点按顺序排列

点数为 $n$ 的满 $m$ 元树：$L = (m - 1) I + 1$

高度为 $h$ 的完全 $m$ 叉树：$m^h$ 个叶子，$\displaystyle \frac{m^{h + 1} - 1}{m - 1}$ 个顶点。

有 $l$ 片叶子的 $m$ 元树的树高 $\displaystyle h \ge \lceil \log_m l \rceil$（可在满 $m$ 元树取等）

树的遍历

先广遍历、先深遍历

先深遍历：前序遍历、中序遍历、后序遍历

表达式：前序表示、中序遍历、后序遍历