文档介绍：数据结构——第15讲
主讲:张华杰
Napoleonz@
0371-7657211
第15讲树的计数 图的基本概念和存储表示
章节范围:
上次课的内容
Huffman树—最优二叉树
概念: 路径长度、树的路径长度、结点的带权路径长度、树的带权路径长度、最优树、最优二叉树(Huffman树)、前缀编码、Huffman编码
Huffman树的特点:无度为1的结点
Huffman树的构造算法
Huffman编码与译码
树的高级话题
树与等价问题
集合的表示----双亲表示法表示的树
回溯法与树的遍历
求含n个元素的集合的幂集----依次对集合中元素“取”或“舍”
3-
树的计数
图的定义与术语
图的存储结构
4-
树的计数问题 具有n个结点的不同形态的树有多少棵?
二叉树T和T՛相似
二者均为空树,或
二者均不为空树,且它们的左右子树分别相似
二叉树T和T՛等价
二者相似,且
所有对应结点上的数据元素均相同
二叉树的计数问题 具有n个结点、互不相似的二叉树的数目bn
树的计数(1)
5-
树的计数(2)
二叉树的计数问题的另一种考虑角度
依据:已知二叉树的结点的先序序列和中序序列,能唯一确定一棵二叉树。(为什么?)
假设:二叉树的 n 个结点从1到n 加以编号,且其先序序列为1,2,…, n
不同形态的二叉树的数目先序序列均为1,2,…, n的二叉树所能得到的中序序列的数目 中序遍历的过程:一个结点进栈和出栈的过程 二叉树的形态确定了其结点的进栈和出栈的顺序,也确定了其结点的中序序列。
具有n 个结点的树的数目tn=bn-1 依据:森林与二叉树的相互转换
6-
重点:图在邻接矩阵和邻接表上的遍历算法及其应用
难点:求图的最小生成树、最短路径、拓扑排序等算法及其应用、性能分析
第七章图
第七章图
图的定义和术语
图的存储结构
图的遍历
图的连通性问题
有向无环图及其应用
最短路径
8-
图的定义和术语(1)
图的定义
图是由顶点集合(vertex)及顶点之间的关系集合组成的一种
数据结构。G = (V, {E}) V-顶点集,E-关系的集合
顶点之间的关系是任意的(m : n)
顶点之间的关系是否有方向性:有向图、无向图
无向图:边(v,w) ∊ E (v,w ∊V),v与w互为邻接点,边( v, w )依附于顶点v和w,或者说边( v, w )和顶点v, w相关联。 顶点v 的度是和v相关联的边的数目,记为TD(v) 。
有向图:弧<v,w> ∊ E (v,w ∊V),w为弧头, v为弧尾; 顶点v 邻接到顶点w,顶点w 邻接自顶点v,弧< v, w >和顶点v、w相关联。 顶点v 的入度是以v 为弧头的弧的数目,记为ID(v); v 的出度是以v为弧尾的弧的数目,记为OD(v); v 的度是TD(v) = ID(v) + OD(v)。
9-
图的定义和术语(2)
路径与连通性
路径、简单路径、回路(环)、简单回路
顶点之间的连通性、无向连通图、有向强连通图
G1: V1V3V4V1V2 是从V1 到V2 的路径,不是简单路径; V1V2是简单路径; V1V3V4V1V3V4V1是环,不是简 单环; V1V3V4V1是简单环。 ID(V1)=1, OD(V1)=2, TD(V1)=3 V1和V4是连通的;从V1到V2是连通的, 但从V2到V1是不连通的。 G1不是强连通图
G2: V1V2V3V5V2 是V1和V2间的路径, 但不是简单路径;V1V2是简单路径; V2V3V5V2V3V5V2是环,但不是简单环
V2V3V5V2是简单环。TD(V1)=2 V1和V4是连通的; G2是连通图
V1
V3
V2
V4
V1
V2
V3
V5
V4
G1
G2
10-