数据结构java实验四.doc

《数据结构（JAVA）》综合性、设计性实验成绩单 开设时间：2012学年第一学期 班级 11信管4班 学号 1.201130560415 2.201130560418 3.201130560419 4.201130560420 5.201130560424 姓名 1.刘梓明 2.王悦 3.薛泽展 4.杨海龙 5.余柏烨 实验题目 实验四 树和二叉树的基本操作 成绩 教师签名  《数据结构（JAVA）》 实 验 报 告 实验题目： 树和二叉树的基本操作 指导教师： 实验组长（姓名+学号）： 组员（姓名+学号）： 实验时间： 组长签名： 一、实验报告提纲? 复制一颗二叉树。 ? 判断一颗二叉树是否为完全二叉树。 ? 实现二叉树后根次序遍历的非递归算法。 （2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。 ① 构造一颗三叉链表表示的二叉树。 ② 返回指定结点的父母结点。 ③ 返回指定结点的所有祖先结点。 ④ 返回两结点最近的共同祖先结点。 （3）在一颗中序线索二叉树中，实现以下操作。 ① 调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树 。 ② 按后根次序遍历中序线索二叉树。 ③ 在构造二叉树时进行线索化。 ④ 插入、删除操作。 3、实验步骤与结果 （1）①审题：在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。 ① 输入叶子结点。 ② 求二叉树中叶子结点个数。 ③ 将每个结点的左子树与右子树交换。 ④ 验证二叉树的性质3：n0=n2+1。 ⑤ 输出值大于k的结点。 ⑥ 已知先根和中根次序遍历序列构造二叉树。 ⑦ 以广义表表示构造二叉树。 ⑧ 判断两颗二叉树是否相等。 ⑨ 求结点所在的层次。 ⑩ 求一颗二叉树在后根次序遍历下第一个访问的结点。 ? 复制一颗二叉树。 ? 判断一颗二叉树是否为完全二叉树。 ? 实现二叉树后根次序遍历的非递归算法。 ②编程：这道小题需要用到几个类，分别是结点类Node,树结点类BinaryNode，顺序栈LinkedStack,顺序队列LinkedQueue，然后编写BinaryTree类，逐一实现以上功能。验证类为yanzheng。 ③验证结果： 图 1 图 2 图 3 图 4 图 5 图 6 图 7 图 8 图 9 图 10 图 11 图 12 图 13 （2）①审题：（2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。 ① 构造一颗三叉链表表示的二叉树。 ② 返回指定结点的父母结点。 ③ 返回指定结点的所有祖先结点。 ④ 返回两结点最近的共同祖先结点。 ②编程：编写结点类TriNode，然后编写TriBinaryNode类实现二叉树的各个功能和方法。验证类为yanzheng2. ③验证结果： 图 14 （3）①审题：（3）在一颗中序线索二叉树中，实现以下操作。 ① 调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树 。 ② 按后根次序遍历中序线索二叉树。 ③ 在构造二叉树时进行线索化。 ④ 插入、删除操作。 ②编程：编写结点类ThreadNode，然后编写中性线索二叉树ThreadTreee逐一实现各个功能。验证类为yanzheng3. ③验证结果： 图 15 图 16 图 17 4、源码 （1）BinaryTree类 package 实验4public class BinaryTreeT{ public BinaryNodeT root; public BinaryTree(){ this.root=null; } public void preOrder(){ System.out.print(先根次序遍历二叉树：); preOrder(root);