本文共 959 字，大约阅读时间需要 3 分钟。

0x01 树

树（Tree）可以定义为一个包含n个结点的有限集合，其中n=0时表示一个空树。

• 根节点：任何非空树都有且仅有一个根节点。
• 结点之间关系：每个结点（除了根节点）都有且仅有一个前驱结点（父节点）。
• 边的数量：n个结点的树共有n-1条边，边是单向的，方向从父节点指向子节点。

有序树与无序树：

• 有序树（Ordered Trees）强调结点之间的顺序关系。例如，有序树的两个子树结构会因结点顺序的不同而不同。
• 无序树（Unordered Trees）则不关心结点的顺序，两个结构如果有相同的子树布局即可视为相同。

0x02 结点

一个结点（Node）具有多种属性：

• 祖先节点：在树中，某个结点的所有可能祖先包括其父节点、父父节点等，直到最高层的根节点。
• 子孙节点：一个结点的所有后代（包括自己）的集合称为其子孙节点。
• 双亲节点：对于非根结点，双亲节点是其直接的父节点和综上，如果有多个父节点，则需要区分。
• 孩子结点：树中某个结点直接连接到它的且在其下方的子节点构成的集合。
• 兄弟节点：同一父节点的其他子节点构成兄弟节点。
• 结点的层次：树的层次通常从0层（根节点）开始递增。
• 结点的高度和深度：
  • 高度：从叶子节点（层次最低的节点）向上依次计算的层数。
  • 深度：从根节点（层次最高的节点）向下依次计算的层数。

0x03 度

树中的度（Degree）用于描述结点的连接情况：

• 一个结点的度表示它的子节点数量。
• 树中最大的度即为树的度。
• 分支结点：度值大于0的结点。
• 叶子结点：度值为0的结点。

0x04 路径

路径（Path）描述的是树中两个结点之间的连接关系。因为树是有向的，只能从父节点向子节点移动，所以路径是从上到下的。例如，A到E的路径存在，而E到F的路径不存在。

0x05 森林

森林（Forest）是由多棵树组成的集合。如果一个树中存在多个子树，并且这些子树之间没有共享的根节点，那么这个集合就是一个森林。

0x06 性质

树的性质及相关结论：