【问题描述】
大学里实行学分制。每门课都有一定的学分。每个学生均需要修满规定数量的课程才能毕业。其中有些课程可以直接修读，有些课程需要一定的基础知识，必须在选了其他一些课程的基础上才能修读。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的“先修课”。在我们的大学里，假定每门课的直接先修课至多只有一门，两门课可能存在相同的先修课。例如：
|
课号 |
先修课号 |
学分 |
|
1 |
0 |
1 |
|
2 |
1 |
1 |
|
3 |
2 |
3 |
|
4 |
0 |
3 |
|
5 |
2 |
4 |
上例中，1是2的先修课，即如果要选修2，则1必定被选。
学生不可能学完大学里开设的所有课程，因此每个学生必须在入学时选定自己要学的课程。每个学生可选课程的总数目是给定的。现在请你们小组编写一个“学生选课系统”，任意给定一种课程体系（总课程数，课程之间的修读先后制约关系，学生毕业要求修的课程数目），该系统能帮助学生找出一种选课方案，使得他能得到的学分最多，并且必须满足先修课程优先的原则
例如：任意给定某一课程体系，该体系总共有7门课，每个学生必须修满4门课，该课程体系中，课程间的修读制约关系见下表：
|
2 |
2 |
|
|
0 |
1 |
|
|
0 |
4 |
|
|
2 |
1 |
|
|
7 |
1 |
|
|
7 |
6 |
|
2 |
2 |
|
2 |
|
|
6 |
|
|
7 |
|
3 |
表1表示，该课程体系总共有7门课，每个学生必须修满4门课，每行代表一门课。每行有2个数，第一个数是这门课程的先修课程课号（0表示该课不存在先修课程），第二个数是这门课程的学分（学分是不超过10的整数）。表2表示在此课程体系下，学生选择课号为：2、6、7、3四门课程得到的学分最多，所得到的学分为13。
上面的需求描述中，我们是给定某一课程体系情况下，指定学生毕业所需修读的课程数，求在此约束下的最多学分选课方案。
【基本要求】
从课程体系文本文件中读取课程信息，生成该课程体系森林，该森林采用二叉链表作为存储结构。
程序能够先序、中序、后序遍历该二叉树，以便验证所生成的二叉树表示的正确性。
指定一个课程数目，生成对应于该课程数目的“最大学分和”及相应选课方案（* 选做内容）。
一、【概要设计】
（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）
本抽象数据类型CourseBinTree是继承于二叉树类的，并使用类型CourseInfo作为二叉树节点的类型。关于二叉树类型的描述请参看《二叉树类型设计说明》。对于本次实验中的“最优求解问题”，我们小组设计了三种方案，并实现了其中两种，下面以方案I进行描述（关于方案II和方案III在四、【实验总结】一项中给予简要说明）。
①节点抽象数据类型的描述：
class CourseInfo
{
public:
// 缺省的构造器，初始化该节点数据
CourseInfo(void);
// 带参数的构造器，根据参数初始化节点数据
CourseInfo(unsigned int courseSerial, // 课程序号
unsigned int courseScore, // 课程学分值
unsigned int precedenceCourse); // 先修课序号
unsigned int m_courseSerial; // 课程序号
unsigned int m_courseScore; // 课程学分值
unsigned int m_precedenceCourse; // 该课程的先修课程序号
unsigned int m_subTreeNodeNum; // 子树节点个数
unsigned int m_leftSubTreeScoreSum; // 左子树学分总和
unsigned int m_rightSubTreeScoreSum; // 右子树学分总和
unsigned int m_maxSum[20]; // 在该节点处可以取得的最大学分和域
};
②课程二叉树抽象数据类型的描述
class CourseBinTree : public BinaryTree<CourseInfo>
{
public: // 用户接口
// 缺少的构造器，初始化相关数据
CourseBinTree(void);
// 从存储课程信息的文本文件中读取信息
void LoadInfo(std::string fileName);
// 显示所有课程信息
void DisplayAll(void);
// 生成课程二叉树
void GenerateCourseBinTree(void);
// 为计算该选课数下可获得的最大学分和，输入一个确定的选课数
void InputElectiveNumber(void);
// 根据用户输入的选课数计算可获得的最大学分和
void GetMaxCredit(void);
// 根据用户输入的选课数显示最大学分选课方案
void ShowMaxCreditSolution(void);
// 先序遍历该课程树
void PreOrderTraverse(void) const;
// 中序遍历该课程树
void InOrderTraverse(void) const;
// 后序遍历该课程树
void PostOrderTraverse(void) const;
// 按层遍历该课程树
void LevelOrderTraverse(void) const;
protected: // 保护的函数
// 从给定的节点开始先序遍历该节点的子树
void PreOrder(BinaryTreeNode<CourseInfo> *root) const;
// 从给定的节点开始中序遍历该节点的子树
void InOrder(BinaryTreeNode<CourseInfo> *root) const;
// 从给定的节点开始后序遍历该节点的子树
void PostOrder(BinaryTreeNode<CourseInfo> *root) const;
// 从给定的节点开始按层遍历该节点的子树
void LevelOrder(BinaryTreeNode<CourseInfo> *root) const;
private: // 私有的数据或函数
// 生成课程树的根节点
void GenerateRoot(void);
// 生成课程树的非根节点
void GenerateNode(BinaryTreeNode<CourseInfo> *p);
// 显示一门课程的信息
inline void DisplayOne(const list<CourseInfo>::iterator &i);
// 求给定节点的最大学分
void MaxScoreSum(BinaryTreeNode<CourseInfo> *root,
unsigned int m);
// 显示给定节点的最大学分选课方案
void DisplayOptionalPlan(BinaryTreeNode<CourseInfo> *root,
unsigned int m);
unsigned int m_electiveNo; // 保存用户输入的选课数
unsigned int m_maxCredit; // 保存最大学分和
std::list<CourseInfo> m_courseSList; // 保存课程信息
// 课程信息的备份，m_courseSList的一个复本
std::list<CourseInfo> m_bakCSList;
};
③主程序模块与抽象类型接口的调用关系描述
int main(void)
{
CourseBinTree myCourse; // 创建一个课程二叉树对象
// 读取当前目录下的CourseHerarchy.txt文件
myCourse.LoadInfo(“CourseHierarchy.txt”);
myCourse.DisplayAll(); //