Mujin Blog

主题

00:00:00
2025-09-10 14:28:252025-11-29 02:24:23
8258
35.9m
0

树 原创 ​

树形结构是重要的非线性结构，用于表示数据元素之间的层次关系。

一、 树的定义 ​

树是 n(n≥0) 个结点的有限集。当 n=0 时，称为空树。对于非空树( n>0 )，有且仅有一个特定的称为的结点，其余结点可分为 m(m≥0) 个互不相交的有限集，每个集合本身又是一棵树，称为根的。

二、 基本术语 ​

  • 结点的度：结点拥有的
  • 树的度：树内
  • 叶子结点：的结点（终端结点）
  • 分支结点：的结点（非终端结点）
  • 孩子结点：一个称为该结点的孩子
  • 双亲结点：
  • 兄弟结点：同一双亲的孩子之间
  • 结点的层次：根为第一层，其孩子为第二层，以此类推
  • 树的深度：树中
  • 有序树：树中结点的
  • 无序树：树中结点的
  • 森林：m(m≥0)棵互

三、二叉树 ​

  • 二叉树是n(n≥0)个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
  • 每个节点最多有两棵子树，且子树有左右之分。

3.1 二叉树的性质 ​

  1. 在二叉树的第 i 层上至多有 个结点(i≥1)
  2. 深度为 k 的二叉树有 个结点(k≥1)
  3. ：对任何一棵二叉树 T ，如果其终端结点数为 n₀ ，度为2的结点数为 n₂，则 n₀ = n₂ + 1

证明过程

设二叉树中结点总数为 ，度为 1 的结点数为 ，度为 2 的节点数为 ，

  1. 则有公式1 ：
  1. 再看二叉树中的分支数: 除根结点外，每个结点都有一个分支进入，设 B 为分支总数，则:

由于这些分支都是由度为 1 或 2 的结点射出的，所以有：

所以得到公式2：

由公式1 和公式2 得：

最终得到

  1. 具有 n 个结点的的深度为:
  2. 对，则 i (1≤i≤n)有：
    • 如果 i=1 ，则结点i是二叉树的根，无双亲
    • 如果 i>1 ，则其双亲是结点 i/2
    • 如果 2i>n ，则结点 i 无左孩子；否则其左孩子是结点 2i
    • 如果 2i+1>n ，则结点 i 无右孩子；否则其右孩子是结点 2i+1

3.2 二叉树的遍历 ​

定义一棵，节点值为 A、B、C、D、E、F、G，结构如下：

  • 根节点：A

  • A的左子树：以 B 为根，B 的左子树是 D ，B 的右子树是 E

  • A的右子树：以 C 为根，C 的左子树是 F ，C 的右子树是 G

  • 示例树图示

3.2.1 深度优先遍历（DFS） ​

深度优先遍历优先沿，再其他路径，核心分为3种：（"序"指）。

3.2.1.1 前序遍历（根→左→右） ​

  • 遍历规则:

    1. 先访问；
    2. 递归遍历根节点的（按前序规则）；
    3. 递归遍历根节点的（按前序规则）。

  • 示例树遍历过程

    • 根A → 左子树（B）→ 根B → 左子树（D）→ 根D（无左右子树）→ 回溯B的右子树（E）→ 根E（无左右子树）→ （C）→ 根C → 左子树（F）→ 根F → 回溯C的右子树（G）→ 根G
    • 前序结果：A → B → D → E → C → F → G

  • 遍历路径（红色箭头为访问顺序）

3.2.1.2 中序遍历（左→根→右） ​

  • 遍历规则:

    1. 递归遍历根节点的（按中序规则）；
    2. 访问；
    3. 递归遍历根节点的（按中序规则）。

  • 示例树遍历过程

    • A的左子树（B）→ B的左子树（D）→ 根D → 回溯访问B → B的右子树（E）→ 根E → 回溯访问A → A的右子树（C）→ C的左子树（F）→ 根F → 回溯访问C → C的右子树（G）→ 根G
    • 中序结果：D → B → E → A → F → C → G

  • 遍历路径

3.2.1.3 后序遍历（左→右→根） ​

  • 遍历规则:

    1. 递归遍历根节点的（按后序规则）；
    2. 递归遍历根节点的（按后序规则）；
    3. 访问。

  • 示例树遍历过程

    • A的左子树（B）→ B的左子树（D）→ 根D → B的右子树（E）→ 根E → 回溯访问B → A的右子树（C）→ C的左子树（F）→ 根F → C的右子树（G）→ 根G → 回溯访问C → 回溯访问A
    • 后序结果：D → E → B → F → G → C → A

  • 遍历路径

3.2.2 广度优先遍历（BFS） ​

广度优先遍历（又称）按访问节点，（第1层），再访问第2层所有节点，依次向下，实现（先进先出）。

  • 遍历规则:

    1. 将根节点入队；
    2. 出队一个节点，访问它；
    3. 若该节点有左子节点，入队；若有右子节点，入队；
    4. 重复步骤2-3，直到队列为空。
    5. 一层一层，

  • 示例树遍历过程

    • 队列初始：[A] → 出队A（访问）→ 入队B、C → 队列：[B,C]
    • 出队B（访问）→ 入队D、E → 队列：[C,D,E]
    • 出队C（访问）→ 入队F、G → 队列：[D,E,F,G]
    • 出队D（访问）→ 无子女 → 队列：[E,F,G]
    • 出队E（访问）→ 无子女 → 队列：[F,G]
    • 出队F（访问）→ 无子女 → 队列：[G]
    • 出队G（访问）→ 无子女 → 队空
    • 层次遍历结果：A → B → C → D → E → F → G

  • 遍历路径

软考真题解析（2023年软件设计师上午题）

一、题干
某二叉树的中序遍历序列为 a b c d e f，后序遍历序列为 a c e f d b，则该二叉树的前序遍历序列为（ ）。

A. b d a c e f
B. b d a c f e
C. b a d f c e
D. b a d c f e

二、解题步骤（核心：由中序+后序推前序）

  1. 确定根节点：后序遍历最后一个节点是根节点 → 根为 b；

  2. 划分左右子树（中序）：中序序列中，根 b 左侧是左子树（a），右侧是右子树（c d e f）；

  3. 递归分析右子树：

    • 右子树的后序序列：后序中根 b 之前的右侧部分（c e f d）→ 右子树的根是 d（后序最后一个）；
    • 右子树的中序序列：c d e f → 根 d 左侧是左子树（c），右侧是右子树（e f）；

  4. 分析最右侧子树：

    • 该子树的后序序列：e f → 根是 f；
    • 该子树的中序序列：e f → 根 f 左侧是左子树（e），右侧无；

  5. 还原二叉树（Mermaid图示）：

  6. 求前序遍历（根→左→右）：b → a → d → c → f → e → 对应选项 D。

3.2.3、核心考点总结 ​

遍历类型核心规则实现方式软考高频场景
前序遍历根→左→右递归/栈构建二叉树、复制树
中序遍历左→根→右递归/栈与后序/前序结合推树结构
后序遍历左→右→根递归/栈销毁树、计算树的高度
层次遍历按层级访问队列求树的宽度、层序处理

3.3 特殊二叉树 ​

构造特殊的二叉树，常见的有

3.3.1 满二叉树 (Full Binary Tree) ​

  • 定义：一棵深度为 k 且具有 个结点的二叉树。
  • 特点：
    1. 每一层上的结点数都达到。
    2. 都出现在。
    3. 结点（每个结点要么有 0 个孩子，要么有 2 个孩子）。
  • 示意图：
             1
       /   \
      2     3
     / \   / \
    4   5 6   7    // 深度3，结点数7 = 2^3 - 1

3.3.2 完全二叉树 (Complete Binary Tree) ​

  • 定义：深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的时，称为完全二叉树。
  • 特点：
    1. 叶子结点只能出现在。
    2. 最下层的叶子结点都的位置。
    3. 如果有度为 1 的结点，只可能有一个，且该结点。
    4. 同样结点的二叉树，。
    5. 是的实现基础。
  • 示意图：
             1
       /   \
      2     3
     / \   /
    4   5 6        // 编号与满二叉树的前6个编号一致。
                   // 结点6是最后一个结点，对应满二叉树中编号6的位置。
  • 与非完全二叉树的区别：
         1
   /   \
  2     3
 / \     \
4   5     6    // 这不是完全二叉树，因为结点3没有左孩子，
               // 但却有右孩子，破坏了 【依次排列在最左边】 的规则。

3.3.3 二叉排序树 (Binary Sort Tree, BST) ​

  • 定义：一棵空树，或者是具有如下性质的二叉树：

    1. 若它的左子树不空，则它的根结点的值。
    2. 若它的右子树不空，则它的根结点的值。
    3. 它的。

  • 特点：

    1. 二叉排序树，会得到一个。
    2. 查找、插入、删除的时间复杂度****。最好为 O(log n)（形态比较平衡），最坏为 O(n)（退化成单支树）。

  • 示意图：

        4
   / \
  2   6
 / \ / \
1  3 5  7     // 对于任意结点，左小右大。
              // 中序遍历（左 -> 根 -> 右）：1, 2, 3, 4, 5, 6, 7

3.3.4 平衡二叉树 (Balanced Binary Tree, AVL Tree) ​

  • 定义：首先，并且任何结点的（即平衡因子 BF ∈ {-1, 0, 1}）。

  • 特点：

    1. 是，保证了查找、插入、删除的时间复杂度为 。
    2. 在插入和删除操作后，需要通过（LL, RR, LR, RL）来重新平衡树。

  • 示意图（平衡 vs 不平衡）：

    // 平衡的AVL树                            // 不平衡的BST（不是AVL树）
    5                                      3
   / \                                    /
  2   7                                  2
 / \ /                                  /
1  4 6                                 1
(BF: 左子树高和右子树高绝对值不超过1)    (BF: 根节点左子树高和右子树高绝对值超过 1 为 2，违反平衡)

3.3.5 哈夫曼树 (Huffman Tree) / 最优二叉树 ​

  • 定义：给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的，则称为最优二叉树，也称哈夫曼树。

  • 相关概念：

    • 路径长度：路径上的分支数目。
    • 结点的带权路径长度：结点的权值 * 其路径长度。
    • 树的带权路径长度 (WPL)：树中的带权路径长度之和。

  • 特点：

    1. 。
    2. （即哈夫曼树也是正则二叉树）。
    3. 用于，是一种高效的数据压缩算法。

  • 示意图（权值：A=5, B=15, C=40, D=30, E=10）：

             [100]
        /    \ 
    (40)C    [60]       
            /    \ 
          [30]    (30)D    
          /   \ 
        [15]   (15)B 
       /   \    
    (5)A (10)E
    • WPL：20 + 40 + 45 + 60 + 40 = 205
      • A(5): 路径长度4 → 5×4 = 20
      • E(10): 路径长度4 → 10×4 = 40
      • B(15): 路径长度3 → 15×3 = 45
      • D(30): 路径长度2 → 30×2 = 60
      • C(40): 路径长度1 → 40×1 = 40

3.3.6 线索二叉树 (Threaded Binary Tree) ​

  • 定义：对二叉树进行。如果某个结点的结点；如果结点。这种附加的指针称为。

  • 特点：

    1. 充分利用空指针域（n 个结点的二叉树有 n+1 个空指针域）。
    2. 无需即可实现二叉树的中序、先序等遍历，提高了效率。
    3. 便于查找结点的前驱和后继。

  • 示意图（中序线索化）：

            // 普通二叉树         // 中序线索二叉树 (虚线为线索)
        1                   1
       / \                 / \ 
      2   3               2   3
     / \                 / \
    4   5               4   5
    // 中序: 4,2,5,1,3   // 4的右指针指向2 (后继)
                         // 5的右指针指向1 (后继)
                         // 3的左指针指向1 (前驱 需看具体实现)，右指针为空

五、树和森林 ​

树和森林的核心知识点、相互关系及转换规则如下所示

5.1 树的存储结构 ​

常用的树的存储有、和表示法。

5.1.1 树的双亲表示法 ​

  1. 方法：该表示法用一组地址连续的单元存储树的结点，并在每个结点中附设一个指示器（指针），指出其(即结点所在)，根节点的 parent 为 -1。

  2. 优点：这种表示法对于求都十分，时间复杂度： O(1)

  3. 缺点：但对于求则需要遍历整个数组，时间复杂度： O(n) ， n 为树中节点总数

  4. 示意图：

5.1.2 树的孩子表示法 ​

  1. 方法：该表示法在存储结构中用指针指示出,为树中每个建立一个,即令每个结点的表示的线性表,则n 个结点的树具有 n个单链表。将这个单链表的。

  2. 优点：查找的。只需遍历该节点的孩子链表即可。

  3. 缺点：查找的。必须遍历所有头节点的孩子链表，时间复杂度为 O(n) ， n 为树中节点总数。

  4. 示意图：

5.1.3 树的孩子兄弟表示法 ​

  1. 方法：孩子兄弟表示法又称为,它在链表的结点中域分别指向该结点的和。

  2. 优点：

    1. ：所有结点类型相同，操作方便。
    2. ：无论结点的度是多少，每个结点都只有两个指针域，空间利用率高。
    3. ：这是最重要的优点。它可以将任何复杂的树或森林转换为唯一的二叉树形态，从而能利用二叉树成熟的理论和算法来处理树和森林。

  3. 缺点：

    1. ：从当前结点出发，只能从（除非额外添加一个 parent 指针域）。
    2. ：如果要找某个结点的第 k 个孩子，必须从第一个孩子开始，通过 nextSibling 指针遍历 k-1 次才能找到。

  4. 示意图：

  5. 查找时间复杂度分析

在孩子兄弟表示法中，查找操作的时间复杂度取决于具体的查找类型：

查找操作时间复杂度原因分析
查找结点 X 的第一个孩子通过 X->firstChild 指针可直接访问。
查找结点 X 的下一个兄弟通过 X->nextSibling 指针可直接访问。
查找结点 X 的第 k 个孩子必须从 firstChild 开始，依次访问 nextSibling 共 k-1 次。
查找结点 X 的父结点最坏情况下需要从根结点开始遍历整棵树才能确定父结点。

5.2 树和森林的遍历 ​

5.2.1 树的遍历 ​

由于树中的每个节点可以有多个子树，因此遍历树的方法有，即（二叉树有三种）

  1. 树的先根遍历：，然后依次先根遍历各棵子树，对于先根遍历可参照。
  2. 树的后根遍历：，然后访问树根节点，对于后根遍历可参照

5.2.2 森林的遍历 ​

按照森林和树的相互递归定义，可得出森林有两种遍历方式

  1. 先序遍历森林(先访根，再访子，最后访邻树)：若森林非空，先访问森林中，最后在遍历，再除去第一棵树之后剩余的树构成的森林。
  2. 中序遍历森林(先访子，再访根，最后访邻树)：若森林非空，先的根结点的子树森林，再访问，最后除去第一棵树之后。

5.2.2.1 遍历示意图 ​

  • 有以下森林
  • 先序遍历：A → B → D → C → E → F → G → H → I

  • 中序遍历：结果 D → B → A → C → F → E → H → G → I

5.2.2.2 核心概念总结说明 ​

  1. 先序遍历森林的规则：

    • 访问森林中第一棵树的根结点
    • 先序遍历第一棵树中根结点的子树森林
    • 先序遍历除去第一棵树之后剩余的树构成的森林

  2. 中序遍历森林的规则：

    • 中序遍历森林中第一棵树的根结点的子树森林
    • 访问第一棵树的根结点
    • 中序遍历除去第一棵树之后剩余的树构成的森林

  3. 重要特性：

    • 森林的先序遍历序列与其对应二叉树的先序遍历序列相同
    • 森林的中序遍历序列与其对应二叉树的中序遍历序列相同

5.3 树、森林和二叉树之间的相互转换 ​

  • 树、森林和二叉树之间可以进行，即任何一个森林或者一个树都可以表现为一棵二叉树，而任何一个二叉树也能对应到一个森林或者一棵树。
  • 树、森转换成二叉树：利用，可导出树和二叉树的对应关系，一棵树可以转换成唯一的一棵二叉树。
  • 二叉树转换成森林、树：一棵二叉树可以转换成的一棵树或者森林

5.3.1 核心转换规则 ​

5.3.2 树 → 二叉树 ​

  • 转换步骤：左孩子，右兄弟，。

    1. 在所有兄弟节点之间加一条连线。
    2. 对每个节点，只保留它与第一个孩子的连线，删除它与其他孩子的连线。
    3. （可选）以树的根节点为轴心，将整棵树顺时针旋转一定角度，使其层次结构更清晰。

  • 示例：

    • 有以下树：

    • 转换过程： null 为空节点，不指向任何数据

    • 最终二叉树结构： null 为空节点，不指向任何数据

5.3.2 森林 → 二叉树 ​

  • 转换步骤：

    1. 将森林中的（方法同上）。
    2. 从，将其。
    3. 将第二棵二叉树的根作为（即作为其右指针）。
    4. 将第三棵二叉树的根作为，以此类推。

  • 示例：

    • 有以下森林：

      • 转换过程： null 为空节点，不指向任何数据
      • 最终二叉树结构： null 为空节点，不指向任何数据

5.3.3 二叉树 → 树/森林 ​

  • 转换步骤：

    1. 若某结点 X 是其双亲的左孩子，则 X 的所有右链上的结点都是其兄弟，也是其双亲的孩子。
    2. 将这些右指针连接起来。
    3. 去掉所有结点与右孩子的原始连接（即原二叉树中表示“兄弟关系”的右指针），恢复为树的结构。
    4. 将二叉树的根节点，以及其右链上的所有节点（即原森林中各树的根），分离为多棵树，形成森林。

  • 示例：

    • 有以下二叉树：

      1. 确定孩子兄弟关系：
      1. 确定第一棵树：第一棵树为根节点的左子树
      1. 确定第二棵树：第二棵树为根节点的右子树的节点加当前节点的左子树节点
      1. 确定第三棵树：第三棵树为根节点的右子树节点的右子树节点加左子树节点

    • 转换结果：

最近更新