数据结构与算法基础课程实验报告
实验2：树及其应用
姓名 黄虎杰 软件学院三楼机房 出勤、表现得分10% 操作结果得分50% 院系 软件学院 指导教师 实验时间 实验报告 得分40% 2014.10.21 实验总分 学号 任课教师 实验地点 实验课表现 实验目的： 1． 掌握树的链式存储方式及其操作实现（创建、遍历、查找等）。 2． 掌握二叉树用不同方法表示所对应的不同输入形式。 3． 掌握二叉树中各种重要性质在解决实际问题中的应用。 实验内容： 假设自上而下按层次，自左至右输入每个结点的一个三元组(N, P, L/R)。其中N 为本结点的元素，P 为其父结点，L 指示N 为P 的左孩子，R 指示N 为P的右孩子。试写一个建立二元树的左右链表示算法，并实现先根、中根、后根以及层序遍历算法。 实验过程中遇到的问题如何解决的？（10分）（着重从软件调试、质量保证、结果分析方面进行阐述） 得分： 问题1： 有关如何根据给定父节点序号得到父节点对应指针。 解决方法：因为编号是按层序由上到下由左到右的顺序依次编号，受层序遍历中利用队列的思想启发，利用与层序遍历差不多的算法改进，用一个int i 来计数，在遍历过程中每输出一个节点i++，当i与给定的父节点序号相等，返回此时应输出的节点指针，即是父节点地址。此种方法耗费时间较多，不过自然思路就是想到这种方法，所以没有做改进。此外，题目中给出按照层序输入，实际程序中即使不按照层序输入也可以，只要父节点存在并合理即可。 问题2： 对于输入不合法时的处理。 解决方法：用getchar（）做缓存，每次输入判断scnaf函数返回值是否为0，如果不合法，输出提醒，继续循环输入，知道合法为止。因为程序会有很多不合法操作，包括父节点输入不正确，整形输入成字符型，没有用逗号间隔，等等，所以需要在程序各处进行判断。此外，对于给定不合法的父节点造成的问题，一是父节点已经存在左右孩子节点，重复插入时，利用判断做出相应回应；二是父节点不存在，处理方法类似。 本次实验的体会（结论）（10分） 得分： 1.写程序之前一定要有个考虑全面的大体思路，如果边写边想的话会遗留许多隐患，调试的时候会很痛苦。 2.对于链表的运用过程中要格外注意指针，避免对内存瞎操作，养成让不用的指针指向NULL的好习惯。 3.更加理解了scanf函数。 4.更加了解了树的链式存储方式及其操作实现，用不同方法表示所对应的不同输入形式。 思考题：（20分） 思考题1：（10分） 得分： 思考题1：在二元树的表示中通常都有哪几种方法？其特点是什么？ （1） 左右链表示：即利用链表，每个节点存储左右两个子节点的地址。利用这种方法根据父节点实现lchild，rchild，data比较容易，但根据子节点寻找父节点和兄弟节点比较困难。 （2） 游标表示：与左右链表示类似，只不过把指向每个节点的指针用游标表示，数据按顺序存在数组里，并有个一struct数组来存储二叉树结构，lchild和rchild。特点与上面类似。 （3） 线索二叉树：在左右链表示的基础上使空链域指向别处。特点是使树连通性更强，通过末节点可以直接访问头结点，一定程度上形成了循环，易于访问。 （4） 完全二叉树可用数组表示，特点是只有完全二叉树可以，有限制。但访问非常容易，不会浪费时间。 思考题2：（5分） 得分： 思考题2：在树的表示中通常都有哪几种方法？其特点是什么？ （1）树的数组表示法 除根节点外，每个节点只有一个指向其父节点的链域，表示为struct node{ Int parent; char data; }.这种只有父链的表示方法对于求父节点及其祖先节点都很 方便 ，只需向上访问即可，但对于给定的节点n，想要求其子节点的信息相当困难， 也不能反映各个兄弟节点的顺序。 （2）树的邻接表示法 将每个节点的所有子节点形成一个线性表，可以用数组链表或游标，每个节点连接一 个链表，来存储其子节点，这种表示方法求一个节点的父节点比较困难，但求子节 点很容易。 （3）树的左右链表示法 在每个节点中只设置两个链域，令左链指向左儿子，右链指向紧挨着他的右兄弟。 这种表示方法很容易实现有较小的树来构造较大的树，且很容易实现除parent之外的 各种操作。 思考题2：（5分） 得分： 思考题3：我们讨论森林和二元树之间的转换，其目的是什么？ 讨论森林和二叉树之间的对应关系，把森林变换为二叉树，再利用之前已经熟悉的二叉树性质对森林操作会比较容易，比如遍历森林与二叉树中，对二叉树提出的算法，完全可以被森林所用而不需要改动。且对于森林的处理要比二叉树复杂得多，它的一个节点可以对应很多孩子节点且可以有多个根节点，而对二叉树处理就很容易，所以转换成二叉树后方便操作。 指导教师特殊评语： 指导教师签字： 日期：
