数据结构java实验四.docx
- 文档编号:18578764
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:36
- 大小:51.89KB
数据结构java实验四.docx
《数据结构java实验四.docx》由会员分享,可在线阅读,更多相关《数据结构java实验四.docx(36页珍藏版)》请在冰点文库上搜索。
数据结构java实验四
《数据结构(JAVA)》综合性、设计性实验成绩单
开设时间:
2012学年第一学期
班级
11信管4班
学号
1.201130560415
2.201130560418
3.201130560419
4.201130560420
5.201130560424
姓名
1.刘梓明
2.王悦
3.薛泽展
4.杨海龙
5.余柏烨
实验题目
实验四树和二叉树的基本操作
成绩
教师签名
《数据结构(JAVA)》
实验报告
实验题目:
树和二叉树的基本操作
指导教师:
实验组长(姓名+学号):
组员(姓名+学号):
实验时间:
组长签名:
一、实验报告撰写提纲
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
图3
图4
图5
图6
图7
图8
图9
图10
图11
图12
图13
(2)①审题:
(2)声明三叉链表表示的二叉树类,实现二叉树的基本操作以及以下操作。
①构造一颗三叉链表表示的二叉树。
②返回指定结点的父母结点。
③返回指定结点的所有祖先结点。
④返回两结点最近的共同祖先结点。
②编程:
编写结点类TriNode,然后编写TriBinaryNode类实现二叉树的各个功能和方法。
验证类为yanzheng2.
③验证结果:
图14
(3)①审题:
(3)在一颗中序线索二叉树中,实现以下操作。
①调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树。
②按后根次序遍历中序线索二叉树。
③在构造二叉树时进行线索化。
④插入、删除操作。
②编程:
编写结点类ThreadNode,然后编写中性线索二叉树ThreadTreee逐一实现各个功能。
验证类为yanzheng3.
③验证结果:
图15
图16
图17
4、源码
(1)BinaryTree类
package实验4;
publicclassBinaryTree
publicBinaryNode
publicBinaryTree(){
this.root=null;
}
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
BinaryNode
if(i Telem=prelist[i]; i++; if(elem! =null){ p=newBinaryNode p.left=create(prelist); p.right=create(prelist); } } returnp; } publicBinaryNode returnsearch(root,key); } publicBinaryNode if(p==null||key==null) returnnull; if(p.data.equals(key)) returnp; BinaryNode if(find==null) find=search(p.right,key); returnfind; } publicBinaryNode if(p==null||x==null) returnnull; if(p.left==null){ p.left=newBinaryNode returnp.left; } elsep.right=newBinaryNode returnp; } publicintyecount(){//②求二叉树中叶子结点个数。 returnyecount(root); } publicintyecount(BinaryNode if(p==null) return0; if(p! =null&&p.left==null&&p.right==null) return1; returnyecount(p.left)+yecount(p.right); } publicBinaryNode returnJHjiedian(root); } publicBinaryNode BinaryNode q=p.left; p.left=p.right; p.right=q; if(p.left! =null){ JHjiedian(p.left); } if(p.right! =null){ JHjiedian(p.right); } returnp; } publicinttwoyezi(){//④验证二叉树的性质3: n0=n2+1。 returntwoyezi(root); } publicinttwoyezi(BinaryNode inti,j; if(p==null) return0; else{ i=twoyezi(p.left); 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 DaJieDina(p,value); System.out.println(); } publicvoidDaJieDina(BinaryNode 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); } } publicBinaryTree(Tprelist[],Tinlist[]){//⑥已知先根和中根次序遍历序列构造二叉树。 this.root=create(prelist,inlist,0,0,prelist.length); } privateBinaryNode if(n<=0) returnnull; Telem=prelist[preStart]; BinaryNode inti=0; 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 if(p==null) 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 if(p==null&&q==null) returntrue; 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; } else returnfalse; } } 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; } publicBinaryNode BinaryNode while(true){ while(p.left! =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 que.enqueue(root);//根结点入队 BinaryNode while(! que.isEmpty()) { p=que.dequeue();//p指向出队结点 if(p.left! =null)//p的非空孩子结点入队 { que.enqueue(p.left); if(p.right! =null) que.enqueue(p.right); elsebreak;//发现空子树,须检测队列中是否都是叶子结点 } else if(p.right! =null) returnfalse;//p的左子树空而右子树不空,确定不是 elsebreak;//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;//向左走 } else { p=stack.pop();//从右子树返回p结点,p结点出栈 System.out.print(p.data+""); front=p;//front是p在后根遍历次序下的前驱结点 p=null; } } System.out.println(); } } BinaryNode类 package实验4; publicclassBinaryNode publicTdata; publicBinaryNode publicBinaryNode(Tdata,BinaryNode this.data=data; this.left=left; this.right=right; } publicBinaryNode(Tdata){ this(data,null,null); } publicBinaryNode(){ this(null,null,null); } } LinkedStack类 package实验4; publicclassLinkedStack privateNode publicLinkedStack(){ this.top=null; } publicbooleanisEmpty(){ returnthis.top==null; } publicvoidpush(Tx){ if(x! =null) this.top=newNode(x,this.top); } publicTpop(){ 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 privateNode publicLinkedQueue(){ this.front=this.rear=null; } publicbooleanisEmpty(){ returnthis.front==null&&this.rear==null; } publicvoidenqueue(Tx){ if(x==null) return; Node if(this.front==null) this.front=q; else 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 publicTdata; publicNode publicNode(Tdata,Node this.data=data; this.next=next; } publicNode(TData){ this(Data,null); } publicNode(){ this(null,null); } } 验证代码 package实验4; public
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 java 实验