数据结构java实验四.docx
- 文档编号:6615829
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:27
- 大小:51.78KB
数据结构java实验四.docx
《数据结构java实验四.docx》由会员分享,可在线阅读,更多相关《数据结构java实验四.docx(27页珍藏版)》请在冰点文库上搜索。
数据结构java实验四
《数据结构(JAVA)》综合性、设计性实验成绩单
开设时间:
2012学年第一学期
班级11信管4班学号1.201130560415姓名1.刘梓明
2.2011305604182.王悦
3.2011305604193.薛泽展
4.2011305604204.杨海龙5.201130560424
5.余柏烨
实实验四树和二叉树的基本操作
验题目
成绩教师签名
《数据结构(JAVA)》
实验报告
实验题目:
树和二叉树的基本操作
指导教师:
实验组长(姓名+学号):
组员(姓名+学号):
实验时间:
组长签名:
1
一、实验报告撰写提纲
1、实验目的
1.理解二叉树的定义、性质、存储结构等基本概念,掌握二叉树类的设计方法,以及
遍历、插入、删除等二叉树操作的算法实现;掌握采用链式存储结构表达非线性结构的设计方法;掌握采用递归算法实现递归数据结构基本操作的设计方法。
2.熟悉树的定义、表示、存储结构和遍历,具备使用树各种操作的能力。
2、实验内容
(1)在一棵二叉链表表示的二叉树中,实现以下操作,并说明采用哪种遍历算法,其他遍历算法是否可行。
①输入叶子结点。
②求二叉树中叶子结点个数。
③将每个结点的左子树与右子树交换。
④验证二叉树的性质3:
n0=n2+1。
⑤输出值大于k的结点。
⑥已知先根和中根次序遍历序列构造二叉树。
⑦以广义表表示构造二叉树。
⑧判断两颗二叉树是否相等。
⑨求结点所在的层次。
⑩求一颗二叉树在后根次序遍历下第一个访问的结点。
⑪复制一颗二叉树。
⑫判断一颗二叉树是否为完全二叉树。
⑬实现二叉树后根次序遍历的非递归算法。
(2)声明三叉链表表示的二叉树类,实现二叉树的基本操作以及以下操作。
①构造一颗三叉链表表示的二叉树。
②返回指定结点的父母结点。
③返回指定结点的所有祖先结点。
④返回两结点最近的共同祖先结点。
(3)在一颗中序线索二叉树中,实现以下操作。
①调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树。
②按后根次序遍历中序线索二叉树。
③在构造二叉树时进行线索化。
④插入、删除操作。
3、实验步骤与结果
(1)①审题:
在一棵二叉链表表示的二叉树中,实现以下操作,并说明采用哪种遍历算法,其他遍历算法是否可行。
①输入叶子结点。
②求二叉树中叶子结点个数。
③将每个结点的左子树与右子树交换。
④验证二叉树的性质3:
n0=n2+1。
⑤输出值大于k的结点。
⑥已知先根和中根次序遍历序列构造二叉树。
2
⑦以广义表表示构造二叉树。
⑧判断两颗二叉树是否相等。
⑨求结点所在的层次。
⑩求一颗二叉树在后根次序遍历下第一个访问的结点。
⑪复制一颗二叉树。
⑫判断一颗二叉树是否为完全二叉树。
⑬实现二叉树后根次序遍历的非递归算法。
②编程:
这道小题需要用到几个类,分别是结点类Node,树结点类BinaryNode,顺序栈LinkedStack,顺序队列LinkedQueue,然后编写BinaryTree类,逐一实现以上功能。
验证类为yanzheng。
③验证结果:
图1
图2
图3
图4
图5
图6
图7
图8
图9
图10
图11
图12
图133
(2)①审题:
(2)声明三叉链表表示的二叉树类,实现二叉树的基本操作以及以下操作。
①构造一颗三叉链表表示的二叉树。
②返回指定结点的父母结点。
③返回指定结点的所有祖先结点。
④返回两结点最近的共同祖先结点。
②编程:
编写结点类TriNode,然后编写TriBinaryNode类实现二叉树的各个功能和方法。
验证类为yanzheng2.
③验证结果:
图14
(3)①审题:
(3)在一颗中序线索二叉树中,实现以下操作。
①调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树。
②按后根次序遍历中序线索二叉树。
③在构造二叉树时进行线索化。
④插入、删除操作。
②编程:
编写结点类ThreadNode,然后编写中性线索二叉树ThreadTreee逐一实现各个功能。
验证类为yanzheng3.③验证结果:
图15
图16
图17
4、源码
(1)BinaryTree类
package实验4;
publicclassBinaryTree
}publicvoidpreOrder(){System.out.print("先根次序遍历二叉树:
");
preOrder(root);System.out.println();}
publicvoidpreOrder(BinaryNode
if(p!
=null){
System.out.print(p.data.toString()+"");preOrder(p.left);preOrder(p.right);}}
publicBinaryTree(Tprelist[]){
this.root=create(prelist);
}
privateinti=0;
publicBinaryNode if(elem! =null){p=newBinaryNode } } returnp; } publicBinaryNode returnsearch(root,key);} publicBinaryNode if(p.data.equals(key))returnp; BinaryNode find=search(p.right,key);returnfind;} publicBinaryNode 5 if(p==null||x==null)returnnull; if(p.left==null){ p.left=newBinaryNode elsep.right=newBinaryNode } publicintyecount(){//②求二叉树中叶子结点个数。 returnyecount(root);} publicintyecount(BinaryNode =null&&p.left==null&&p.right==null)return1; returnyecount(p.left)+yecount(p.right); } publicBinaryNode returnJHjiedian(root);} publicBinaryNode if(p.left! =null){JHjiedian(p.left);} if(p.right! =null){JHjiedian(p.right);} returnp; } publicinttwoyezi(){//④ 验证二叉树的性质3: n0=n2+1。 returntwoyezi(root);} publicinttwoyezi(BinaryNode else{ i=twoyezi(p.left);6 j=twoyezi(p.right); if(p.left! =null&&p.right! =null)returni+j+1;else return(i+j);} } publicvoidDaJieDina(Tvalue){//⑤输出值大于k的结点。 System.out.print("大于"+value+"的结点有: "); BinaryNode publicvoidDaJieDina(BinaryNode =null){if(((String)p.data).compareTo((String)value)>0)System.out.print(p.data.toString()+"");DaJieDina(p.left,value);DaJieDina(p.right,value); } } publicBinaryTree(Tprelist[],Tinlist[]){//⑥已知先根和中根次序遍 历序列构造二叉树。 this.root=create(prelist,inlist,0,0,prelist.length);} private BinaryNode preStart,int inStart,intn){ if(n<=0)returnnull; Telem=prelist[preStart]; BinaryNode while(i elem.equals(inlist[inStart+i]))i++; p.left=create(prelist,inlist,preStart+1,inStart,i); p.right=create(prelist,inlist,preStart+i+1,inStart+i+1,n-1-i);returnp; } publicStringtoGenListString(){//⑦以广义表表示构造二叉树。 return"广义表表示为: "+toGenListString(root)+"\n";} publicStringtoGenListString(BinaryNode returnnull; Stringstr=p.data.toString();if(p.left! =null||p.right! =null)str+="("+toGenListString(p.left)+","+toGenListString(p.right)+")"; returnstr; } publicbooleancompareTree(BinaryNode 是否相等。 returncompareNode(root,root2);} publicbooleancompareNode(BinaryNode elseif(p==null||q==null){returnfalse;}else{ if(p.data! =q.data){returnfalse; } booleancleft=compareNode(p.left,q.left);booleancright=compareNode(p.right,q.right);if(cleft&&cright){returntrue;} elsereturnfalse;}} publicintgetLevel(Tx){//⑨求结点所在的层次。 returngetLevel(root,1,x);//令根结点的层次为1} privateintgetLevel(BinaryNode if(p==null)//空树或查找不成功 return-1; if(p.data.equals(x)) returni;//查找成功 intlevel=getLevel(p.left,i+1,x);//在左子树查找 if(level==-1) level=getLevel(p.right,i+1,x);//继续在右子树中查找 returnlevel;}8 publicBinaryNode 第一个访问的结点. BinaryNode =null)p=p.left;if(p.right! =null) {p=p.right;continue;}break; } returnp; } publicBinaryTree(BinaryTree this.root=copy(bitree.root);} privateBinaryNode 返回新建子二叉树的根结点 if(p==null)returnnull; BinaryNode q.left=copy(p.left);//复制左子树,递归调用 q.right=copy(p.right);//复制右子树,递归调用 returnq;//返回建立子树的根结点 } booleanisCompleteBinaryTree(){//12判断一颗二叉树是否为完全二叉 树。 if(this.root==null)returntrue; LinkedQueue LinkedQueue que.enqueue(root);//根结点入队 BinaryNode que.isEmpty()){ p=que.dequeue();//p指向出队结点 if(p.left! =null)//p的非空孩子结点入队 { que.enqueue(p.left);if(p.right! =null)que.enqueue(p.right); else break;//发现空子树,须检测队列 9 中是否都是叶子结点 }else if(p.right! =null) returnfalse;//p的左子树空而右子树不空,确定不是 else break;//p是叶子,须检测队列中 是否都是叶子结点 }while(! que.isEmpty())//检测队列中是否都是叶子结点 {p=que.dequeue(); if(p.left! =null||p.right! =null)//发现非叶子,确定 不是 returnfalse;} returntrue;} publicvoidpostOrderTraverse(){//13实现二叉树后根次序遍历的非递归算法。 System.out.print("后根次序遍历(非递归): ");LinkedStack BinaryNode while(p! =null||! stack.isEmpty())//p非空或栈非 空时 if(p! =null){ stack.push(p);//p结点入栈 p=p.left;//进入左子树 } else//p为空且栈非空时 { p=stack.get();//从左子树返回p结点,p结点不出栈 if(p.right! =null&&p.right! =front)//p有右孩子, 且右孩子没被访问过 {p=p.right;//进入右子树 stack.push(p); p=p.left;//向左走 }else10 { p=stack.pop();//从右子树返回p 结点,p结点出栈 System.out.print(p.data+"");front=p;//front是p在后根遍历次序下的前驱结点 p=null;}} System.out.println();} } BinaryNode类 package实验4; publicclassBinaryNode publicBinaryNode publicBinaryNode(Tdata,BinaryNode publicBinaryNode(Tdata){this(data,null,null);} publicBinaryNode(){this(null,null,null);}} LinkedStack类 package实验4; publicclassLinkedStack } publicbooleanisEmpty(){returnthis.top==null;} publicvoidpush(Tx){if(x! =null)this.top=newNode(x,this.top);} publicTpop(){11 if(this.top==null)returnnull;Ttemp=this.top.data;this.top=this.top.next;returntemp; } publicTget(){returnthis.top==null? null: this.top.data; } } LinkedQueue类 package实验4; publicclassLinkedQueue } publicbooleanisEmpty(){returnthis.front==null&&this.rear==null;} publicvoidenqueue(Tx){if(x==null)return; Node this.rear.next=q;this.rear=q; } publicTdequeue(){if(isEmpty())returnnull; Ttemp=this.front.data;this.front=this.front.next;if(this.front==null)this.rear=null;returntemp;} } Node类 package实验4; publicclassNode publicNode publicNode(Tdata,Node } publicNode(TData){this(Data,null);} publicNode(){this(null,null);}} 验证代码 package实验4; publicclassyanZheng{publicstaticvoidmain(String[]args){Stringprelist[]={"A","B","D","M","E","C","F","Z","H","I"};Stringinlist[]={"M","D","B","E","A","Z","F","C","H","I"};B
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 java 实验