数据结构java实验四

《数据结构（JAVA）》综合性、设计性实验成绩单开设时间：2012学年第一学期班级11信管4班学号1.2011305604152.2011305604183.2011305604194.2011305604205.201130560424姓名1.刘梓明2.王悦3.薛泽展4.杨海龙5.余柏烨实验题目实验四树和二叉树的基本操作成绩教师签名1《数据结构（JAVA）》实验报告实验题目：树和二叉树的基本操作指导教师：实验组长（姓名+学号）：组员（姓名+学号）：实验时间：组长签名：2一、实验报告撰写提纲1、实验目的1．理解二叉树的定义、性质、存储结构等基本概念，掌握二叉树类的设计方法，以及遍历、插入、删除等二叉树操作的算法实现；掌握采用链式存储结构表达非线性结构的设计方法；掌握采用递归算法实现递归数据结构基本操作的设计方法。2．熟悉树的定义、表示、存储结构和遍历，具备使用树各种操作的能力。2、实验内容（1）在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。①输入叶子结点。②求二叉树中叶子结点个数。③将每个结点的左子树与右子树交换。④验证二叉树的性质3：n0=n2+1。⑤输出值大于k的结点。⑥已知先根和中根次序遍历序列构造二叉树。⑦以广义表表示构造二叉树。⑧判断两颗二叉树是否相等。⑨求结点所在的层次。⑩求一颗二叉树在后根次序遍历下第一个访问的结点。⑪复制一颗二叉树。⑫判断一颗二叉树是否为完全二叉树。⑬实现二叉树后根次序遍历的非递归算法。（2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。①构造一颗三叉链表表示的二叉树。②返回指定结点的父母结点。③返回指定结点的所有祖先结点。④返回两结点最近的共同祖先结点。（3）在一颗中序线索二叉树中，实现以下操作。①调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树。②按后根次序遍历中序线索二叉树。③在构造二叉树时进行线索化。④插入、删除操作。3、实验步骤与结果（1）①审题：在一棵二叉链表表示的二叉树中，实现以下操作，并说明采用哪种遍历算法，其他遍历算法是否可行。①输入叶子结点。②求二叉树中叶子结点个数。③将每个结点的左子树与右子树交换。④验证二叉树的性质3：n0=n2+1。⑤输出值大于k的结点。⑥已知先根和中根次序遍历序列构造二叉树。3⑦以广义表表示构造二叉树。⑧判断两颗二叉树是否相等。⑨求结点所在的层次。⑩求一颗二叉树在后根次序遍历下第一个访问的结点。⑪复制一颗二叉树。⑫判断一颗二叉树是否为完全二叉树。⑬实现二叉树后根次序遍历的非递归算法。②编程：这道小题需要用到几个类，分别是结点类Node,树结点类BinaryNode，顺序栈LinkedStack,顺序队列LinkedQueue，然后编写BinaryTree类，逐一实现以上功能。验证类为yanzheng。③验证结果：图1图2图3图4图5图6图7图8图9图10图11图12图134（2）①审题：（2）声明三叉链表表示的二叉树类，实现二叉树的基本操作以及以下操作。①构造一颗三叉链表表示的二叉树。②返回指定结点的父母结点。③返回指定结点的所有祖先结点。④返回两结点最近的共同祖先结点。②编程：编写结点类TriNode，然后编写TriBinaryNode类实现二叉树的各个功能和方法。验证类为yanzheng2.③验证结果：图14（3）①审题：（3）在一颗中序线索二叉树中，实现以下操作。①调用求结点的前驱结点算法，按中根次序遍历一颗中序线索二叉树。②按后根次序遍历中序线索二叉树。③在构造二叉树时进行线索化。④插入、删除操作。②编程：编写结点类ThreadNode，然后编写中性线索二叉树ThreadTreee逐一实现各个功能。验证类为yanzheng3.③验证结果：图15图16图174、源码（1）BinaryTree类package实验4；publicclassBinaryTreeT{publicBinaryNodeTroot;publicBinaryTree(){this.root=null;5}publicvoidpreOrder(){System.out.print(先根次序遍历二叉树：);preOrder(root);System.out.println();}publicvoidpreOrder(BinaryNodeTp){if(p!=null){System.out.print(p.data.toString()+);preOrder(p.left);preOrder(p.right);}}publicBinaryTree(Tprelist[]){this.root=create(prelist);}privateinti=0;publicBinaryNodeTcreate(Tprelist[]){BinaryNodeTp=null;if(iprelist.length){Telem=prelist[i];i++;if(elem!=null){p=newBinaryNodeT(elem);p.left=create(prelist);p.right=create(prelist);}}returnp;}publicBinaryNodeTsearch(Tkey){//①输入叶子结点。returnsearch(root,key);}publicBinaryNodeTsearch(BinaryNodeTp,Tkey){if(p==null||key==null)returnnull;if(p.data.equals(key))returnp;BinaryNodeTfind=search(p.left,key);if(find==null)find=search(p.right,key);returnfind;}publicBinaryNodeTinsertChild(BinaryNodeTp,Tx){6if(p==null||x==null)returnnull;if(p.left==null){p.left=newBinaryNodeT(x,null,null);returnp.left;}elsep.right=newBinaryNodeT(x,null,null);returnp;}publicintyecount(){//②求二叉树中叶子结点个数。returnyecount(root);}publicintyecount(BinaryNodeTp){if(p==null)return0;if(p!=null&&p.left==null&&p.right==null)return1;returnyecount(p.left)+yecount(p.right);}publicBinaryNodeTJHjiedian(){//③将每个结点的左子树与右子树交换。returnJHjiedian(root);}publicBinaryNodeTJHjiedian(BinaryNodeTp){BinaryNodeTq=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);}returnp;}publicinttwoyezi(){//④验证二叉树的性质3：n0=n2+1。returntwoyezi(root);}publicinttwoyezi(BinaryNodeTp){inti,j;if(p==null)return0;else{i=twoyezi(p.left);7j=twoyezi(p.right);if(p.left!=null&&p.right!=null)returni+j+1;elsereturn(i+j);}}publicvoidDaJieDina(Tvalue){//⑤输出值大于k的结点。System.out.print(大于+value+的结点有：);BinaryNodeTp=this.root;DaJieDina(p,value);System.out.println();}publicvoidDaJieDina(BinaryNodeTp,Tvalue){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);}privateBinaryNodeTcreate(Tprelist[],Tinlist[],intpreStart,intinStart,intn){if(n=0)returnnull;Telem=prelist[preStart];BinaryNodeTp=newBinaryNodeT(elem);inti=0;while(in&&!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(BinaryNodeTp){if(p==null)8returnnull;Stringstr=p.data.toString();if(p.left!=null||p.right!=null)str+=(+toGenListString(p.left)+,+toGenListString(p.right)+);returnstr;}publicbooleancompareTree(BinaryNodeTroot2){//⑧判断两颗二叉树是否相等。returncompareNode(root,root2);}publicbooleancompareNode(BinaryNodeTp,BinaryNodeTq){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;}elsereturnfalse;}}publicintgetLevel(Tx){//⑨求结点所在的层次。returngetLevel(root,1,x);//令根结点的层次为1}privateintgetLevel(BinaryNodeTp,inti,Tx){//在以p结点（层次为i）为根的子树中，求x结点所在的层次if(p==null)//空树或查找不成功return-1;if(p.data.equals(x))returni;//查找成功intlevel=getLevel(p.left,i+1,x);//在左子树