《数据结构》第六、七章学习指导

第六章树

1、树的相关概念：结点的度、树的度、孩子、双亲等，一般树能否为空，二叉树能否为空？ 2、二叉树的定义、性质？第i层上结点个数、深度为k的二叉树结点个数、满二叉树、完全二叉树、完全二叉树结点编号间的关系，度为2的树与二叉树的区别（二叉树有序）？ 3、二叉树的存储结构:重点掌握二叉链表。

4、二叉树的遍历：三大遍历方法、写遍历结果、根据遍历结果画树、遍历算法的应用（相关程序设计问题，如统计结点数等，参见课件）？ 5、线索二叉树的定义？

6、一般树与二叉树的相互转换？森林与二叉树的相互转换？ 7、哈夫曼树的定义、特点、生成、哈夫曼编码、计算WPL？ 8、已知二叉完全树的结点个数，求叶子结点个数？见课件。 9、树中结点在m层，则该结点的子树的根在哪一层？

第七章图

1、图的相关定义：弧、弧头、弧尾、有向完全图、无向完全图、连通、连通图、连通分量、强连通、强连通的有向图、强连通分量等？

2、图的存储结构，重点掌握邻接矩阵、邻接链表？ 3、图的遍历：深度优先、广度优先基本思想？

4、图的生成树：概念、特点；最小生成树：概念，生成算法，prim,kruskal算法？ 5、迪杰斯特拉算法求最短路径？ 6、拓扑排序概念、方法。

第六、七章综合练习参考答案 一、填空

1、 树结构体现了数据元素间一对多的关系。在树中除根结点外，其余结点有且仅有一个直接前驱；除叶子结点外，其余结点可能有多个直接后继。 2、 树的遍历方法主要有先根遍历、中根遍历和后根遍历。

3、 树中某结点在第k层，则该结点的孩子（即该结点的子树的根）在k+1层。 4、 二叉树的重要性质1。 5、 二叉树的重要性质2。

6、 完全二叉树中结点间编号的关系：若某结点的编号为i，则其双亲（若有）的编号为i/2，

左孩子（若有）的编号为i*2，右孩子（若有）的编号为i*2+1。 7、 在二叉平衡树中，平衡因子hl-hr的所有可能取值有－1、0、1。 8、 树不能为空，但二叉树可以为空。 9、 对森林先根遍历的结果与对其转换而成的二叉树先根遍历的结果相同。 10、 对森林后根遍历的结果与对其转换而成的二叉树中根遍历的结果相同。 11、 把一棵树转换为二叉树后，这棵二叉树的形态是唯一的。 12、 完全二叉树就是在同高度的满二叉树的最大层上从右向左连续删除若干结点所构

成。 13、 任意一棵哈夫曼树的带权路径长度都等于其所有非叶子结点的权值之和。 14、 树中的结点数比边数多1。 15、 二叉树可以采用顺序存储结构，也可以采用链式存储结构。

16、 对一般树先根遍历的结果与对其转换而成的二叉树先根遍历的结果相同。 17、 对一般树后根遍历的结果与对其转换而成的二叉树中根遍历的结果相同。 18、 在二叉排序树中，比根结点小的结点一定在根结点的左子树上，比根结点大或相等的结点一定在根结点的右子树上。对二叉排序树做中根遍历可以得到一个由小到大的序列。 19、 哈夫曼树是带权路径长度最短的树。 20、 图的遍历方法主要有深度优先遍历和广度优先遍历。 21、 稠密图适用于邻接矩阵存储结构。 22、 稀疏图适用于邻接链表存储结构。 23、 图的生成树是原图的极小连通子图。 24、 有向图的邻接矩阵中第i行中1的个数就是顶点i的出度，第i列中1的个数是顶

点i的入度。 25、 无向完全图中边的数目为n*(n-1)/2,有向完全图中边的数目为n*(n-1)。 26、 有n个顶点的有向图，至少需要n-1条弧才能保证是连通的。 27、 无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。 28、 在一个图中，所有顶点的度数之和等于图的边数的2倍。 29、 图的最小生成树一定包含原图的n个顶点，但只有n-1条边。

二、综合设计分析题

1、构造一棵哈夫曼树，对字符串“aaabccccccdddaabccccddd”进行哈夫曼编码。 解：统计各字符出现次数：a:5次；b:2次；c:10次；d:6次； 以各字符出现的次数为权构造哈夫曼树：

各字符的哈夫曼编码：a:111; b:110; c:0; d:10;

2、求下图中从顶点1到其余顶点的最短路径。

解：终点 dist[i]的变化 2 50（1，2） 50（1，2） 45（1，3，4，2） 3 10（1，3） 4 ∞ 25（1，3，4） 5 ∞ ∞ 60（1，3，4，5） 55（1，3，4，2，5） 6 ∞ ∞ ∞ ∞ S {1，3} {1，3，4} {1，3，4，2} {1，3，4，2，5} 结论：1到2的最段短路径为45（1，3，4，2）；1到3的最短路径为10（1，3）； 1到4的最短路径为25（1，3，4）；1到5的最短路径为55（1，3，4，2，5）； 1到6没有最短路径。

3、采用prim算法构造下图的最小生成树，并依次写出每一步生成的边。

解：最小生成树为

根据prim算法依次生成的边是：（D，H）；（H，E）；（H，A）；（H，I）；（E，B）； （E，F）；（F，C）；（C，G）；（G，J）。

4、采用kruskal算法构造上图的最小生成树，并依次写出每一步生成的边。 解：最小生成树为

根据kruskal算法依次生成的边是：（H，E）；（H，D）；（H，A）；（E，B）； （E，F）；（C，G）；（H，I）；（F，C）。

5、把如图所示的树转化成二叉树。

类似题目还有很多，请多参考课件。