文档内容
~ 2025年教师资格证·《信息技术》~
数 据 结 构 与 算 法 4 / 5
主讲老师 孙珍珍
粉笔教师教育 粉笔教师P284
三、树和二叉树的应用
（一）二叉排序树
1.二叉排序树的定义
19
13 50
11 66
26
9 12
21 30 60 70
特点1：中序遍历是升序
特点2：左子树 < 根节点 < 右子树P284
（二）二叉排序树
2.二叉排序树的查找
查找4 查找 7
特点：从根节点开始，小在左，大在右书上无
试题巩固
从空树开始，依次插入元素52， 26，14，32，71，60，93，58，24，41后构成了一棵二叉排序
树。在该树查找60要进行比较的次数为（ ）。
A.3
B.4
C.5
D.6P284
（二）哈夫曼树和哈夫曼编码
1.哈夫曼树的定义
Ø又称最优二叉树，是带权路径长度（WPL）最短的树
ü 权：为节点赋予某种意义的数值
ü 节点的带权路径长度：从根到节点的路径长度与该节点上权值的乘积
ü 树的带权路径长度：树中所有叶子节点的带权路径长度之和P285
（二）哈夫曼树和哈夫曼编码
2.哈夫曼树的构造
【例】给定权值集w={7，5，2，4}，构造关于w的哈夫曼树，并求其加权路径长度WPL。
第1步：找最小的2个数
第2步：组成二叉树（左小右大）根为2数之和
第3步：删除这2个数，并加入根（2数之和）
第4步：重复上述步骤书上无
试题巩固
设给定权集 w = { 5, 2, 3, 4｝，试构造关于 w 的一棵哈夫曼树，并求其加权径长度 WPL。
①构造的哈夫曼树可以不唯一
②但WPL一定是唯一且最小P286
（二）哈夫曼树和哈夫曼编码
3.哈夫曼编码
编码规则：左分支赋予0，右分支赋予1P286
（二）哈夫曼树和哈夫曼编码
【例】已知某系统在通信联络中只可能出现8 种字符（A~H），其概率分别为0.05，0.29，
0.07，0.08，0.14，0.23 ，0.03 ，0.11，试设计哈夫曼编码。
第1步：构造哈夫曼树
第2步：左0右1得到编码P286
（二）哈夫曼树和哈夫曼编码
【例】已知某系统在通信联络中只可能出现8 种字符（A~H），其概率分别为0.05，0.29，
0.07，0.08，0.14，0.23 ，0.03 ，0.11，试设计哈夫曼编码。第五节 图P287
一、图的基本概念
（一）图的定义
Ø记为 G=（V，E）
ü 顶点 V
ü 边 E
（二）图的相关术语
1.有向图
ü 边上有箭头。如：AC弧表示为
2.无向图
ü 边上无箭头。如：AC边表示为(A , C) 或 (C , A)
10.权/网
ü 边上有数值P288
（二）图的相关术语
5.邻接/依附/关联
Ø两个顶点之间有边/弧
Ø两个顶点互为邻接点、边依附顶点、边和顶点相关联
7.路径
Ø从顶点 1 到顶点 2 ，依次经过的顶点序列P288
（二）图的相关术语
3.完全图
Ø任意两顶点之间都有边/弧
Ø无向完全图，有 n（n–1）/2 条边
Ø有向完全图，有 n（n–1）条弧
8/9.连通图/强连通图
Ø任意两顶点之间都有通路P289
（二）图的相关术语
6.度
Ø度（TD）
$
ü 和顶点 v 相关联的边的数目 ! 𝑇𝐷(𝑣 ) = 2𝑒
!
!"#
Ø入度（ID）
$ $
ü 以顶点 v 为头的弧的数目 ! 𝐼𝐷(𝑣 ) = ! 𝑂𝐷(𝑣 ) = 𝑒
! !
!"# !"#
Ø出度（OD）
ü 以顶点 v 为尾的弧的数目总结下
（二）图的相关术语
术语 说明
1.有向图 边上有箭头。如：AC弧表示为
2.无向图 边上无箭头。如：AC边表示为(A , C)或(C , A)
任意两顶点都有边/弧
3.完全图
分：无向完全图 n（n–1）/2 条边 、有向完全图 n（n–1）条弧
4.子图 某个图的组成部分
两个顶点之间有边/弧
5.邻接、依附、关联
两个顶点互为邻接点、边依附顶点、边和顶点相关联
与顶点相关联的边/弧的个数
6.度
分：度（相连）、入度（箭头指向）、出度（箭头出去）
7.路径 从顶点A到顶点B，依次经过的顶点序列
任意两个顶点之间都有通路
8~9.连通
分：连通图、强连通图
10.权、网 边上有数值P290
二、图的存储
（一）邻接矩阵
图：有边写1，无边写0
网：有边写值，无边写∞P290
二、图的存储
（二）邻接表
无向图：写与该顶点相连的
有向图：写由该顶点出发的P291
三、图的遍历
（一）深度优先遍历
Ø类似树的先序遍历，从任意顶点出发，沿一个方向遍历一个相邻顶点，然后回溯P292
三、图的遍历
（二）广度优先遍历
Ø类似树的层遍历，从任意顶点出发，先遍历完该顶点所有相邻顶点，再遍历下一层书上无
试题巩固
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（ ）。
A. h、c、a、b、d、e、g、f
B. e、a、f、g、b、h、c、d
C. d、b、c、a、h、e、f、g
D. a、b、c、d、h、e、f、gP292
四、图的应用（旅行商问题）
旅行商问题（TSP）
u
Ø从一个城市出发，需要经过所有城市一次并且仅一次之后， 回到出发城市。
Ø要求总路程最短。
两种解决方法（贪心）
u
最短链接策略【关注的是边】
最近邻点策略【关注的是顶点】P292
1.最短链接策略
【例】假设 5 个相互可直达且距离已知的城市如下图（a）所示，采用最短链接策略从城市 A 出发
回到城市 A。
城市 距离 可用否
A
E B
D C
第1步：按距离升序排列
第2步：依次加入最短边
要求①：无回路
要求②：每个顶点≤2条边P293
2.最近邻点策略
【例】假设 5 个相互可直达且距离已知的城市如下图（a）所示，采用最近邻点策略从城市 A 出发
回到城市 A 。
A
E B
D C
第1步：找顶点X相邻的最短路径，确定下一个顶点Y
第2步：从Y出发，继续找Y相邻的最短路径
要求①：无回路
要求②：选未到过的顶点书上无
试题巩固
（2023上·高中）有五个相互可直达且距离已知的学校A、B、C、D、E，如下表所示，调研员从
学校A出发，去每个学校各调研一次，最后回到学校A，请找出一条路径最短的路线（ ）。
A.ADEBCA
A B C D E
B.ACDEBA
A
A —— 7 5 10 10
C.ABCDEA
B 7 —— 7 10 10
D.ADCBEA
C 5 7 —— 6 9
B C
D 10 10 6 —— 8
E 10 10 9 8 ——
D E书上无
试题巩固
（2021 下· 高中）“绿水青山就是金山银山”，加强环境保护对经济社会发展十分必要，长江和重
要支流进入十年禁渔期，一大批长江保护巡查员常年在“水上漂”，目的就是及时发现不法分子对长
江水域的各种破坏活动。有五个相互可直达且距离已知的工作站甲、乙、丙、丁、戊，如下表所示，
某巡查员从工作地甲出发，其他四个工作站巡查完后再回到工作站甲。产生式得出最短巡查路线的距
离x 是（ ）。
甲
A. 42
甲 乙 丙 丁 戊
B. 38
甲 —— 7 5 10 10 乙 丙
C. 36
乙 7 —— 7 10 10
D. 47
丙 5 7 —— 6 9
丁 10 10 6 —— 8
丁 戊
戊 10 10 9 8 ——第六节 查找和排序算法P294
（一）顺序查找
定义：在序列中依次与给定值进行比较
u
最坏查找次数：n
实例：在（2，45，36，17，6，86，62，87，91，25）中，查找数值“6”。
uP295
（二）二分查找
定义：前提有序（升序），先与中间值进行比较，若比中间值小则在前半段继续折半查找。
u
实例：在（8，15，23，37，46，63，66，71，80，86，88，101）中，查找“71”
u
次数 查找范围 中间位置 key与中间值比较 结果
第一次
第二次
第三次
第四次P295
（二）二分查找
实例：在（8，15，23，37，46，63，66，71，80，86，88，101）中，查找“71”
u
次数 查找范围 中间位置 key与中间值比较 结果
第一次 1 ~ 12 (1 + 12)/2 =6 71>63 在右侧
第二次 7 ~ 12 (7 + 12)/2 =9 71<80 在左侧
第三次 7 ~ 8 (7 + 8)/2 =7 71>66 在右侧
第四次 8 ~ 8 (8 + 8)/2 =8 71=71 成功
①查找失败标志：L > R
②最坏查找次数： log n + 1
!书上无
试题巩固
（2022 下 · 高中）猜数字游戏：系统随机产生一个 0 ～ 20 之间的整数， 要求玩家说出自己猜的
数字。判断玩家输入的数字。如果猜对了，则提示“恭喜你，猜对了”；如果猜错了，则提示“你猜
的数字大（小）了”。玩家在 3 次机会之内猜对给定的数字，则游戏成功，否则便失败。最坏情况
下需要几次才能猜对？请说出二分查找算法的基本原理。下
节
内
容在 粉 笔
遇 见 不 一 样 的 自 己
粉笔教师教育 粉笔教师
