二、知识总结

✨ 核心思想

树是一种非线性数据结构，广泛应用于计算机科学中，用于表示具有层次关系的数据。树由节点（nodes）和连接这些节点的边（edges）组成。树的一个重要特性是它不包含任何循环或回路（cycle-free），这使得树结构适用于表示具有明确层级或顺序的数据结构。

✨ 树的基本组成和术语

树结构中常见的术语包括：

• 节点（Node）：树的基本部分，可以含有指向其他节点的链接。
• 根节点（Root）：树结构中的顶端节点。每棵树只有一个根节点。
• 父节点（Parent）：除根节点外的任何节点都有一个父节点。
• 子节点（Child）：具有从一个节点引出的链接指向的节点。
• 叶节点（Leaf）/终端节点（Terminal node）：没有子节点的节点。
• 兄弟（Siblings）：共享同一父节点的节点。
• 边（Edge）：连接两个节点的线。
• 路径（Path）：从一个节点到另一个节点的边的序列。
• 深度（Depth）：从根节点到指定节点的边的数量。
• 高度（Height）：从指定节点到最深叶节点的最长路径的边的数量。树的高度是其根节点的高度。

✨ 树的类型

树有很多种类，每种都有其特定的用途和特性：

• 二叉树（Binary Tree）：每个节点最多有两个子节点（通常称为左子节点和右子节点）。
• 二叉搜索树（Binary Search Tree, BST）：一种特殊的二叉树，其中每个节点都符合以下条件：左子树中的所有元素都小于节点的值，右子树中的所有元素都大于节点的值。
• 平衡二叉树（Balanced Binary Tree）：任何两个叶子节点之间的高度差最多为一，如 AVL 树和红黑树。
• 完全二叉树（Complete Binary Tree）：除了最后一层外，每一层都被完全填满，且所有节点都尽可能地向左填充。
• 满二叉树（Full Binary Tree）：每个节点都有 0 个或 2 个子节点。
• 多叉树/多路搜索树（M-ary Tree）：节点可以有多于两个的子节点，如 B树和 B+ 树，这在数据库索引和文件系统中非常常见。

✨ 树的表示

在计算机中，树可以通过多种方式表示：

• 嵌套列表：特别是在具有解释性质的语言如 Python 中，树可以通过嵌套列表或元组的方式来表示。
• 节点和指针：在像 C++ 或 Java 这样的编程语言中，通常通过创建一个节点类，其中包含数据和指向其子节点的指针来实现。
• 数组：对于完全二叉树或堆，可以使用数组来表示。根节点存储在索引 1，对于任何位于索引 i 的节点，其左子节点在索引 2i，右子节点在索引 2i + 1。

树结构的多样性和灵活性使得它成为解决许多计算问题的理想选择，包括组织数据、管理信息层次结构、编程环境中的语法表示，以及许多类型的算法，如搜索和排序算法。

✨ 执行示例

下面通过一个具体的例子，展示如何用数组表示一棵完全二叉树，并计算各节点的父子关系。

示例： 将数据 [1, 2, 3, 4, 5, 6, 7] 存储为一棵完全二叉树。

使用数组下标从 1 开始存储（索引 0 不使用）：

数组：[_, 1, 2, 3, 4, 5, 6, 7]
索引：  0  1  2  3  4  5  6  7

对应的树结构：

1 (索引1)
        / \
       2   3 (索引2, 3)
      / \ / \
     4  5 6  7 (索引4, 5, 6, 7)

验证父子关系：

• 节点 2（索引 2）：父节点 = 2/2 = 1，左子 = 22 = 4，右子 = 22+1 = 5
• 节点 3（索引 3）：父节点 = 3/2 = 1，左子 = 23 = 6，右子 = 23+1 = 7
• 节点 5（索引 5）：父节点 = 5/2 = 2，无子节点（2*5 = 10 > 7 越界）
• 根节点 1（索引 1）：无父节点，左子 = 2，右子 = 3

用指针（链表）表示同一棵树：

每个节点包含 value、left、right 三个域：

• 根节点 Node(1)：left -> Node(2)，right -> Node(3)
• Node(2)：left -> Node(4)，right -> Node(5)
• Node(3)：left -> Node(6)，right -> Node(7)
• Node(4), Node(5), Node(6), Node(7) 的 left 和 right 都为 nullptr（叶子节点）

✨ 解题步骤详解

以"找树根和孩子"为例，介绍如何根据输入数据建立树结构：

问题： 给定 n 个节点和若干条边（父子关系），找到根节点并输出指定节点的子节点。

解题步骤：

1. 记录每个节点的父节点：对于每条边 (parent, child)，将 child 的父节点记录为 parent。
2. 找根节点：遍历所有节点，找到没有父节点的那个节点就是根。
3. 建立子节点关系：可以用邻接表或数组存储每个节点的子节点列表。
4. 查询输出：根据题目要求，输出指定节点的所有子节点。

关键数据结构选择：

• 如果节点编号连续且较小，使用数组存储父子关系即可。
• 如果节点数量大或关系复杂，使用 vector 的邻接表更灵活。

✨ 常见错误

1. 混淆"深度"和"高度"的定义：深度是从根到该节点的边数（根的深度为 0），高度是从该节点到最深叶子的边数。树的高度等于根的高度。
2. 数组表示时索引从 0 还是从 1 开始不统一：从 1 开始时，父节点 = i/2，左子 = 2i，右子 = 2i+1；从 0 开始时，父节点 = (i-1)/2，左子 = 2i+1，右子 = 2i+2。两者不能混用。
3. 忘记处理空树的情况：当 n = 0 时，树为空，需要特判。
4. 多叉树只用二叉树结构存储：如果一个节点可能有多个子节点，不能只用 left/right 两个指针，需要用子节点数组或"左孩子右兄弟"表示法。