信管实验报告树与二叉树的基本操作.docx
- 文档编号:14185248
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:26
- 大小:65.44KB
信管实验报告树与二叉树的基本操作.docx
《信管实验报告树与二叉树的基本操作.docx》由会员分享,可在线阅读,更多相关《信管实验报告树与二叉树的基本操作.docx(26页珍藏版)》请在冰点文库上搜索。
信管实验报告树与二叉树的基本操作
管理学院信管专业12
(1)班学号3112004734
协作者:
无教师评定_________________
实验题目树与二叉树的基本操作
实验评分表
指导教师评分标准
序号
评分项目
评分标准
满分
打分
1
完成度
按要求独立完成实验准备、程序调试、实验报告撰写。
20
2
实验容
(1)完成功能需求分析、存储结构设计;
(2)程序功能完善、可正常运行;
(3)测试数据正确,分析正确,结论正确。
30
3
实验报告
容齐全,符合要求,文理通顺,排版美观。
40
4
总结
对实验过程遇到的问题能初步独立分析,解决后能总结问题原因及解决方法,有心得体会。
10
下述代码尽管输入eclipse或者JC验证,绝无弄虚作假
实验报告
一、实验目的与要求
1.本实验通过对线性表各种操作的算法设计,理解和掌握线性表的概念、存储结构及操作要求,体会顺序和链式两种存储结构的特点;
2.根据操作的不同要求,选择合适的存储结构,设计并实现算法,对算法进行时间复杂度分析,从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。
二、实验容
1.在一棵二叉链表表示的二叉树中,实现以下操作,并说明采用哪种遍历算法,其他遍历算法是否可行。
(1)输出叶子结点
//求二叉树叶子结点个数的递归算法
(2)publicclassleaf{//输出叶子结点
(3)publicstatic
(4)leaf(bitree.root);
(5)}
(6)publicstatic
(7)if(p!
=null){
(8)if(p.left==null&&p.right==null){
(9)System.out.println(p.data+"");
(10)}
(11)leaf(p.left);
(12)leaf(p.right);
(13)
(14)}
(15)}
(16)publicstaticvoidmain(Stringargs[]){
(17)Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","G"};//先根遍历序列
(18)BinaryTree
(19)bitree.preOrder();//先根次序遍历的递归算法
(20)leaf(bitree);
(21)
(22)Stringprelist2[]={"A","B",null,null,"C"};//先根遍历序列
(23)BinaryTree
(24)bitree2.preOrder();//先根次序遍历的递归算法
(25)leaf(bitree2);
(26)
(27)}
(28)}
运算结果:
(2)求二叉树中叶子节点的个数
//求二叉树中叶子结点的个数的递归算法
publicclassgetLeaves{
publicstatic
returngetLeaves(bitree.root);
}
publicstatic
inti=0;
if(p!
=null)
{
if(p.left==null&&p.right==null){
i++;
}
getLeaves(p.left);
getLeaves(p.right);
}
System.out.println(i);
return0;
}
publicstaticvoidmain(Stringargs[]){
Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"};
BinaryTree
bitree.preOrder();
getLeaves(bitree);
Stringprelist2[]={"A","B",null,null,"C"};
BinaryTree
bitree2.preOrder();
getLeaves(bitree2);
}
}
运算结果:
(3)将每个结点的左子树和右子树交换
//将二叉树的每个结点的左右子树交换的递归算法
//交换二叉树的左右子树的递归算法的实现
publicclassBitree_revolute{
publicstatic
Bitree_revolute(bitree.root);//从bitree树的根结点开始遍历
}
publicstatic
if(p!
=null){
p.setLeftChild(p.getRightChild());//交换左右子树
p.setRightChild(p.getLeftChild());//交换左右子树
System.out.println(p.data.toString());
if(p.getLeftChild()!
=null){
Bitree_revolute(p.getLeftChild());
}
if(p.getRightChild()!
=null){
Bitree_revolute(p.getRightChild());
}
}
}
publicstaticvoidmain(Stringargs[]){
Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"};
BinaryTree
bitree.preOrder();//先根次序遍历
Bitree_revolute(bitree);
Stringprelist2[]={"A","B",null,null,"C"};
BinaryTree
bitree2.preOrder();//先根次序遍历
Bitree_revolute(bitree2);
}
}
运算结果:
(4)验证二叉树的性质3:
n0=n2+1
//验证二叉树的性质3的递归算法
publicclassProperty3
privatestaticintn0=0,n2=0;//声明并初始化2度结点数n2,0度结点数n0(0度结点数即是叶子结点数)
publicstatic
n0=0;n2=0;
count(bitree.root);
System.out.println("验证二叉树的性质3,n0="+n0+",n2="+n2+",n0==n2+1?
"+(n0==n2+1));
}
privatestatic
//以p结点为根的子树的结点数
if(p!
=null)
{
if(p.left==null&&p.right==null)//叶子结点
n0++;//
if(p.left!
=null&&p.right!
=null)//2度结点
n2++;
count(p.left);
count(p.right);
}
}
publicstaticvoidmain(Stringargs[]){//测试
Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"};//以一维数组Stringprelist[]存储二叉树的标明空子树的先根遍历序列
BinaryTree
bitree.preOrder();//先根次序遍历的递归算法
count(bitree);
Stringprelist2[]={"A","B",null,null,"C"};//以一维数组Stringprelist2[]存储二叉树的标明空子树的先根遍历序列2
BinaryTree
bitree2.preOrder();//先根次序遍历的递归算法
count(bitree);
}
}
运算结果:
(5)判断一棵二叉树bitree是否与当前二叉树的一棵子树匹配。
方法一:
publicclassBoolIsSubTree_1{
publicstaticvoidmain(Stringargs[]){
Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"};
BinaryTree
Stringprestr=bitree.preOrder();
Stringinstr=bitree.inOrder();
Stringprelist2[]={"C","E","F"};
Stringinlist[]={"E","C","F"};
BinaryTree
if(inlist.toString().indexOf(instr)!
=-1&&(prelist.toString().indexOf(prestr)!
=-1)){
System.out.println("bitree2是bitree的子树");
}
else
System.out.println("bitree2不是bitree的子树");
}
}
运算结果:
方法二:
//判断一棵二叉树是否为另一颗二叉树的子树的递归算法
publicclassBoolIsSubTree{
publicstaticvoidmain(Stringargs[]){
Stringprelist[]={"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"};//先根遍历序列
BinaryTree
Stringinlist[]={"E","C","F"};//中根遍历序列
Stringprelist2[]={"C","E","F"};//先根遍历序列
BinaryTree
BinaryNode
BinaryNode
bitree.postOrder(p,q,bitree2);
}
}
运算结果:
辅助类:
BinaryNode
publicclassBinaryNode
publicTdata;//数据域
publicBinaryNode
//构造结点,参数分别指定元素和左右孩子结点
publicBinaryNode(Tdata,BinaryNode
this.data=data;
this.left=left;
this.right=right;
}
/**
*paramargs
*/
publicBinaryNode(Tdata){//调用二叉树结点的构造方法
this(data,null,null);//构造指定值的叶子结点
}
publicBinaryNode(){//调用二叉树结点的构造方法
this(null,null,null);//空的结点
}
publicbooleanisLeaf(){
//TODOAuto-generatedmethodstub
BinaryNode
if(p.left==null&&p.right==null)
returntrue;
else
returnfalse;
}
publicBinaryNode
returnthis.left;
}
publicBinaryNode
returnthis.right;
}
publicvoidsetLeftChild(BinaryNode
this.left=rightChild;
}
publicvoidsetRightChild(BinaryNode
this.right=leftChild;
}
}
辅助类:
BinaryTree
importjava.util.LinkedList;//线性链表
importjava.util.Stack;//栈
publicclassBinaryTree
publicBinaryNode
publicBinaryTree(){
this.root=null;
}//构造空的二叉树
/**
*paramargs
*/
publicbooleanisEmpty(){
returnthis.root==null;
}
//判断二叉树是否为空
Override
publicintcount(){//返回一棵二叉树(子树)的结点数
//TODOAuto-generatedmethodstub
returncount(root);//返回二叉树的结点个数
}
publicintcount(BinaryNode
if(p==null)
return0;
else
return1+count(p.left)+count(p.right);
}
Override
publicintheight(){
//TODOAuto-generatedmethodstub
return0;
}
Override
publicStringpreOrder(){//先根次序遍历二叉树
//TODOAuto-generatedmethodstub
System.out.print("先根次序遍历二叉树:
");
preOrder(root);//调用先根次序遍历二叉树的递归方法
/*System.out.println();*/
Stringprestr="";
returnprestr;
}
publicStringpreOrder(BinaryNode
Stringprestr="";
if(p!
=null){//如果二叉树不为空
/*System.out.println(p.data.toString()+"");//访问当前结点
preOrder(p.left);//按照先根次序遍历访问当前结点的左子树,递归调用
preOrder(p.right);//按照先根次序遍历访问当前结点的右子树,递归调用*/
prestr+=p.data.toString();
preOrder(p.left);
preOrder(p.right);
}
returnprestr;
}
Override
publicStringinOrder(){//中根遍历二叉树
//TODOAuto-generatedmethodstub
System.out.print("中根次序遍历二叉树:
");
inOrder(root);
Stringinstr="";
/*System.out.println();*/
returninstr;
}
publicStringinOrder(BinaryNode
Stringinstr="";
if(p!
=null)//若二叉树不空
{
/*inOrder(p.left);
System.out.print(p.data.toString()+"");
inOrder(p.right);*/
inOrder(p.left);
instr+=p.data.toString();
inOrder(p.right);
}
returninstr;
}
Override
publicvoidpostOrder(){//后根次序遍历二叉树
//TODOAuto-generatedmethodstub
System.out.print("后根次序遍历二叉树:
");
postOrder(root);
System.out.println();
}
publicvoidpostOrder(BinaryNode
if(p!
=null&&q!
=null)//如果二叉树不为空
{
postOrder(p.left);
postOrder(p.right);
//System.out.println(p.data.toString()+"");
/*if(p.data==q.data&&p.left==q.left&&p.right==q.right){
postOrder(p.left);
postOrder(q.left);
postOrder(p.right);
postOrder(q.right);//遍历bitree2
}*/
//if(p.data==q.data){
//returnpostOrder(p.left,q.left,bitree2)&&postOrder(p.right,q.right,bitree2);
//}
if(p.data==bitree2.root){
if(p.data==q.data)
postOrder(p.left,q.left,bitree2);
postOrder(p.right,q.right,bitree2);
if((p.isLeaf()==true)&&(q.isLeaf()==true)&&(p.data==q.data)){
System.out.println("bitree2是bitree的子树");
}
}
}
}
/*publicbooleanpostOrder(BinaryNode
BinaryNode
postOrder(p.left);
postOrder(p.right);
if(p.data==q.data){
returnpostOrder(p.)
}*/
publicvoidpostOrder(BinaryNode
if(p!
=null)//如果二叉树不为空
{
postOrder(p.left);
postOrder(p.right);
System.out.print(p.data.toString()+"");
}
}
Override
publicvoidlevelorder(){
//TODOAuto-generatedmethodstub
}
Override
publicBinaryNode
//TODOAuto-generated
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 报告 二叉 基本 操作