资源预览内容
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
第9页 / 共24页
第10页 / 共24页
亲,该文档总共24页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构(JAVA)综合性、设计性实验成绩单开设时间:2012 学年第一学期班级11信管4班学号1.2011305604152.2011305604183.2011305604194.2011305604205.201130560424姓名1.刘梓明2王悦3薛泽展4.杨海龙5余柏烨实验题目实验四 树和二叉树的基本操作成绩教师签名数据结构(J AVA)实验报告实验题目:树和二叉树的基本操作指导教师:实验组长(姓名+学号):组员(姓名+学号):实验时间:组长签名:一、实验报告撰写提纲1、实验目的1 理解二叉树的定义、性质、存储结构等基本概念,掌握二叉树类的设计方法,以及 遍历、插入、删除等二叉树操作的算法实现;掌握采用链式存储结构表达非线性结 构的设计方法;掌握采用递归算法实现递归数据结构基本操作的设计方法。2熟悉树的定义、表示、存储结构和遍历,具备使用树各种操作的能力。2、实验内容(1)在一棵二叉链表表示的二叉树中,实现以下操作,并说明采用哪种遍历算法,其他遍 历算法是否可行。 输入叶子结点。 求二叉树中叶子结点个数。 将每个结点的左子树与右子树交换。 验证二叉树的性质 3 : n0=n2+1。 输出值大于 k 的结点。 已知先根和中根次序遍历序列构造二叉树。 以广义表表示构造二叉树。 判断两颗二叉树是否相等。 求结点所在的层次。 求一颗二叉树在后根次序遍历下第一个访问的结点。 复制一颗二叉树。 判断一颗二叉树是否为完全二叉树。 实现二叉树后根次序遍历的非递归算法。(2)声明三叉链表表示的二叉树类,实现二叉树的基本操作以及以下操作。 构造一颗三叉链表表示的二叉树。 返回指定结点的父母结点。 返回指定结点的所有祖先结点。 返回两结点最近的共同祖先结点。(3)在一颗中序线索二叉树中,实现以下操作。 调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树 。 按后根次序遍历中序线索二叉树。 在构造二叉树时进行线索化。 插入、删除操作。3、实验步骤与结果(1)审题:在一棵二叉链表表示的二叉树中,实现以下操作,并说明采用哪种遍历算法, 其他遍历算法是否可行。 输入叶子结点。 求二叉树中叶子结点个数。 将每个结点的左子树与右子树交换。 验证二叉树的性质 3: n0=n2+1。 输出值大于 k 的结点。 已知先根和中根次序遍历序列构造二叉树。 以广义表表示构造二叉树。 判断两颗二叉树是否相等。 求结点所在的层次。 求一颗二叉树在后根次序遍历下第一个访问的结点。复制一颗二叉树。判断一颗二叉树是否为完全二叉树。实现二叉树后根次序遍历的非递归算法。 编程:这道小题需要用到几个类,分别是结点类Node,树结点类BinaryNode,顺序栈 LinkedStack,顺序队列LinkedQueue,然后编写BinaryTree类,逐一实现以上功能。验证 类为 yanzheng。 验证结果:先根次序遍历二殳树:忆图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:-1C:A图13(2)审题:(2)声明三叉链表表示的二叉树类,实现二叉树的基本操作以及以下操作。 构造一颗三叉链表表示的二叉树。 返回指定结点的父母结点。 返回指定结点的所有祖先结点。 返回两结点最近的共同祖先结点。 编程:编写结点类TriNode,然后编写TriBinaryNode类实现二叉树的各个功能和方法。 验证类为yanzheng2. 验证结果:先根次序遍历二B D G C E F HG的父母结点是:DG的所有祖先结点为;D 3 AD结点与?1结点最近的共同祖先结点是:A图14(3)审题:(3)在一颗中序线索二叉树中,实现以下操作。 调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树。 按后根次序遍历中序线索二叉树。 在构造二叉树时进行线索化。 插入、删除操作。 编程:编写结点类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 类 package 实验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);public 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 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=null)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);public 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(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.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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号