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

数据结构实验报告 学院： 管理学院 班级： 13电商1班 姓名： 蔡少云 学号： 321300- 2014年 12 月1 日目录一、需求分析 问题描述 基本要求 实现说明二、设计目的三、概要设计基本框架图设计想法四、详细设计 结点类 二叉树接口 二叉树类 测试类五、测试结果 基本数据 操作截图六、用户使用说明七、心得体会题目：二叉树的基本操作一、需求分析【问题描述】在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。1. 二叉树的先根次序遍历2. 输出以p结点为根的子树的所有叶子结点，先根次序遍历算法3. 将每个结点的左子树与右子树交换4. 由中根和后根次序遍历序列构造二叉树5. 二叉树深拷贝，复制一棵二叉树【基本要求】建立结点类，二叉树接口。实现二叉树的先根次序遍历，中根次序遍历和后根次序遍历。【实现说明】可以利用利用二叉树的先根次序遍历完成相应功能。二、设计目的1、达到熟悉掌握java和数据结构的基本知识和技能；2、能够利用所学的基本知识和技能，解决简单的面向对象的设计问题；3、把课本上的知识应用到实际生活中，达到学以致用的目的；4、复习学过的知识，思考新的问题；三、概要设计(1)基本框架图：结点类属性：data、left、right、构造函数方法：输出方法、判断是否叶子结点方法判断二叉树是否为空isEmpty()二叉树接口先根、中根、后根次序遍历二叉树遍历输出叶子结点lrTran();将每个结点的左子树与右子树交换leaf1()二叉树深拷贝，复制一棵二叉树抽象方法实现二叉树类 (2)设计想法:1、建立结点类BinaryNode；2、建立二叉树接口BinaryTTree3、建立二叉树类，实现二叉树接口BinaryTree4、建立主类，创建二叉树，进行测试。四、详细设计1、结点类/结点类public class BinaryNode /二叉树的二叉链表结点类，泛型T指定结点的元素类型 public T data; /数据域，存储数据元素 public BinaryNode left, right; /链域，分别指向左、右孩子结点 /构造结点，参数分别指定元素和左、右孩子结点 public BinaryNode(T data, BinaryNode left, BinaryNode right) this.data = data; this.left = left; this.right = right; public BinaryNode(T data) /构造指定值的叶子结点 this(data, null, null); public BinaryNode() this(null, null, null); /可声明以下方法 public String toString() return this.data.toString(); public boolean equals(Object obj) /比较两个结点值是否相等，覆盖Object类的equals(obj)方法 return obj=this | obj instanceof BinaryNode & this.data.equals(BinaryNode)obj).data); public boolean isLeaf() /判断是否叶子结点 return this.left=null & this.right=null; 2、二叉树接口：/二叉树接口public interface BinaryTTree /二叉树接口，二叉树抽象数据类型boolean isEmpty(); /判断二叉树是否空void preOrder(); /先根次序遍历二叉树void inOrder(); /中根次序遍历二叉树void postOrder(); /后根次序遍历二叉树 void lrTran(); void leaf1();BinaryNode copy(BinaryNode p); 3、二叉树类：/二叉树类，实现BinaryTTree接口，泛型T指定结点的元素类型public class BinaryTree implements BinaryTTree public BinaryNode root; /根结点，结点结构为二叉链表 public BinaryTree() /构造空二叉树 this.root=null; public boolean isEmpty() /判断二叉树是否空 return this.root=null; /* 1.先根次序遍历* public void preOrder() /先根次序遍历二叉树 System.out.print(先根次序遍历二叉树： ); preOrder(root); /调用先根次序遍历二叉树的递归方法 System.out.println(); public void preOrder(BinaryNode p) /先根次序遍历以p结点为根的子二叉树，递归方法 if (p!=null) /若二叉树不空 System.out.print(p.data.toString()+ ); /访问当前结点 preOrder(p.left); /按先根次序遍历当前结点的左子树，递归调用 preOrder(p.right); /按先根次序遍历当前结点的右子树，递归调用 public String toString() /返回先根次序遍历二叉树所有结点的描述字符串 return toString(root); private String toString(BinaryNode p) /返回先根次序遍历以p为根的子树描述字符串，递归算法 if (p=null) return ; return p.data.toString()+ + toString(p.left) + toString(p.right);/递归调用 /2.输出以p结点为根的子树的所有叶子结点，先根次序遍历算法 public void leaf1() /遍历输出叶子结点 leaf1(root); private void leaf1(BinaryNode p) int sum = 0; if(p!=null) if (p.left=null & p.right=null) /p.isLeaf() System.out.print(p.data.toString()+ ); leaf1(p.left); /递归 leaf1(p.right); /*3.将每个结点的左子树与右子树交换* public void lrTran() lrTran(root); public void lrTran(BinaryNode p) if (!(p.left=null&p.right=null) BinaryNode temp = p.left; p.left = p.right; p.right = temp; /*4.由中根和后根次序遍历序列构造二叉树* /* 中根次序遍历* public void inOrder() /中根次序遍历二叉树 System.out.print(中根次序遍历二叉树： ); inOrder(root); System.out.println(); public void inOrder(BinaryNode p) /中根次序遍历以p结点为根的子二叉树，递归方法 if (p!=null) inOrder(p.left); /中根次序遍历左子树，递归调用 System.out.print(p.data.toString()+ ); inOrder(p.right); /中根次序遍历右子树，递归调用 /* 后根次序遍历* public void postOrder() /后根次序遍历二叉树 System.out.print(后根次序遍历二叉树： ); postOrder(root); System.out.println(); public void postOrder(BinaryNode p) /后根次序遍历以p结点为根的子二叉树，递归方法 if (p!=null) postOrder(p.left); postOrder(p.right); System.out.print(p.data.toString()+ ); /*5.二叉树深拷贝，复制一棵二叉树* public BinaryNode copy(BinaryNode p) if (p=null) return null; BinaryNode q = new BinaryNode(p.data); q.left = copy(p.left); /复制左子树，递归调用 q.right = copy(p.right); /复制右子树，递归调用 return q; /返回建立子树的根结点 4.测试类：/主类public class BinaryTree_make public static BinaryTree make() /构造给定的一棵二叉树 /* A / B C / / D E F / G H */ BinaryTree bitree=new BinaryTree(); /创建空二叉树 BinaryNode child_f, child_d, child_b, child_c; child_d = new BinaryNode(D, null, new BinaryNode(G); child_b = new BinaryNode(B, child_d, null); child_f = new BinaryNode(F, new BinaryNode(H), null); child_c = new BinaryNode(C, new BinaryNode(E), child_f); bitree.root = new BinaryNode(A, child_b, child_c); return bitree; public static void main(String args) BinaryTree bitree = make(); bitree.leaf1(); System.out.println(n+先根次序遍历为：); bitree.preOrder(bitree.root); bitree.lrTran(); System.out.println(n+左右子树交换后的先根次序遍历为：); bitree.preOrder(bitree.root); System.out.println(n+中根次序遍历为：); bitree.inOrder(bitree.root); System.out.println(n+后根次序遍历为：); bitree.postOrder(bitree.root)