1、1. 熟练掌握二叉树的结构特性 ， 了解相应的证明方法 。
2. 熟悉二叉树的各种存储结构的特点及适用范围 。
3. 遍历二叉树是二叉树各种操作的基础 。
实现二叉树遍历的具体算法与所采用的存储结构有关 。
掌握各种遍历策略的递归算法 ， 灵活运用遍历算法实现二叉树的其它操作 。
层次遍历是按另一种搜索策略进行的遍历 。
,本章重点:,4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系 ， 熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法 。
二叉树的线索化过程是基于对二叉树进行遍历 ， 而线索二叉树上的线索又为相应的遍历提供了方便 。
,5. 熟悉树的各种存储结构及其特点 ， 掌握树 。

2、和森林与二叉树的转换方法 。
建立存储结构是进行其它操作的前提 ， 因此应掌握 1 至 2 种建立二叉树和树的存储结构的方法 。
6. 学会编写实现树的各种操作的算法 。
7. 了解最优树的特性 ， 掌握建立最优树和哈夫曼编码的方法 。
,4,7.1 图的基本术语,其中：V 是G 的顶点集合 ， 是有穷非空集； E 是G 的边集合 ， 是有穷集 。
,问：当E(G)为空时 ， 图G存在否？ 答：还存在！但此时图G只有顶点而没有边 。
,有向图： 无向图： 完全图：,图G中的每条边都是有方向的； 图G中的每条边都是无方向的； 图G任意两个顶点都有一条边相连接；,若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 若 n 。

3、 个顶点的有向图有n(n-1) 条边, 称为有向完全图,V=vertex E=edge,图：记为 G( V, E ),5,证明：,证明：若是完全有向图 ， 则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点, 因此总边数=n(n-1),证明：从可以直接推论出无向完全图的边数因为无方向 ， 两弧合并为一边 ， 所以边数减半 ， 总边数为n(n-1)/2 。
, 完全无向图有n(n-1)/2 条边 。
, 完全有向图有n(n-1)条边 。
,6,例：判断下列4种图形各属什么类型？,无向,无向图(树),有向图,有向,n(n-1)/2 条边,n(n-1) 条边,G1的顶点集合为V(G1)=0,1,2,3 边集合为E(G1)=( 。

4、0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全图,完全图,7,稀疏图：稠密图：,设有两个图 G(V, E) 和 G(V, E) 。
若 V V 且 E E, 则称 图G 是 图G 的子图 。
,子 图：,边较少的图 。
通常边数远少于nlogn 边很多的图 。
,无向图中 ， 边数接近n(n-1)/2 有向图中 ， 边数接近n(n-1),8,带权图：,即边上带权的图 。
其中权是指每条边可以标上具有某种含义的数值（即与边相关的数） 。
,连通图：,在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的 。
如果图中任意一对顶点都是连通的, 则称此图是连通图 。
非连通图的极大连通子图叫 。

5、做连通分量 。
,带权图,在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图 。
,强连通图：,网 络：,非强连通图的极大强连通子图叫做强连通分量 。
,9,生成树：,是一个极小连通子图 ， 它含有图中全部n个顶点 ， 但只有n-1条边 。
,若干棵生成树的集合 ， 含全部顶点 ， 但构成这些树的边或弧是最少的 。
,有两类图形不在本章讨论之列：,图的基本术语(续),如果在生成树上添加1条边 ， 必定构成一个环 。
若图中有n个顶点 ， 却少于n-1条边 ， 必为非连通图 。
,生成森林：,10,邻接点：,有向边(u, v)称为弧 ， 边的始点u 叫弧尾 ， 终点v 叫弧头 。
,顶点 v 的入度是以 。

6、 v 为终点的有向边的条数, 记作 ID(v);
顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v) 。
,若 (u, v) 是 E(G) 中的一条边 ， 则称 u 与 v 互为邻接顶点 。
,弧头和弧尾：,入度和出度：,问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1 ， 此时是何形状？,度：,顶点v 的度是与它相关联的边的条数 。
记作TD(v) 。
在有向图中, 顶点的度等于该顶点的入度与出度之和 。
,u 的入度=? u 的出度=?,答：是树！而且是一棵有向树！,11,简单路径：,路径上各顶点 v1,v2,.,vm 均不互相重复 。
,回路：,若路径上第一个顶点 v1 与最后一个顶点vm 重 。

7、合 ， 则称这样的路径为回路或环 。
,路径：,在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm ， 到达顶点vj 。
则称顶点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点vi 到顶点 vj 的路径 。

来源：(未知)

【学习资料】网址：/a/2021/0330/0021813749.html

标题：[计算机软件及应用]数据结构图A