13 数构上机实验题目第二次上机.pdf

第1页：第二次上机验证试验（必作题）封面

第二次上机验证试验（必作题）：题目1：二叉树相关算法的实验验证[实验目的]验证二叉树的链接存储结构及其上的基本操作。[实验内容及要求]1、定义链接存储的二叉树类。2、实验验证如下算法的正确性、各种功能及指标：1创建一棵二叉树，并对其初始化；2先根、中根、后根遍历二叉树；3在二叉树中搜索给定结点的父结点；

4搜索二叉树中符合数据域条件的结点；5从二叉树中删除给定结点及其左右子树。3、为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式展现、存储计算结果。4、测试程序时，对所有输入变量取遍各种有代表性的值。5、为了增强程序的可读性，程序中要有适当的注释。题目2：线索二叉树相关算法的实验验证[实验目的]验证线索二叉树及其上的基本操作。

[实验内容及要求]1、定义线索二叉树类。2、实验验证如下算法的正确性、各种功能及指标：1创建一棵中根线索二叉树；2求线索二叉树在中根遍历顺序下的第一个和最后一个结点；3求任一结点在中根遍历顺序下的前驱和后继结点；4遍历线索二叉树；5插入操作：在线索二叉树T*中插入结点p，作为T*中某结点s的左子结点或右子结点；

6删除操作：删除一个结点的左孩子（若其左孩子存在），或删除一个结点的右孩子（若其右孩子存在）。设计实验（选作题）：题目：判别给定二叉树是否为完全二叉树。[实验目的]在掌握二叉树的链接存储及基本操作的基础上，设计解决问题的算法。

第2页：[实验内容

[实验内容及要求]设计算法CompleteTree判别给定二叉树t是否为完全二叉树；编制程序实现该函数，制定测试方案，并调试通过。1、实现链接存储的二叉树类。2、实现算法CompleteTree.3、为便于观察程序的运行结果，设计输出函数，该函数能在输出设备上以图形、表格或其它直观的形式展现程序的运行结果，并能存储程序的这些运行结果。

4、为程序制定测试方案。5、为方便程序测试，程序代码中应包括合适的调试语句。6、测试程序时，所有输入变量应遍取各种有代表性的值。7、为增强程序的可读性，对程序中较难理解的语句要有准确、清晰的注释。