一、树的定义和基本术语

1. 树的基本概念

树是 n（n≥0） 个结点的有限集合：

• n=0 时为空树（特殊情况）；
• 非空树中：有且仅有一个根结点，其余结点可分为 m（m>0） 个互不相交的有限集合，每个集合本身也是树（称为根的子树）。

2. 结点与树的属性

• 结点的层次（深度）：从上往下数；
• 结点的高度：从下往上数；
• 树的高度（深度）：树的总层数；
• 结点的度：结点拥有的子树（孩子）数量。

3. 有序树 vs 无序树

• 有序树：子树从左至右有次序，不可互换；
• 无序树：子树无次序，可互换。

4. 树 vs 森林

• 森林是 m（m≥0） 棵互不相交的树的集合；
• 树和森林可相互转化（去掉树的根结点可得森林，森林添加共同根结点可得树）。