树的基本概念

树的定义

树是 $n(n \ge 0)$ 个结点的有限集合。

  • $n=0$ 时为空树。
  • 非空树有且仅有一个根结点。
  • 当 $n>1$ 时，其余结点可分为 $m(m>0)$ 个互不相交的有限集合 $T_1,T_2,\ldots,T_m$，每个集合本身又是一棵树，称为根的子树。

树是递归定义的数据结构。

非空树的基本特性

  • 有且仅有一个根结点。
  • 没有后继的结点称为叶子结点或终端结点。
  • 有后继的结点称为分支结点或非终端结点。
  • 除根结点外，任何结点都有且仅有一个前驱。
  • 每个结点可以有 0 个或多个后继。

概念表

概念 含义
祖先结点 从根到该结点路径上的所有上级结点
子孙结点 以某结点为根的子树中的所有下级结点
双亲结点 某结点的直接前驱
孩子结点 某结点的直接后继
兄弟结点 有同一个双亲的结点
堂兄弟结点 双亲在同一层的结点
路径 从一个祖先到一个子孙经过的结点序列
路径长度 路径上经过的边数

树的路径默认只能从上往下讨论；普通树中不把从子孙回到祖先看作树的路径。

结点和树的属性

  • 结点的层次或深度：从根开始自上向下计数，通常根为第 1 层。
  • 结点的高度：从叶子开始自下向上计数。
  • 树的高度或深度：树中结点的最大层数。
  • 结点的度：该结点的孩子个数。
  • 树的度：树中各结点度的最大值。
  • 叶子结点的度为 0。
  • 非叶子结点的度大于 0。

更多详见tree-properties

有序树、无序树和森林

  • 有序树：树中结点的各子树从左到右有次序，不能互换。
  • 无序树：各子树无次序，可以互换。
  • 森林：$m(m \ge 0)$ 棵互不相交的树的集合，$m=0$ 时为空森林。

森林和树可以相互转换，见tree-forest-and-binary-tree-conversion。

树形逻辑结构的应用

树适合表示层次关系，例如文件目录、组织结构、家谱、表达式分解等。其核心特点是：除根外每个结点只有一个直接前驱，但可以有多个直接后继。