树 (Tree)

树 (Tree)

概念：层级关系的数据结构，由节点和边组成

想象一下，一棵倒立的树。树根在最上面，树枝向下延伸，树枝上又分叉出更小的树枝，最后是叶子。 树 (Tree) 这种数据结构就类似于自然界中的树，它是一种表示 层级关系 的数据结构。 由 节点 (Node) 和 边 (Edge) 组成。

  • 节点 (Node)： 树的基本单元，代表数据集合中的一个元素。 节点可以有子节点，也可以没有子节点。
  • 边 (Edge)： 连接节点与节点之间的线，表示节点之间的父子关系。 在树结构中，边是有方向的，通常从父节点指向子节点。

树数据结构示意图

重要概念 (Key Concepts)

理解树结构需要掌握一些重要的概念：

1
2
3
4
5
     A
   /   \
  B     C
 / \   / \
D   E F   G

  1. 根节点 (Root Node)： 树的最顶端的节点，整棵树的起始节点。 一棵树只有一个根节点。 在倒立树的比喻中，根节点就是树根。 在示意图中，通常将根节点画在最上方。

  2. 父节点 (Parent Node)： 除了根节点外，每个节点都有且仅有一个父节点（可以理解为“直接上级”）。 指向该节点的节点称为其父节点。 例如，节点 B 和 C 的父节点是 A。 根节点没有父节点。

  3. 子节点 (Child Node)： 一个节点可以有零个或多个子节点（可以理解为“直接下级”）。 被该节点指向的节点称为其子节点。 例如，节点 A 的子节点是 B 和 C。

  4. 叶子节点 (Leaf Node)： 没有子节点的节点称为叶子节点，也叫终端节点。 它们是树结构“最末端”的节点。 例如，节点 D、E、F、G 都是叶子节点。

  5. 兄弟节点 (Sibling Node)： 拥有同一个父节点的节点互为兄弟节点。 例如，节点 B 和 C 是兄弟节点，节点 D 和 E 是兄弟节点。

  6. 祖先节点 (Ancestor Node)： 从根节点到某个节点路径上的所有节点都是该节点的祖先节点。 例如，节点 G 的祖先节点是 C 和 A。

  7. 子孙节点 (Descendant Node)： 某个节点的所有子树中的节点都是该节点的子孙节点。 例如，节点 B 的子孙节点是 D 和 E。

  8. 深度 (Depth)： 从根节点到某个节点的 唯一路径 的 边 的数量。 根节点的深度为 0。 例如，节点 D 的深度为 2 (A->B->D 有两条边)。

  9. 高度 (Height)： 从某个节点到它 最远叶子节点 的 边 的数量。 叶子节点的高度为 0。 例如，节点 B 的高度为 1 (最远叶子节点是 D 或 E，B->D 或 B->E 只有一条边)。 树的高度通常指根节点的高度。

  10. 层 (Level)： 节点的层数，根节点为第 0 层，根节点的子节点为第 1 层，以此类推。 层数与深度类似，但层数通常从 0 或 1 开始计数。 这里我们约定根节点为第 0 层。

  11. 度 (Degree)： 一个节点拥有的子节点的数量。 例如，节点 A 的度为 2，节点 D 的度为 0 (叶子节点度为 0)。

  12. 子树 (Subtree)： 以某个节点为根节点（包含该节点及其所有子孙节点）构成的树，称为原树的子树。 每个节点都可以看作是一棵子树的根节点。

二叉树 (Binary Tree)

概念：每个节点最多有两个子节点的树

二叉树 (Binary Tree) 是一种特殊的树结构，也是最常用和最重要的树类型之一。 “二叉” 的含义是，每个节点最多只能有两个子节点，分别称为 左子节点 (Left Child) 和 右子节点 (Right Child)。 当然，二叉树的节点也可以只有左子节点、只有右子节点，或者没有子节点（叶子节点）。

二叉树结构示意图

类型 (Types)

二叉树根据其节点的分布和形状，又可以细分为几种特殊类型：

  1. 满二叉树 (Full Binary Tree)

    除了叶子节点外，每个节点都有两个子节点。并且，所有的叶子节点都在同一层。

    满二叉树是一种非常“丰满”、“平衡”的二叉树。

  2. 完全二叉树 (Complete Binary Tree)

    对树的节点进行从上到下、从左到右的编号，如果编号与 满二叉树 对应位置的节点完全相同，则为完全二叉树。

    更直观的定义是：除了最后一层外，其他层的节点数都达到最大值，并且最后一层的叶子节点都连续地集中在最左边。

    完全二叉树可以看作是从满二叉树的最右下侧，逐个删除叶子节点 得到的。

    满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

区分满二叉树和完全二叉树的关键在于： 是否允许最后一层叶子节点不满，以及最后一层叶子节点的排列位置。满二叉树要求最后一层必须满，完全二叉树允许最后一层不满，但要求叶子节点尽可能靠左排列。

遍历方式 (Traversal Methods)

二叉树的遍历是指按照某种顺序访问二叉树中的所有节点，确保每个节点都被访问且仅访问一次。

常见的二叉树遍历方式有四种：

  1. 前序遍历 (Preorder Traversal)： 根 -> 左 -> 右

    **访问顺序：**先访问 根节点，然后 递归地前序遍历左子树，最后 递归地前序遍历右子树。

    特点： 先根后叶，优先访问树的深度方向。 可以用来复制树结构。

    口诀： 根左右

    前序遍历示例 (访问顺序: A -> B -> D -> E -> C -> F -> G):

    1
    2
    3
    4
    5
    6
    7
           A
         /   \
        B     C
       / \   / \
      D   E F   G

    前序遍历结果: A, B, D, E, C, F, G

  2. 中序遍历 (Inorder Traversal)： 左 -> 根 -> 右

    访问顺序： 先 递归地中序遍历左子树，然后访问 根节点，最后 递归地中序遍历右子树。

    特点： 对于二叉搜索树 (BST)，中序遍历的结果是 有序的。 可以用来对 BST 进行排序。

    口诀： 左根右

    中序遍历示例 (访问顺序: D -> B -> E -> A -> F -> C -> G):

    1
    2
    3
    4
    5
    6
    7
           A
         /   \
        B     C
       / \   / \
      D   E F   G
      
    中序遍历结果: D, B, E, A, F, C, G

  3. 后序遍历 (Postorder Traversal)： 左 -> 右 -> 根

    访问顺序： 先 递归地后序遍历左子树，然后 递归地后序遍历右子树，最后访问 根节点。

    特点： 先叶后根，可以用来计算树的高度、删除树节点等。

    口诀： 左右根

    后序遍历示例 (访问顺序: D -> E -> B -> F -> G -> C -> A):

    1
    2
    3
    4
    5
    6
    7
           A
         /   \
        B     C
       / \   / \
      D   E F   G
      
    后序遍历结果: D, E, B, F, G, C, A

  4. 层序遍历 (Level Order Traversal)： 逐层访问

    **访问顺序：**从根节点开始，一层一层 地从上到下、从左到右访问每个节点。 也称为 广度优先遍历 (BFS - Breadth-First Search)。

    **实现方式：**通常使用 队列 (Queue) 来辅助实现。 先将根节点入队，然后循环执行：出队一个节点，访问该节点，将其左右子节点（如果存在）依次入队。

    **特点：**按层级顺序访问，可以用来查找树的某些层级信息，或者解决一些最短路径问题（在某些树结构中）。

    层序遍历示例 (访问顺序: A -> B -> C -> D -> E -> F -> G):

    1
    2
    3
    4
    5
    6
    7
           A
         /   \
        B     C
       / \   / \
      D   E F   G
      
    层序遍历结果: A, B, C, D, E, F, G

二叉搜索树 (Binary Search Tree - BST)

概念：有序的二叉树，左子树所有节点值小于根节点，右子树所有节点值大于根节点

二叉搜索树 (Binary Search Tree, BST)，也叫二叉排序树。 它是一种特殊的二叉树，最重要的特点是 有序性。 这种有序性体现在以下两个关键性质上：

  1. 左子树性质： 任何节点的左子树中的所有节点的值，都小于该节点的值。
  2. 右子树性质： 任何节点的右子树中的所有节点的值，都大于该节点的值。

并且，二叉搜索树的 左右子树也必须分别是二叉搜索树。

这种递归的定义保证了整棵树的有序性。

二叉搜索树示意图，左子树小于根节点，右子树大于根节点

基本操作 (Operations)

二叉搜索树的有序性使得它在查找、插入、删除等操作上具有很高的效率，尤其是在平均情况下。

  1. 查找 (Search)： 利用 BST 的有序性，可以快速查找目标值。

    • 查找步骤：
      a. 从根节点开始。
      b. 如果目标值等于当前节点值，查找成功，返回当前节点。
      c. 如果目标值小于当前节点值，则在当前节点的 左子树 中递归查找。
      d. 如果目标值大于当前节点值，则在当前节点的 右子树 中递归查找。
      e. 如果子树为空（查找路径到达叶子节点的子节点，仍未找到），则查找失败，返回空。

    • 高效性： 每次比较都可以排除一半的搜索空间（左子树或右子树），因此平均时间复杂度为 O(log n)，类似于二分查找。最坏情况下（BST 退化成链表），时间复杂度为 O(n)。

  2. 插入 (Insert)： 将新节点插入到 BST 中，并保持 BST 的有序性。

    • 插入步骤：
      a. 从根节点开始，按照查找的步骤比较新节点值与当前节点值。
      b. 如果新节点值小于当前节点值，则向左子树方向移动。
      c. 如果新节点值大于当前节点值，则向右子树方向移动。
      d. 直到遇到空子树（即到达叶子节点），将新节点作为叶子节点的子节点插入（如果新节点值小于叶子节点值，作为左子节点插入，否则作为右子节点插入）。

    • 保持有序性： 插入过程始终遵循 BST 的性质，保证插入后仍然是一棵 BST。 平均时间复杂度为 O(log n)，最坏情况 O(n)。

  3. 删除 (Delete)： 从 BST 中删除一个节点，并保持 BST 的性质。 删除操作相对复杂，需要考虑多种情况：

    • 删除叶子节点： 直接删除即可，不影响 BST 结构。

    • 删除只有一个子节点的节点： 将该节点的父节点指向其子节点，相当于用子节点替代被删除节点的位置。

    • 删除有两个子节点的节点： 这是最复杂的情况。 通常有两种方法：
      a. 方法一 (前驱节点替代)： 在被删除节点的左子树中，找到值最大的节点（前驱节点），用前驱节点的值替换被删除节点的值，然后在左子树中递归删除前驱节点（前驱节点最多只有一个右子节点，删除相对简单）。
      b. 方法二 (后继节点替代)： 在被删除节点的右子树中，找到值最小的节点（后继节点），用后继节点的值替换被删除节点的值，然后在右子树中递归删除后继节点（后继节点最多只有一个左子节点，删除相对简单）。

    • 平衡性问题： 频繁的插入和删除操作可能导致 BST 失去平衡，树的深度增加，查找效率降低。 为了解决这个问题，需要使用 平衡二叉树。

  • 优势 (Advantages)：高效的查找操作

    二叉搜索树最主要的优势在于其 高效的查找性能。

    平均情况下，查找、插入、删除操作的时间复杂度都接近于 O(log n)，这使得 BST 在需要频繁进行查找操作的场景中非常适用。 例如，用于实现字典、索引、关联数组等数据结构。

平衡二叉树 (Balanced Binary Tree)

概念：为了解决二叉搜索树在极端情况下退化成链表的问题，保证树的平衡性，提高查找效率

虽然二叉搜索树在平均情况下查找效率很高，但在 最坏情况下 (例如，插入的节点值是有序的)，BST 可能退化成一条 链表，树的深度变为 O(n)，导致查找效率也退化为 O(n)，失去了 BST 的优势。

平衡二叉树 (Balanced Binary Tree) 就是为了解决这个问题而提出的。

平衡二叉树是一种特殊的二叉搜索树，它通过 某种机制 来 保证树的结构相对平衡，限制树的深度，从而避免退化成链表，始终维持较高的查找效率。

常见类型 (Common Types)

常见的平衡二叉树类型有多种，它们采用了不同的平衡策略，各有优缺点。

对于初学者，了解以下两种最常见的平衡二叉树类型即可：

  1. AVL 树 (AVL Tree)： 最早被发明的自平衡二叉搜索树。

    AVL 树通过 高度平衡 来保持平衡。

    每个节点的左子树和右子树的高度差的绝对值最多为 1。

    为了维持 AVL 树的平衡性，插入和删除节点时，如果破坏了平衡条件，需要进行 旋转操作 (Rotate) 来调整树的结构，使其重新满足平衡条件。

    AVL 树的查找、插入、删除操作的时间复杂度都严格保持在 O(log n)。但 AVL 树的平衡条件比较严格，导致插入和删除操作需要进行更多的旋转调整，维护平衡的代价相对较高。

  2. 红黑树 (Red-Black Tree)： 一种更 “宽松” 的平衡二叉搜索树，也广泛应用于实际中，例如 Java 的 TreeMap 和 C++ 的 map 底层实现就是红黑树。

    红黑树通过一套 颜色标记 (红色或黑色) 和 旋转、颜色翻转 操作来维持平衡，其平衡条件相对 AVL 树宽松，但仍然能够保证较好的查找性能。

    红黑树的插入和删除操作的平均性能比 AVL 树更优，但最坏情况下的查找性能略逊于 AVL 树。

    由于红黑树的实现相对复杂，对于初学者，可以先了解红黑树的概念和基本性质，知道它也是一种平衡二叉树即可。

    红黑树的性质 (简单了解即可):

    • 每个节点是红色或黑色。
    • 根节点是黑色。
    • 所有叶子节点（NIL 节点，空节点）都是黑色。
    • 如果一个节点是红色，则它的子节点必须是黑色（不能有连续的红色节点）。
    • 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点（黑色完美平衡）。

适用场景 (Use Cases)

树结构由于其层级关系和高效的操作，在计算机科学和实际应用中都有着广泛的应用：

  1. 组织层级数据： 树结构天然适合表示具有层级关系的数据，例如：

    • 文件系统： 目录和文件的层级结构可以用树来表示，文件夹作为父节点，文件和子文件夹作为子节点。
    • 组织结构： 公司、机构的组织架构，部门、职位之间的上下级关系可以用树来表示。
    • 族谱家谱： 家庭成员之间的血缘关系可以用树来表示。
    • HTML/XML 文档结构： HTML 和 XML 文档的标签嵌套结构可以用树来表示 (DOM 树、XML 树)。

  2. 快速查找和排序： 二叉搜索树 (BST) 和平衡二叉树 (AVL 树、红黑树) 非常适合用于实现 高效的查找和排序算法。 例如：

    • 字典、词典： 使用 BST 或平衡树来存储单词和解释，可以快速查找单词。
    • 索引： 数据库、搜索引擎的索引可以使用 BST 或平衡树来加速数据检索。
    • 关联数组、映射 (Map)： 例如 Java 的 TreeMap，C++ 的 map，Python 的 dict 底层可以使用平衡树实现（例如红黑树）。
    • 优先级队列： 堆（一种特殊的树结构）常用于实现优先级队列。

  3. 路由算法： 网络路由协议 (例如 RIP、OSPF) 可以使用树结构 (例如生成树、最短路径树) 来计算网络中的最佳路径。

  4. 决策树： 机器学习中的决策树算法使用树结构来进行分类和预测。

  5. 语法树、抽象语法树： 编译器使用树结构来表示程序代码的语法结构，用于语法分析、语义分析、代码优化等。

总结

树是一种非常重要且强大的数据结构，它以其独特的层级结构和高效的操作，在计算机科学的各个领域都扮演着至关重要的角色。

理解树的概念、类型、遍历方式、以及各种特殊类型的树（如二叉树、二叉搜索树、平衡二叉树）的特性和应用场景，是深入学习算法和数据结构的关键一步。

掌握树结构，能够帮助你更好地组织和处理层级数据，构建更高效、更灵活的系统。

计算机科学基础 > 数据结构 > 初学者入门 > 3.进阶数据结构
#数据结构 #树
树 (Tree)
https://god23bin.github.io/unreal-engine-blog/2025/01/01/cs/ds/ds-for-beginner/advanced-ds/树 (Tree)/
作者
god23bin
发布于
2025年1月1日
许可协议