树的基本定义

树是 $n(n\ge 1)$个结点的有限集合，在任意一棵非空树中：

1. 有且仅有一个称为根 (root) 的结点。
2. 当 n > 1 时，其余结点可以分为 K 个互不相交的有限集合 T1, T2, …, Tk，且每个集合本身又是一棵树，称为根的子树 (subtree)。

除根外，其余结点都有且仅一个前驱；都存在唯一一条从根到该结点的路径。

基本术语

• 结点层：根结点的层定义为 1，其它依此类推。
• 树的深度：树中最大的结点层。
• 结点的度：结点子树的个数。
• 树的度：树中最大的结点度。
• 叶子结点：也叫终端结点，是度为 0 的结点。
• 分枝结点：度不为 0 的结点。
• 有序树：子树有序的树，如家族树。
• 无序树：不考虑子树的顺序。
• 森林：互不相交的树集合。

一棵树去掉根，其子树构成一个森林；一个森林增加一个根结点成为树。

链接到

• 上一个知识点：无（本章第一个知识点）
• 下一个知识点：6.2 树的存储结构