《数据结构java实验四》由会员分享，可在线阅读，更多相关《数据结构java实验四（24页珍藏版）》请在金锄头文库上搜索。
1、数据结构（JAVA）综合性、设计性实验成绩单开设时间：2012 学年第一学期班级11信管4班学号1.2011305604152.2011305604183.2011305604194.2011305604205.201130560424姓名1.刘梓明2王悦3薛泽展4.杨海龙5余柏烨实验题目实验四 树和二叉树的基本操作成绩教师签名数据结构（J AVA）实验报告实验题目：树和二叉树的基本操作指导教师：实验组长（姓名+学号）：组员（姓名+学号）：实验时间：组长签名：一、实验报告撰写提纲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类，逐一实现以上功能。验证 类为 yanzheng。 验
5、证结果：先根次序遍历二殳树:忆图1叶子节点个埶話图2交换节点后的先根次序遍历二貝树:A C H I F Z B E h M图3叶子结点：4=卫度结点：34二即r.0=ri2-L .图4犬于D的结点有；I F E E M图5先根次序遍历二龙树:区图6广义恚表示対；眞 CB （DMFnull） , E）匚Fr H （nail, IJ J图7bitr eee 亡 2 相等图8亡结乏所在的层次是；3图9后根坎帛逅历下第一个祐问的结点是:M图10先根次序遍历二叉樹也DMErFZHI图11bitree是否药完全二更树:Emlmm图12 -_ I I L 一 _ U- 后根炭序遍历非递归）：MDEZFI：-
6、1C：A图13（2）审题：（2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。 构造一颗三叉链表表示的二叉树。 返回指定结点的父母结点。 返回指定结点的所有祖先结点。 返回两结点最近的共同祖先结点。 编程：编写结点类TriNode，然后编写TriBinaryNode类实现二叉树的各个功能和方法。 验证类为yanzheng2. 验证结果：先根次序遍历二B D G C E F HG的父母结点是：DG的所有祖先结点为；D 3 AD结点与?1结点最近的共同祖先结点是：A图14（3）审题：（3）在一颗中序线索二叉树中，实现以下操作。 调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二
7、叉树。 按后根次序遍历中序线索二叉树。 在构造二叉树时进行线索化。 插入、删除操作。 编程：编写结点类ThreadNode，然后编写中性线索二叉树ThreadTreee逐一实现各个功 能。验证类为yanzheng3. 验证结果：中根次序（反序）遍历中序线索二買树：XCHFAES3D图15后根次席（反序）遍厉中席线索二爰树：ACXFHBEGD图16中根衣序（反序）遍历中序线索二叉树：C H F A E G M B M D中根次序（良帛）遍历中序缩索二盘树；o F A E G H B H D中根次序（反序）遍历中序线索二更树：FAESMMD图174、源码（1）BinaryTree 类 packag
8、e 实验4；public class BinaryTreepublic BinaryNode root;public BinaryTree（）this.root=null;public void preOrder()System. out.print(先根次序遍历二叉树：)； preOrder(root);System. out.println();public void preOrder(BinaryNode p) if(p!=null)System.out.print(p.data.toString()+ ); preOrder(p.left);preOrder(p.right);publ
9、ic BinaryTree(T prelist) this.root=create(prelist);private int i=0;public BinaryNode create(T prelist) BinaryNode p=null;if(iprelist.length)T elem=prelisti;i+;if(elem!=null)p=new BinaryNode(elem);p.left=create(prelist); p.right=create(prelist); return p;public BinaryNode search(T key) /输入叶子结点。return
10、 search(root,key);public BinaryNode search(BinaryNode p,T key) if(p=null|key=null)return null;if(p .data.equals(key) return p;BinaryNode find=search(p.left,key); if(find=null)find=search(p.right,key);return find;public BinaryNode insertChild(BinaryNode p,T x)if(p=null|x=null) return null;if(p.left=n
11、ull)p.left=new BinaryNode(x,null,null); return p.left;else p.right=new BinaryNode(x,null,null); return p;public int yecount()/求二叉树中叶子结点个数。return yecount(root);public int yecount(BinaryNode p) if(p=null)return 0;if(p!=null &p.left=null&p.right=null)return 1;return yecount(p.left)+yecount(p.right);pub
12、lic BinaryNode JHjiedian ( ) / 将每个结点的左子树与右子树交换 return JHjiedian(root);public BinaryNode JHjiedian(BinaryNode p) BinaryNode q=null;q=p.left; p.left=p.right;p.right=q;if(p.left!=null)JHjiedian(p.left);if(p.right!=null)JHjiedian(p.right);return p;public int twoyezi()/验证二叉树的性质3： n0=n2 + 1。return twoyezi
13、(root);public int twoyezi(BinaryNode p)int i,j; if(p=null) return 0;elsei=twoyezi(p.left);j=twoyezi(p.right);if(p.left!=null&p.right!=null)return i+j+1;elsereturn (i+j);public void DaJieDina(T value)/ 输出值大于k的结点。System.out. print(大于+value+的结点有：);BinaryNode p = this.root;DaJieDina(p, value);System.out
14、.println();public void DaJieDina(BinaryNode p, T value)if (p != null )if (String) p.data).compareTo(String)value) 0) System.out.print (p.data.toString ( ) + );DaJieDina(p.left, value);DaJieDina(p.right, value);public BinaryTree(T prelis t ,T inlis t )/已知先根和中根次序遍历序列构造二叉树。this.root=create(prelist,inlist,0,0,prelist.length);private BinaryNodecreate(Tprelist,T
