12信管实验报告(树与二叉树的基本操作).doc

管理 学院 信管 专业 12（1） 班 学号 3112004734 姓名 协作者： 无 教师评定_实验题目 树与二叉树的基本操作 实验评分表指导教师评分标准序号评分项目评分标准满分打分1完成度按要求独立完成实验准备、程序调试、实验报告撰写。202实验内容（1） 完成功能需求分析、存储结构设计；（2） 程序功能完善、可正常运行；（3） 测试数据正确，分析正确，结论正确。303实验报告内容齐全，符合要求，文理通顺，排版美观。404总结对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。10下述代码尽管输入eclipse或者JC验证，绝无弄虚作假实验报告一、 实验目的与要求1. 本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概念、存储结构及操作要求，体会顺序和链式两种存储结构的特点； 2. 根据操作的不同要求，选择合适的存储结构，设计并实现算法，对算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。 二、 实验内容1. 在一棵二叉链表表示的二叉树中,实现以下操作，并说明采用哪种遍历算法,其他遍历算法是否可行。（1） 输出叶子结点/求二叉树叶子结点个数的递归算法（2） public class leaf /输出叶子结点（3） public static void leaf(BinaryTree bitree)（4） leaf(bitree.root);（5） （6） public static void leaf(BinaryNode p)（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） public static void main(String args)（17） String prelist=A,B,D,null,G,null,null,null,C,E,null,null,F,G;/先根遍历序列（18） BinaryTree bitree=new BinaryTree(prelist);/以先根遍历序列构造的一棵二叉树（19） bitree.preOrder();/先根次序遍历的递归算法（20） leaf(bitree);（21） （22） String prelist2=A,B,null,null,C;/先根遍历序列（23） BinaryTree bitree2=new BinaryTree(prelist2);/以先根遍历序列构造的一棵二叉树（24） bitree2.preOrder();/先根次序遍历的递归算法（25） leaf(bitree2);（26） （27） （28） 运算结果： (2)求二叉树中叶子节点的个数/求二叉树中叶子结点的个数的递归算法public class getLeavespublic static int getLeaves(BinaryTree bitree)return getLeaves(bitree.root);public static int getLeaves(BinaryNode p)int i=0;if(p!=null) if(p.left=null&p.right=null)i+;getLeaves(p.left);getLeaves(p.right);System.out.println(i);return 0;public static void main(String args) String prelist=A,B,D,null,G,null,null,null,C,E,null,null,F,E; BinaryTree bitree=new BinaryTree(prelist); bitree.preOrder(); getLeaves(bitree); String prelist2=A,B,null,null,C; BinaryTree bitree2=new BinaryTree(prelist2); bitree2.preOrder(); getLeaves(bitree2);运算结果： (3)将每个结点的左子树和右子树交换/将二叉树的每个结点的左右子树交换的递归算法/交换二叉树的左右子树的递归算法的实现public class Bitree_revolutepublic static void Bitree_revolute(BinaryTree bitree)Bitree_revolute(bitree.root);/从bitree树的根结点开始遍历public static void Bitree_revolute(BinaryNode p)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();public static void main(String args)String prelist=A,B,D,null,G,null,null,null,C,E,null,null,F,E;BinaryTree bitree=new BinaryTree(prelist);bitree.preOrder();/先根次序遍历Bitree_revolute(bitree);String prelist2=A,B,null,null,C;BinaryTree bitree2=new BinaryTree(prelist2);bitree2.preOrder();/先根次序遍历Bitree_revolute(bitree2);运算结果：(4)验证二叉树的性质3：n0=n2+1/验证二叉树的性质3的递归算法public class Property3 /验证二叉树的性质3,n0=n2+1private static int n0=0,n2=0;/声明并初始化2度结点数n2,0度结点数n0(0度结点数即是叶子结点数)public static void count(BinaryTree bitree)/统计二度结点数n2和叶子结点数n0n0=0;n2=0;count(bitree.root);System.out.println(验证二叉树的性质3,n0=+n0+,n2=+n2+,n0=n2+1?+(n0=n2+1);private static void count(BinaryNode p)/统计二度结点数n2和叶子结点数n0/以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);public static void main(String args)/测试String prelist=A,B,D,null,G,null,null,null,C,E,null,null,F,E; /以一维数组String prelist存储二叉树的标明空子树的先根遍历序列BinaryTree bitree=new BinaryTree(prelist);/以先根遍历序列prelist构造二叉树bitreebitree.preOrder();/先根次序遍历的递归算法count(bitree);String prelist2=A,B,null,null,C;/以一维数组String prelist2存储二叉树的标明空子树的先根遍历序列2BinaryTree bitree2=new BinaryTree(prelist2);/以先根遍历序列构造二叉树bitree2bitree2.preOrder();/先根次序遍历的递归算法count(bitree);运算结果：(5)判断一棵二叉树bitree是否与当前二叉树的一棵子树匹配。方法一：public class BoolIsSubTree_1 public static void main(String args)String prelist=A,B,D,null,G,null,null,null,C,E,null,null,F,E;BinaryTree bitree=new BinaryTree(prelist);String prestr=bitree.preOrder(); String instr=bitree.inOrder();String prelist2=C,E,F; String inlist=E,C,F; BinaryTree bitree2=new BinaryTree(prelist2,inlist); if(inlist.toString().indexOf(instr)!=-1&(prelist.toString().indexOf(prestr)!=-1) System.out.println(bitree2是bitree的子树); else System.out.println(bitree2不是bitree的子树);运算结果：方法二：/判断一棵二叉树是否为另一颗二叉树的子树的递归算法public class BoolIsSubTree public static void main(String args)String prelist=A,B,D,null,G,null,null,null,C,E,null,null,F,E;/先根遍历序列BinaryTree bitree=new BinaryTree(prelist);/以先根遍历序列构造一棵二叉树String inlist=E,C,F;/中根遍历序列String prelist2=C,E,F;/先根遍历序列BinaryTree bitree2=new BinaryTree(prelist2,inlist);/以中根遍历序列和先根遍历序列构造一棵子树BinaryNode p = null;BinaryNode q = null;bitree.postOrder(p, q, bitree2);运算结果：辅助类：BinaryNodepublic class BinaryNode/二叉树的二叉链表结点类 public T data;/数据域 public BinaryNode left,right;/链域,分别指向左右孩子结点 /构造结点,参数分别指定元素和左右孩子结点 public BinaryNode(T data,BinaryNode left,BinaryNode right)/构造二叉树结点 this.data=data; this.left=left; this.right=right; /* * param args */ public BinaryNode(T data)/调用二叉树结点的构造方法 this(data,null,null);/构造指定值的叶子结点 public BinaryNode()/调用二叉树结点的构造方法 this(null,null,null); /空的结点 public boolean isLeaf() / TODO Auto-generated method stubBinaryNode p=null;if(p.left=null&p.right=null)return true;elsereturn false;public BinaryNode getRightChild() /获取当前结点的右孩子结点return this.left;public BinaryNode getLeftChild() /获取当前节点的左孩子结点return this.right;public void setLeftChild(BinaryNode rightChild) /设置当前节点的右孩子结点this.left=rightChild;public void setRightChild(BinaryNode leftChild) /设置 当前结点的左孩子结点this.right=leftChild;辅助类：BinaryTreeimport java.util.LinkedList;/线性链表import java.util.Stack;/栈public class BinaryTree implements BinaryTTree public BinaryNode root;/根结点,结点结构为二叉链表 public BinaryTree() this.root=null; /构造空的二叉树/* * param args */public boolean isEmpty()return this.root=null; /判断二叉树是否为空Overridepublic int count() /返回一棵二叉树(子树)的结点数/ TODO Auto-generated method stubreturn count(root);/返回二叉树的结点个数public int count(BinaryNode p)/返回以p结点为根的子树的的结点个数if(p=null)return 0;elsereturn 1+count(p.left)+count(p.right);Overridepublic int height() / TODO Auto-generated method stubreturn 0;Overridepublic String preOrder() /先根次序遍历二叉树/ TODO Auto-generated method stubSystem.out.print(先根次序遍历二叉树: );preOrder(root);/调用先根次序遍历二叉树的递归方法/*System.out.println();*/String prestr=;return prestr;public String preOrder(BinaryNode p)/先根次序遍历以p结点为根结点的子二叉树,递归方法String prestr=;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);return prestr;Overridepublic String inOrder() /中根遍历二叉树/ TODO Auto-generated method stubSystem.out.print(中根次序遍历二叉树: );inOrder(root);String instr = ;/*System.out.println();*/return instr;public String inOrder(BinaryNode p)/中根次序遍历以p结点为根结点的子二叉树,递归方法String instr=;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);return instr;Overridepublic void postOrder() /后根次序遍历二叉树/ TODO Auto-generated method stubSystem.out.print(后根次序遍历二叉树: );postOrder(root);System.out.println();public void postOrder(BinaryNode p,BinaryNode q,BinaryTree bitree2)/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) /return postOrder(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的子树);/*public boolean postOrder(BinaryNode p,BinaryTree bitree2)BinaryNode q=bitree2.root;postOrder(p.left);postOrder(p.right);if(p.data=q.data)return postOrder(p.)*/public void postOrder(BinaryNode p)/后根次序遍历以p结点为根结点的子二叉树,递归方法if(p!=null)/如果二叉树不为空postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+);Overridepublic void levelorder() / TODO Auto-generated method stubOverridepublic BinaryNode search(T key) /查找并返回首次出现的关键字为key的元素结点/ TODO Auto-generated method stubreturn search(root,key); public BinaryNode search(BinaryNode p,T key) if(p=null|key=null)/如果p为空或者key为空则此算法无法实现 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;/返回查找的结果 Overridepublic BinaryNode getParent(BinaryNode node) / TODO Auto-generated method stubreturn null;Overridepublic void insertRoot() / TODO Auto-generated method stubOverridepublic BinaryNode insertChild(BinaryNode p, T x, boolean leftChild) / TODO Auto-generated method stubreturn null;Overridepublic void removeChild(BinaryNode p, boolean leftChild) / TODO Auto-generated method stubOverridepublic void removeAll() / TODO Auto-generated method stubpublic void inOrderTraverse()/中根次序遍历的非递归算法System.out.print(中根次序遍历(非递归): );LinkedStackBinaryNode stack=new LinkedStack();/创造空的链式栈存储二叉树结点BinaryNodeBinaryNode p=this.root;/p指向当前二叉树的根结点while(p!=null|!stack.isEmpty()/当p不为空或者栈不为空时开始执行if(p!=null)/如果p不为空,则表示刚刚到达p结点stack.push(p);/p结点入栈p=p.left;/进入左子树else/若p为空且栈不空,表示已经走完了一条路径,则需返回寻找下一条路径。而返回的结点就是刚刚经过的最后一个结点,即是根结点root,使指针p指向它,访问p结点,再进入p的右子树。p=stack.pop();/System.out.print(p.data+);p=p.right;/进入右子树System.out.println();public void preOrderTraverse()/先根次序遍历的非递归算法LinkedStackBinaryNode stack=new LinkedStack();/创造空的链式栈存储二叉树结点BinaryNodepublic void postOrderTraverse()/后根次序遍历的非递归算法LinkedStackBinaryNode stack=new LinkedStack();/创造空的链式栈 存储二叉树结点BinaryNodepublic void leaf()/遍历输出叶子结点leaf(root);public void leaf(BinaryNode p)/先根次序遍历,输出叶子结点,3种遍历次序的结果都一样if(p!=null)if(p.isLeaf()System.out.print(p.data+);leaf(p.left);leaf(p.right);public int getLeaves()/求一棵二叉树中所有叶子结点的个数return getLeaves(root);public int getLeaves(BinaryNode p)/求一棵二叉树叶子结点的个数if(p=null)return 0;if(p.isLeaf()return 1;return getLeaves(p.left)+getLeaves(p.right);/以先根和中根次序遍历序列构造二叉树public BinaryTree(T prelist,T inlist)/以先根和中根次序遍历序列构造二叉树this.root=create(prelist,inlist,0,0,prelist.length);/以先根和中根序列创造一棵子树,子树根结点值是prelistpreStart,n指定子序列的长度,返回/所创建的子树的根结点private BinaryNode create(T prelist,T inlist,int preStart,int inStart,int n)if(n=0)return null;T elem=prelistpreStart;/临时变量elem存储子树根结点值prelistpreStartBinaryNode p=new BinaryNode(elem);/创建叶子结点int i=0;/while(in&!elem.equals(inlistinStart+i)/在中根序列中寻找根结点的所在位置i+; p.left=create(prelist,inlist,preStart+1,inStart,i);/创建p的左子树 p.right=create(prelist,inlist,preStart+i+1,inStart+i+1,n-1-i);/创建p的右子树 return p;/标明空子树的先根遍历序列构造二叉树public BinaryTree(T prelist)/T prelist数组保存二叉树的先根遍历序列this.root=create(prelist);/create(prelist)方法创建一棵二叉树的子树/以标明空子树的先根