数据结构作业：构建二叉树与最小生成树算法应用

本次作业是关于数据结构的课程作业，占总成绩的10%，其中程序的正确性和质量是评分的关键。作业提交时间为2019年12月15日，由学生杨轶完成，班级和学号为619231386。作业包括四道题目，涉及二叉树的构造、赫夫曼树的构建以及最小生成树和最短路径的求解。 第1题：题目要求根据给定的二叉树的中序遍历序列（BFDGAEC）和后序遍历序列（FGDBECA），重建这棵二叉树。这是一个典型的二叉树重构问题，通过中序遍历和后序遍历，可以确定每个节点的位置，因为中序遍历可以确定左子树和根节点的顺序，而后序遍历可以确定根节点和右子树的顺序。学生需要利用这些线索逐步构建二叉树。 第2题：赫夫曼树是一种带权路径长度最短的二叉树，题目给出了8个叶子节点的权值，要求画出对应的赫夫曼树并计算其WPL值（最小权重路径长度）。构建赫夫曼树的过程是递归的，通过合并权值最小的两个节点形成新的节点，直到所有节点都被合并。学生需要理解如何通过贪心策略来构建赫夫曼树，并计算WPL。 第3题：使用的是普里姆（Prim）或克鲁斯卡尔（Kruskal）算法来求解无向图的最小生成树。普里姆算法是从一个初始顶点开始，逐步添加连接其他顶点的边，确保每次添加的边都是当前未连接顶点中权重最小的，直到形成连通的树。在这个例子中，学生需找出图中连接各顶点的最小权重边。 第4题：迪杰斯特拉算法用于有向图中的单源最短路径问题，题目给出的是从顶点1出发，找到其余各顶点的最短路径。学生需要运用迪杰斯特拉算法，每次更新已知路径的最短距离，直到所有顶点都被考虑过。 这次作业涵盖了二叉树的构造、图论中的最小生成树和最短路径算法，这些都是数据结构和算法的重要组成部分，需要扎实的理论基础和实践能力。学生通过解决这些问题，不仅能够加深对数据结构的理解，还能提升算法设计和分析能力。