二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(18)

bbb) 遍历树、森林与遍历二叉树的关系

表 错误！文档中没有指定样式的文字。.9 遍历树、森林和二叉树的关系

树 先根遍历 后根遍历

森林 先序遍历 中序遍历

二叉树 先序遍历 中序遍历

赫夫曼树及其应用

ccc) 最优二叉树(赫夫曼树，哈夫曼树)

树的带权路径长度：所有叶子结点的带权路径长度之和。

WPL??wklk

k?1n

路径长度lk按分支数目计算。

带权路径长度最小的二叉树称为最优二叉树，或赫夫曼树(哈夫曼树)。 ddd) 构造赫夫曼树 算法：参见课本P145。

12

简单说，“每次取两个最小的树组成二叉树”。 eee) 赫夫曼编码(前缀码)

向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。

例：字符及其权值如下：A(6), B(7), C(1), D(5), E(2), F(8)，构造哈夫曼树和哈夫曼编码，计算带权路径长度。

12

不准确的说法，只为便于理解和记忆，不要在正式场合引用。

哈夫曼编码： A:00 B:01 C:1110 D:110 E:1111

WPL = (6+7+8)*2+5*3+(1+2)*4 = 69

或采用课本上的算法计算，如下。

说明：同样的一组权值可能构造出不同的哈夫曼树，结果不一定唯一，但带权路径长度都是最小的。 技巧：要使前一种方法构造出的赫夫曼树和课本上算法产生的一样，只要把每次合并产生的二叉树放在树的集合的末尾，并且总是用两个最小树的前者作为左子树后者作为右子树。

图

基础知识和算法

图的有关概念

图，顶点，弧，弧头，弧尾；有向图（顶点集+弧集），0≤e≤n(n-1)，无向图（顶点集+边集），0≤e≤n(n-1)/2；稀疏图（e<nlogn），稠密图；完全图e=n(n-1)/2，有向完全图e=n(n-1)；网，有向网，无向网。子图，邻接点，顶点的度，入度，出度；路径，路径长度（经过边或弧的数目），简单路径，回路（环），简单回路（简单环）；连通图，连通分量，强连通分量。

例：有6个顶点组成的无向图构成连通图，最少需要(_a_)条边；当边的数目大于(_b_)时，该图必定连通。

分析：a. 5。最少有n-1条边就可以构成连通图。 b. 10。考虑将n个顶点分成两组，一组有n-1个顶点，另一组只有1个顶点。首先在第一组中添加边，直到n-1个顶点构成全连通子图，共(n-1)(n-2)/2条边，此后若再在图中任意添加一条边将必定连通两组顶点，从而构成连通图。

思考：对有向图有何结论。

图的存储结构

图的存储结构

常见图的存储结构有：邻接矩阵，邻接表，逆邻接表，十字链表，邻接多重表。 邻接多重表只适用于存储无向图，其他存储结构可以存储无向图和有向图。

例：画出图的邻接矩阵、邻接表、逆邻接表和十字链表。

邻接矩阵 13简言之，“数组(顶点)+二维数组(弧)+个数”。

const int MAX_VERTEX = 最大顶点个数;

typedef struct Graph { // 图

VertexType vexs[MAX_VERTEX]; // 顶点向量 ArcType arcs[MAX_VERTEX] [MAX_VERTEX]; // 邻接矩阵

int vexnum, arcnum; // 顶点和弧的个数

} Graph;

图：有边(弧)为1；否则为0。网：有边(弧)为权值；否则为∞。

2存储空间个数为n，与边的数目无关。

无向图的邻接矩阵是对称的。

A

B

C

D

E

邻接表

13 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

简言之，“数组(弧尾顶点)+链表(邻接点)+个数”。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-18.html