通用树

没有环的图称为无环图。 树是无环图或没有环的图。

树或通用树定义为非空的有限元素集合，称为顶点或节点，每个节点可以具有最小度为 1 和最大度为 n 的属性。 它可以划分为 n+1 个不相交的子集，使得第一个子集包含树的根，剩余的 n 个子集包含 n 个子树的元素。

有向树

有向树是无环有向图。 它有一个入度为 0 的节点，而所有其他节点的入度都为 1，如图所示

出度为 0 的节点称为外部节点或终端节点或叶节点。 出度大于或等于 1 的节点称为内部节点。

有序树

如果树的每一层都定义了排序，则这样的树称为有序树。

示例： 图中所示的树代表同一棵树，但具有不同的顺序。

树的性质

1. 树的每对顶点之间只有一条路径。
2. 如果图 G 中每对顶点之间只有一条路径，则 G 是一棵树。
3. 具有 n 个顶点的树 T 有 n-1 条边。
4. 一个图是一棵树当且仅当它是最小连通的。

有根树

如果一个有向树只有一个节点或顶点称为根，其入度为 0，而所有其他顶点的入度都为 1，则该树称为有根树。

注意：1. 没有节点的树是一棵有根树（空树）
          2. 一个没有子节点的单个节点是一棵有根树。

顶点的路径长度

有根树中顶点的路径长度定义为从根到该顶点的路径中的边数。

示例： 找出图中节点 b、f、l、q 的路径长度

解决方案： 节点 b 的路径长度为 1。
                节点 f 的路径长度为 2。
                节点 l 的路径长度为 3
                节点 q 的路径长度为 4。