大数据结构java实验四.doc

《大数据结构java实验四.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构（JAVA）》综合性、设计性实验成绩单开设时间：2012学年第一学期班级11信管4班学号1.52.83.94.05.41.梓明2.王悦3.薛泽展4.海龙5.余柏烨实验题目实验四树和二叉树的基本操作成绩教师签名《数据结构（JAVA）》实验报告实验题目：树和二叉树的基本操作指导教师：实验组长（+学号）：组员（+学号）：实验时间：组长签名：一、实验报告撰写提纲1、实验目的1．理解二叉树的定义、性质、存储结构等基本概念，掌握二叉树类的设计方法，以及遍历、插入、删除等二叉树操作的算法实现；掌握采用链式存储结构表达非线性结构的设计方法；掌握采用递归算法实现递

2、归数据结构基本操作的设计方法。2．熟悉树的定义、表示、存储结构和遍历，具备使用树各种操作的能力。2、实验容（1）在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。①输入叶子结点。②求二叉树中叶子结点个数。③将每个结点的左子树与右子树交换。④验证二叉树的性质3：n0=n2+1。⑤输出值大于k的结点。⑥已知先根和中根次序遍历序列构造二叉树。⑦以广义表表示构造二叉树。⑧判断两颗二叉树是否相等。⑨求结点所在的层次。⑩求一颗二叉树在后根次序遍历下第一个访问的结点。⑪复制一颗二叉树。⑫判断一颗二叉树是否为完全二叉树。⑬实现二叉树

3、后根次序遍历的非递归算法。（2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。①构造一颗三叉链表表示的二叉树。②返回指定结点的父母结点。③返回指定结点的所有祖先结点。④返回两结点最近的共同祖先结点。（3）在一颗中序线索二叉树中，实现以下操作。①调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树。②按后根次序遍历中序线索二叉树。③在构造二叉树时进行线索化。④插入、删除操作。3、实验步骤与结果（1）①审题：在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。①输入叶子结点。②求二叉树中叶子结点个数。

4、③将每个结点的左子树与右子树交换。④验证二叉树的性质3：n0=n2+1。⑤输出值大于k的结点。⑥已知先根和中根次序遍历序列构造二叉树。⑦以广义表表示构造二叉树。⑧判断两颗二叉树是否相等。⑨求结点所在的层次。⑩求一颗二叉树在后根次序遍历下第一个访问的结点。⑪复制一颗二叉树。⑫判断一颗二叉树是否为完全二叉树。⑬实现二叉树后根次序遍历的非递归算法。②编程：这道小题需要用到几个类，分别是结点类Node,树结点类BinaryNode，顺序栈LinkedStack,顺序队列LinkedQueue，然后编写BinaryTree类，逐一实现以上功能。验证类为yanzhen

5、g。③验证结果：图1图2图3图4图5图6图7图8图9图10图11图12图13（2）①审题：（2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。①构造一颗三叉链表表示的二叉树。②返回指定结点的父母结点。③返回指定结点的所有祖先结点。④返回两结点最近的共同祖先结点。②编程：编写结点类TriNode，然后编写TriBinaryNode类实现二叉树的各个功能和方法。验证类为yanzheng2.③验证结果：图14（3）①审题：（3）在一颗中序线索二叉树中，实现以下操作。①调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树。②按后根次序遍历中序

6、线索二叉树。③在构造二叉树时进行线索化。④插入、删除操作。②编程：编写结点类ThreadNode，然后编写中性线索二叉树ThreadTreee逐一实现各个功能。验证类为yanzheng3.③验证结果：图15图16图174、源码（1）BinaryTree类package实验4；publicclassBinaryTree{publicBinaryNoderoot;publicBinaryTree(){this.root=null;}publicvoidpreOrder(){System.out.print("先根次序遍历二叉树：");preOrde

7、r(root);System.out.println();}publicvoidpreOrder(BinaryNodep){if(p!=null){System.out.print(p.data.toString()+"");preOrder(p.left);preOrder(p.right);}}publicBinaryTree(Tprelist[]){this.root=create(prelist);}privateinti=0;publicBinaryNodecreate(Tprelist[]){BinaryNodep=null;

8、if(i