当前位置：首页 > news >正文

软考中级软件设计师考点知识点笔记总结 day06

news 来源：原创 2025/8/10 5:10:21

文章目录

- - - 6、树和二叉树
    - - 6.1、树的基本概念
      - 6.2、二叉树的基本概念
      - 6.3、二叉树的遍历
      - 6.4、查找二叉树（二叉排序树）BST
      - 6.5、构造霍夫曼树+
      - 6.6、线索二叉树
      - 6.7、平衡二叉树
    - 7、图
    - - 7.1 、存储结构 - 邻接矩阵
      - 7.2 、存储结构 - 邻接表
      - 7.3、图的遍历
      - 7.4、拓扑排序
      - 7.5 、最小生成树普利姆算法
      - 7.6、克鲁斯卡尔算法

6、树和二叉树

6.1、树的基本概念

结点的度：一个结点的度是指该结点拥有的子树数量或直接连接到它的子节点的数量。例如，如果一个结点有三个子节点，则称这个

结点的度为3。结点拥有的子树个数称为结点的度

树的度：树的度是树中所有结点的度的最大值。换句话说，它是树中任何一个结点的最大子节点数。
叶子结点（Leaf Node）：也称为终端结点，指的是没有子节点的结点。即度为0的结点。
分支结点（Branch Node）：与叶子结点相对，分支结点是指至少有一个子节点的结点。包括根节点在内的所有非叶子结点都是分支

结点。

内部结点（Internal Node）：除了根节点以外的所有分支结点。有时也将根节点算作内部结点的一部分
父结点（Parent Node）：对于树中的任意结点（除根节点外），其直接上层结点被称为它的父结点。
子结点（Child Node）：相对于父结点而言，直接下层的结点被称为子结点。
兄弟结点（Sibling Node）：拥有同一父结点的结点互为兄弟结点。
层次（Level）：从根开始计算，根节点位于第1层，它的直接子节点位于第2层，以此类推。层次也可以用来描述树的高度或者深

度，其中树的高度是指从根到最远叶子结点的最长路径上的边的数量。

6.2、二叉树的基本概念

二叉树的重要特性每个节点最多有两个子节点

二叉树的第i层上最多2^(i - 1)个结点

深度为k的二叉树最多2^k - 1个结点

对任何一颗二叉树如果叶子结点数为 n0 度为2的结点数为n2 n0 = n2 + 1

满二叉树叶子节点外，所有节点都有两个子节点。
完全二叉树除最后一层节点外，其他层节点都必须要有两个子节点，并且最后一层节点都要左

排列。完全二叉树要满足两个条件：

1.除最后一层节点外，其他层节点都必须要有两个子节点
2.最后一层节点都要左排列

没有满足完全二叉树的例子就可以称为非完全二叉树。

6.3、二叉树的遍历

前序遍历根左右

中序遍历左根右

后序遍历左右根

层次遍历

    A/ \B   C/ \
D   E

前序：A B D E C
中序：D B E A C
后序：D E B C A
层次：A B C D E

反向构造二叉树

由前序序列为ABHFDECG 中序序列为 HBEDFAGC 构造二叉树

        A/ \B   C/   /H   G\F/D/E

树转二叉树

孩子结点左子树结点兄弟结点右孩子结点

孩子结点作为左结点同层兄弟结点作为右结点

    A/|\B C D/ \
E   F

    A/B —— C —— D/  
E —— F

6.4、查找二叉树（二叉排序树）BST

特点左孩子小于根右孩子大于根

插入节点的要求：
唯一性：
插入的值必须是唯一的，不能与树中已有节点的值重复。若存在重复值，插入操作失败。
示例：若树中已有节点值为 58，则插入 58 的操作会被拒

位置要求：
新节点必须作为叶子节点插入，即插入位置是查找路径上的最后一个空子节点。
实现逻辑：通过递归或迭代查找，直到找到空位置

维护 BST 性质：
左子树 < 根 < 右子树：
若插入值小于当前节点，继续向左子树查找。
若插入值大于当前节点，继续向右子树查找。

删除节点的要求：
根据节点的子节点情况分为三种情况：

叶子节点（无子节点）：
直接删除该节点，父节点的对应子指针设为 null。

单子节点（只有左或右子节点）：
将子节点直接替代被删除节点的位置。例如：
若删除节点有左子节点，则父节点的左/右指针指向左子节点。
若删除节点有右子节点，则父节点的左/右指针指向右子节点。

双子节点（左右子节点均存在）：
替换规则：
找到左子树的最大值（前驱）或右子树的最小值（后继）。
用该值替换被删除节点的值，然后删除前驱或后继节点（递归处理）。
示例：删除节点 62（假设其左右子树均存在），可用左子树的最大值 58 替换 62，然后删除 58。

6.5、构造霍夫曼树+

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度

假设有一组权值 5，29，7，14，23，3，11 构建霍夫曼树

步骤 1：初始权值列表
将权值按升序排列：
3, 5, 7, 11, 14, 23, 29

步骤 2：合并最小的两个权值
第 1 次合并
选择最小的两个权值：3 和 5
合并后的权值：
3+5=8
新列表：
7,8,11,14,23,29
生成的树：

   8  / \  3   5

第 2 次合并
选择最小的两个权值：7 和 8
合并后的权值：
7+8=15
新列表：
11,14,15,23,29
生成的树：

    15  /  \  7    8  / \  3   5

第 3 次合并
选择最小的两个权值：11 和 14
合并后的权值：
11+14=25
新列表：
15,23,25,29
生成的树：

    25  /  \  11   14

第 4 次合并
选择最小的两个权值：15 和 23
合并后的权值：
15+23=38
新列表：
25,29,38
生成的树：

    38  /  \  15  23  /  \  
7    8  / \  3   5

第 5 次合并
选择最小的两个权值：25 和 29
合并后的权值：
25+29=54
新列表：
38,54
生成的树：

    54  /  \  25  29  /  \  
11  14

第 6 次合并
选择最小的两个权值：38 和 54
合并后的权值：

38+54=92
最终根节点：92
完整霍夫曼树结构：

         92  /  \  38    54  /  \   /  \  15  23 25  29  /  \       /  \  7    8    11  14  / \  3   5

6.6、线索二叉树

为什么要有线索二叉树？

1、解决空指针浪费问题

2、加快遍历和查找效率

线索二叉树的概念

线索二叉树（Threaded Binary Tree）是通过将二叉树的空指针域转化为线索（指向遍历序列中的前驱或后继节点）而形成的二叉树。

类型

根据遍历方式的不同，线索二叉树分为：
前序线索二叉树：线索指向先序序列的前驱或后继。
中序线索二叉树：线索指向中序序列的前驱或后继。
后序线索二叉树：线索指向后序序列的前驱或后继。

存储结构

每个节点包含以下字段：
数据域（data）：存储节点值。
左、右指针（leftChild、rightChild）：指向左右子节点或线索。
左、右标志位（ltag、rtag）：
ltag：若为 0，左指针指向左孩子；若为 1，左指针指向遍历序列的前驱。
rtag：若为 0，右指针指向右孩子；若为 1，右指针指向遍历序列的后继。

线索二叉树的表示

如何将二叉树转为线索二叉树？

选择遍历方式

根据需求选择先序、中序或后序遍历，确定线索指向的前驱和后继序列。
遍历并线索化
使用递归或非递归方法遍历二叉树。
在遍历过程中，记录每个节点的前驱节点（pre）。
当遇到空指针时，将其替换为对应的前驱或后继线索，并设置标志位。

6.7、平衡二叉树

平衡二叉树提出原因？

解决BST的退化问题：防止树因数据有序而退化为链表，导致性能下降。
保证操作效率：通过高度限制和旋转操作，确保时间复杂度为 O(log⁡n)O(logn)。
自适应调整：动态维护树的平衡，适应频繁的插入和删除操作。
应用广泛性：为后续的自平衡树（如红黑树、B树）奠定了基础，成为高效数据管理的关键结构。

对数列{1，5，7，9，8，39，73，88} 构造排序二叉树

可以构造出多少形式不同的排序二叉树？

定义 任意结点的左右子树深度相差不超过1 每结点的平衡度只能为 -1 、 0 或1

7、图

有向图

无向图

完全图无向图中，若每对顶点之间都有一条边相连则称该图为完全图。在有向图中每对顶点之间都有二条有向边相互连接则称为完全图

度、入度、出度

7.1 、存储结构 - 邻接矩阵

邻接矩阵（Adjacency Matrix）是用一个 n×n 的二维数组表示图的结构，其中：

行和列对应图中的顶点。
元素值表示顶点之间的连接关系：
无权图：1 表示有边，0 表示无边。
带权图：元素值为边的权重，无边时用特殊值（如 0 或 ∞）表示。

有向图与无向图的区别
无向图：邻接矩阵对称（因为边是双向的）。
例如，若顶点 A 与 B 连接，则 A→B 和 B→A 对应的矩阵元素均为 1。
有向图：邻接矩阵不对称。
例如，若顶点 A 有边指向 B，则 A→B 的元素为 1，但 B→A 的元素可能为 0。

顶点的度数计算
无向图：顶点的度 = 该行（或列）的元素之和。
例题：
已知无向图邻接矩阵中顶点 B 的行元素为 [1, 0, 1]，则其度数为 2。
有向图：
出度：该行元素之和。
入度：该列元素之和。
例题：
有向图邻接矩阵中顶点 B 的行元素为 [0, 1, 0]，列元素为 [1, 0, 0]，则：
出度为 1（指向 C），入度为 1（来自 A）。

图的类型判断
完全图：
无向图：除对角线外所有元素为 1。
有向图：每对顶点之间有两条边（双向），矩阵中非对角线元素全为 1。
自环：顶点与自身有边时，对角线元素为 1。
环：若存在路径 A→B→A，则矩阵中 A→B 和 B→A 均为 1。

邻接矩阵的优缺点
优点：
快速判断两点是否直接相连（时间复杂度 O(1)）。
方便计算顶点的度、入度、出度。
缺点：
空间复杂度高（O(n²)），稀疏图浪费空间。
插入/删除顶点需重构矩阵，效率低。

7.2 、存储结构 - 邻接表

首先每个顶点的邻接顶点用链表示出来然后用一个一维数组来顺序存储上面每个链表的头指针

7.3、图的遍历

      v1/  \v2    v3/ \    / \
v4  v5 v6  v7\v8

深度优先 v1, v2, v4, v8, v5, v3, v6, v7，

广度优先 v1, v2, v3, v4, v5, v6, v7, v8。

7.4、拓扑排序

我们把用有向边表示活动之间开始的先后关系这种有向图称为用顶点表示活动网络简称AOV网络。

仅适用于有向无环图（DAG），若图中存在环，则无法进行拓扑排序。

拓扑序列不唯一，但所有合法序列必须满足依赖关系。

7.5 、最小生成树普利姆算法

普利姆算法（Prim算法）是用于求解**带权无向连通图的最小生成树（MST）**的贪心算法。其核心思想是：

逐步扩展：从一个顶点出发，逐步将顶点加入最小生成树集合，每次选择当前集合到未加入集合的最小边。
贪心策略：每一步选择局部最优（当前最小边），最终得到全局最优解。

适用条件

必须是连通图：若图不连通，需分别处理每个连通分量，生成最小生成森林。
无向图：普利姆算法仅适用于无向图，且边有权值。

7.6、克鲁斯卡尔算法

克鲁斯卡尔算法（Kruskal Algorithm）是用于求解**带权无向连通图的最小生成树（MST）**的贪心算法。其核心思想是：

逐步选边：按边权值从小到大依次选择边，每次选择一条不形成环路的边，直到所有顶点连通。
贪心策略：每一步选择当前最小边，最终得到全局最优解。

2. 适用条件

必须是连通图：若图不连通，需分别处理每个连通分量，生成最小生成森林。
无向图：克鲁斯卡尔算法仅适用于无向图，且边有权值。

文章目录

6、树和二叉树

6.1、树的基本概念

6.2、二叉树的基本概念

6.3、二叉树的遍历

6.4、查找二叉树（二叉排序树）BST

6.5、构造霍夫曼树+

6.6、线索二叉树

6.7、 平衡二叉树

7、 图

7.1 、 存储结构 - 邻接矩阵

7.2 、 存储结构 - 邻接表