树的基本性质

1. 节点与边的关系

• 节点（Node）：树的基本单位，可以有零个或多个子节点。
• 边（Edge）：连接两个节点的线，表示节点之间的关系。
• 根节点（Root Node）：树的顶端节点，所有其他节点都从它开始扩展。根节点没有父节点。
• 叶子节点（Leaf Node）：没有子节点的节点，位于树的底部。
• 内部节点（Internal Node）：有子节点的节点，但不是叶子节点。
• 树的边数（Edges Count）：树中节点数为 (N)，则树中边数为 (N-1)。

2. 度数（Degree）

• 度数（Degree of a Node）：一个节点连接到其他节点的边的数量。
• 树的度数（Degree of Tree）：树中所有节点的最大度数。

3. 层次与高度

• 层次（Level/Depth）：节点的层次是从根节点到该节点的边的数量。根节点的层次为0，直接连接到根节点的子节点的层次为1，依此类推。
• 树的高度（Height of Tree）：从根节点到最远的叶子节点的最长路径上的边数，等同于树中最大层次值。

4. 树的种类

• 二叉树（Binary Tree）：每个节点最多有两个子节点，通常称为左子节点和右子节点。
• 满二叉树（Full Binary Tree）：每个节点要么没有子节点，要么有两个子节点。
• 完全二叉树（Complete Binary Tree）：除了最后一层，其他层次都被节点填满，且最后一层的所有节点尽可能靠左。
• 平衡二叉树（Balanced Binary Tree）：左右子树的高度差最多为1。
• 二叉搜索树（Binary Search Tree, BST）：每个节点的左子树包含的值小于该节点的值，右子树包含的值大于该节点的值。
• N叉树（N-ary Tree）：每个节点最多有N个子节点。

5. 遍历（Traversal）

• 前序遍历（Pre-order Traversal）：先访问根节点，再访问左子树，然后访问右子树。
• 中序遍历（In-order Traversal）：先访问左子树，再访问根节点，然后访问右子树。
• 后序遍历（Post-order Traversal）：先访问左子树，再访问右子树，然后访问根节点。
• 层次遍历（Level-order Traversal）：按层次从上到下、从左到右逐层访问节点。

6. 树的性质

• 每棵非空树有且仅有一个根节点。
• 每个节点都有唯一的路径可以到达根节点。
• 树的节点数等于内部节点数加上叶子节点数。
• 一个N个节点的二叉树中，叶子节点数为 (L)，度数为2的内部节点数为 (N_2)，则有 (L = N_2 + 1)。
• 树的高度为 (h)，则树的节点总数最大为 (2^{h+1}-1)，最小为 (h+1)。

7. 树的应用

• 文件系统的目录结构
• HTML/XML文档对象模型
• 操作系统的进程调度
• 数据库索引（如B树和B+树）
• 路由算法