遍历算法及应用.doc

实验报告课程名称算法与数据结构姓名何劼专业计算机科学与技术部别指导教员日期年月日实验项目列表序号实验项目名称成绩01稀疏多项式02小型计算器03遍历算法及应用040506070809101**********总评成绩:教员签字:实验报告姓名:何劼学号:专业:计算机科学与技术部别:实验地点:实验时间:2012、4、17设备编号:同组人员:指导教员签字:成绩:教员评语:实验名称遍历算法及应用二、、实验内容和要求编写完成如下功能的程序。(中序加后序序列造树选做)(选)(选),并输出树宽(选)要求:,然后输出原树的三种遍历序列。,再输出新二叉树的三种遍历序列。。。。。,并输出树宽四、::Windows操作系统,VC++集成开发环境五、算法设计思想题目一—构造二叉树。为了使得程序能够更加具有通用性,设计者在构造二叉树时编写了三种造树方式,分别是先序扩充序列造树,先序加中序序列造树以及中序加后序造树。其中前两个程序已经在课上得到了实现。中序加后序造树,主要问题就是左右子树上下标界的确定,运用图示法能够较为形象准确的解决此问题。三种序列的输出这里不加赘述。题目二——删除树中1度结点。采用先序遍历递归。首先判断下一结点是否为1度结点,若为1度结点并且有右儿子,返回1;若为1度结点并且有左儿子,返回2;不为1度结点返回0。再根据返回值的情况进行勾连和结点的删除。题目三——求结点的父亲。采用后续遍历递归。设计者配合使用了类似于“红绿灯”的found标记值。若为0则还未发现结点;若为1则找到该结点返回上一层输出其父亲,并置found为2。题目四——输出从根到叶的一条最长路径。首先找到最长路径对应的叶子(先序),再求取叶子的祖先(后序)。运用order数组存储其祖先,最后从后到前输出。这样得到的路径是符合从根到叶的顺序的。题目五——计算叶子的数目。采用先序遍历递归。判断是否为叶子。若为叶节点num加1;反之递归判断其左儿子,右儿子。题目六——判断正则树。如果存在这样一个结点,它只有一个儿子,那么found标记值置1。当递归遍历完整棵树之后,found等于1则不为正则树;反之则为正则树。题目七——按层遍历树。运用了队的结构。初始时刻last指针boundary指针重合,first指针在两者之前1位。树根先入队,并访问它,first指针后移,与boundary指针重合,说明该层遍历完成,breadth记录该层宽度。然后其左儿子,右儿子入队,last指针移至队尾。接着访问下一结点……每当first与boundary重合则说明该层遍历完成。六、主要问题与解决方法构造二叉树时,主要是中序加后序造树的递归标界的确定。如上文所说,运用图示法比较形象准确的解决了问题。删除1度结点时,设计者一开始觉得问题较为简单,但是真正上手之后,发现还是有一定难度的,不仅需要判断采用哪种遍历方式,还需要考虑找到一度结点输出最长路径时,一开始递归输出叶子祖先的顺序是从叶子到根。后来运用一个数组,将顺序倒了过来。按层遍历树时,按照教员的提示,运用队结构和boundary指针的方式,实现了按层遍历。并且记录了树宽。这个思想值得学习。七、实验结果程序对题目要求的构造二叉树、删除树中1度结点、输出从根到叶的一条最长路径、求结点的父亲、计算叶子的数目和判断正则树的问题进行了解决。在构造二叉树的问题中加入了先序扩充序列造树和中序加后序造树。在最后还添加了教员课上要求的按层遍历树以及求树宽的代码。经测试,该程序是可以解决以上问题的。而对于整个程序,稍微不太满意的地方是对于1度结点的删除和求最长路径的函数部分。两者过于冗长,并且进行了函数的二次调用。对于前者,经过教员后期课上指导发现可以有更好的较为简单的解决方法(主要思想是运用引用型参数),而后者暂时还没有找到较好的方法能够只对树一次遍历就得到从根到叶的顺序输出。以下是程序运行的截图和部分程序运行示意图:八、体会、质疑、建议本次实验主要是对二叉树进行了一系列的操作,归根结底是二叉树的查找、插入、删除。通过实验我对三种操作有了更加深入的认识,也更加熟练的掌握了其具体应用。通过对于树这种非链式结构的结构类型各种操作,我也体会到了学以所用的道理。任何一种结构类型都是为了更加方便准确的对事物进