二叉树实验报告.doc

过程控制软件技术基础课程实验报告 实验项目：二叉树的建立和遍历 姓名： 戚风亮 学号： 1008180230 指导教师： 任登凤 1. 实验目的 通过自主设计实验，掌握过程控制软件的基础理论知识，本实验具体表现为二叉树的建立和遍历，为以后计算机控制的软件设计提供基础。提高逻辑思维方式，培养应用可视化编程工具开发计算机软件的能力。 2. 实验内容 本文主要介绍二叉树的建立和遍历。所使用的编程软件为matlab2010版本，主要使用其中的GUI功能，完成可视化界面操作。从更直接的角度感受二叉树的建立和遍历。 二叉树的建立和遍历包含两个方面：建立和遍历。其中建立包括输入二叉树的每一个结点的元素，以及二叉树每一个结点的随机存储地址。与此同时，更重要的是创建两个指针域：左指针域L和右指针域R，在本次实验中，采用产生随机数的方式生成随机存储地址，采用两个数组代表两个指针域。二叉树的遍历采用递归函数的方式，本实验中采用三个函数Front,Middle,Behind分别实现前序、中序以及后序的功能。 （1）界面的设计： 软件的设计界面见图1。 图1 软件的总体界面 界面中主要包括以下几个部分： a. 深度m的输入框：此输入框在输入某个数值后将决定二叉树的深度，值得注意的是：本次实验中的设计标准为4层，即最大为4层。当输入数值大于4时，将提示出错（见图2），并要求重新输入。 图2. 出错消息提醒框 同时，当输入层数小于4时，软件将自动消去最后的那几层结点。（见图3） 图3. 软件自动按要求生成二叉树层数 b. 二叉树结点元素输入框： 二叉树结点元素输入框用于输入每个结点的元素值，同时按照二叉树的规则，每一个根结点对应至少两个子结点，即如果根结点的值为空（没有值），则它的子结点输入框不得输入，即其enabled属性为false（背景色为灰色，见图3）。当根结点输入值后，子结点输入框即可输入（见图4）。 与此同时，由于matlab的GUI中，没有向VB中的line控件，所以必须用代码加以实现，在matlab中，函数annotation可以用来画箭头，具体如下： arr(1,1)=annotation(gcf,arrow,[0.5 0.35],[0.8 0.75]); 其中，后面的两组数据为坐标值，arr(1,1)表示第一排的第一个箭头，在matlab中的每个图象都对应一个句柄值，这样，所有箭头都对应各自的句柄值，进而形成一个所有箭头的数组，便于管理每一个图像。 图4. 根结点输入后子结点方可输入 c. 控制按钮：生成二叉树 生成二叉树的主要功能是，将没有输入值的结点以及箭头隐藏，同时为每一个结点分配随机的存储地址（见图5），进而形成左右指针域。 图5. 最终形成的二叉树 如图5所示，在每个结点的左边有一个数字，即代表该结点在内存中的随机地址。该数字由matlab内部函数randperm产生。如： data=randperm(5) 即产生1——5的5个随机数（各不相同），并赋值给数组data。 本次实验中，最关键的是左右指针域的建立，即左右数组的建立。为实现这个功能，创建函数[L,R,VV]=point。 其中L表示左指针域，R代表右指针域，VV代表值域。至此，二叉树已完全建立。 d. 重置按钮：将界面设置为初始状态 e. 退出按钮：退出系统 f. 前序按钮：生成二叉树的前序遍历。（中序按钮、后序按钮依次类推） 3. 软件总体结构、程序流程图 软件总体结构： （1）软件界面总体上有三个部分： 输入界面 二叉树总体结构 控制界面 二叉树最终形成 结果界面 二叉树遍历显示 （2）软件程序总体上有以下几个方面： a. 名为gouzao的函数：该函数输入参数为输入框的坐标（x,y），返回该输入框的特点。即只有该输入框存在值时，它对应的子结点输入框方可输入。这里所谓的存在值的相反面是“非空”，而并非“空字符串”。 b. 名为point的函数：该函数没有输入参数，但可以返回左指针域、右指针域以及值域。其调用格式为[L,R,VV]=point。 c. 名为Front、Middle、Behind的函数：这三个函数分别返回前序遍历、中序遍历、后序遍历的结果。 d. 名为Erchashu的函数：该函数为matlab的GUI中系统自动生成的m文件格式的函数。它是整个系统的中枢，整合了以上的所有函数。 程序流程图： 图6. 程序流程图 4. 实验中遇到的