蔡少云数据结构实验报告-二叉树的基本操作.doc

《蔡少云数据结构实验报告-二叉树的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验报告学院：管理学院班级：13电商1班姓名：蔡少云学号：321300----2014年12月1日目录一、需求分析………………………………………问题描述…………………………………………基本要求…………………………………………实现说明…………………………………………二、设计目的………………………………………三、概要设计………………………………………基本框架图………………………………………设计想法…………………………………………四、详细设计………………………………………结点类……………………………………二叉树接口…………………………………………二

2、叉树类………………………………………测试类………………………………………五、测试结果………………………………………基本数据…………………………………………操作截图…………………………………………六、用户使用说明…………………………………七、心得体会………………………………………题目：二叉树的基本操作一、需求分析【问题描述】在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。1.二叉树的先根次序遍历2.输出以p结点为根的子树的所有叶子结点，先根次序遍历算法3.将每个结点的左子树与右子树交换4.由中根和后根次序遍历序

3、列构造二叉树5.二叉树深拷贝，复制一棵二叉树【基本要求】建立结点类，二叉树接口。实现二叉树的先根次序遍历，中根次序遍历和后根次序遍历。【实现说明】可以利用利用二叉树的先根次序遍历完成相应功能。二、设计目的1、达到熟悉掌握java和数据结构的基本知识和技能；2、能够利用所学的基本知识和技能，解决简单的面向对象的设计问题；3、把课本上的知识应用到实际生活中，达到学以致用的目的；4、复习学过的知识，思考新的问题；三、概要设计(1)基本框架图：结点类属性：data、left、right、构造函数方法：输出方法、判断是否叶子结点方法判断二叉树是否为空isEmp

4、ty()二叉树接口先根、中根、后根次序遍历二叉树遍历输出叶子结点lrTran();将每个结点的左子树与右子树交换leaf1()二叉树深拷贝，复制一棵二叉树抽象方法实现二叉树类(2)设计想法:1、建立结点类BinaryNode；2、建立二叉树接口BinaryTTree3、建立二叉树类，实现二叉树接口BinaryTree4、建立主类，创建二叉树，进行测试。四、详细设计1、结点类//结点类publicclassBinaryNode//二叉树的二叉链表结点类，泛型T指定结点的元素类型{publicTdata;//数据域，存储数据元素publ

5、icBinaryNodeleft,right;//链域，分别指向左、右孩子结点//构造结点，参数分别指定元素和左、右孩子结点publicBinaryNode(Tdata,BinaryNodeleft,BinaryNoderight){this.data=data;this.left=left;this.right=right;}publicBinaryNode(Tdata)//构造指定值的叶子结点{this(data,null,null);}publicBinaryNode(){this(null,null,null);}//可声明

6、以下方法publicStringtoString(){returnthis.data.toString();}publicbooleanequals(Objectobj)//比较两个结点值是否相等，覆盖Object类的equals(obj)方法{returnobj==this

7、

8、objinstanceofBinaryNode&&this.data.equals(((BinaryNode)obj).data);}publicbooleanisLeaf()//判断是否叶子结点{returnthis.left==null&&this.right==n

9、ull;}}2、二叉树接口：//二叉树接口publicinterfaceBinaryTTree//二叉树接口，二叉树抽象数据类型{booleanisEmpty();//判断二叉树是否空voidpreOrder();//先根次序遍历二叉树voidinOrder();//中根次序遍历二叉树voidpostOrder();//后根次序遍历二叉树voidlrTran();voidleaf1();BinaryNodecopy(BinaryNodep);}3、二叉树类：//二叉树类，实现BinaryTTree接口，泛型T指定结点的元素类型

10、publicclassBinaryTreeimplementsBinaryTTree{publi