信管实验报告树及二叉树的基本操作.doc

-实验题目树与二叉树的根本操作实验评分表指导教师评分标准序号评分工程评分标准总分值打分1完成度按要求独立完成实验准备、程序调试、实验报告撰写。202实验容（1） 完成功能需求分析、存储构造设计；（2） 程序功能完善、可正常运行；（3） 测试数据正确，分析正确，结论正确。303实验报告容齐全，符合要求，文理通顺，排版美观。404总结对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。10实验报告一、 实验目的与要求1. 本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概念、存储构造及操作要求，体会顺序和链式两种存储构造的特点；2. 根据操作的不同要求，选择适宜的存储构造，设计并实现算法，对算法进展时间复杂度分析，从而到达掌握数据构造的研究方法、算法设计和分析方法的目的。二、 实验容1. 在一棵二叉链表表示的二叉树中,实现以下操作，并说明采用哪种遍历算法,其他遍历算法是否可行。（1） 输出叶子结点/求二叉树叶子结点个数的递归算法（2） publicclass leaf /输出叶子结点（3） publicstatic<T> voidleaf(BinaryTree<T> bitree)（4） leaf(bitree.root);（5） （6） publicstatic<T> voidleaf(BinaryNode<T> 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） publicstaticvoid main(String args)（16） String prelist="A","B","D",null,"G",null,null,null,"C","E",null,null,"F","G"/先根遍历序列（17） BinaryTree<String> bitree=new BinaryTree<String>(prelist);/以先根遍历序列构造的一棵二叉树（18） bitree.preOrder();/先根次序遍历的递归算法（19） leaf(bitree);（20） String prelist2="A","B",null,null,"C"/先根遍历序列（21） BinaryTree<String> bitree2=new BinaryTree<String>(prelist2);/以先根遍历序列构造的一棵二叉树（22） bitree2.preOrder();/先根次序遍历的递归算法（23） leaf(bitree2);（24） （25） 运算结果：(2)求二叉树中叶子节点的个数/求二叉树中叶子结点的个数的递归算法publicclass getLeavespublicstatic<T> intgetLeaves(BinaryTree<T> bitree)returngetLeaves(bitree.root);publicstatic<T> intgetLeaves(BinaryNode<T> 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;publicstaticvoid main(String args) String prelist="A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E" BinaryTree<String> bitree=new BinaryTree<String>(prelist); bitree.preOrder();getLeaves(bitree); String prelist2="A","B",null,null,"C" BinaryTree<String> bitree2=new BinaryTree<String>(prelist2); bitree2.preOrder();getLeaves(bitree2);运算结果： (3)将每个结点的左子树和右子树交换/将二叉树的每个结点的左右子树交换的递归算法/交换二叉树的左右子树的递归算法的实现publicclass Bitree_revolutepublicstatic<T> voidBitree_revolute(BinaryTree<T> bitree)Bitree_revolute(bitree.root);/从bitree树的根结点开场遍历publicstatic<T> voidBitree_revolute(BinaryNode<T> 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();publicstaticvoid main(String args)String prelist="A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"BinaryTree<String> bitree=new BinaryTree<String>(prelist);bitree.preOrder();/先根次序遍历Bitree_revolute(bitree);String prelist2="A","B",null,null,"C"BinaryTree<String> bitree2=new BinaryTree<String>(prelist2);bitree2.preOrder();/先根次序遍历Bitree_revolute(bitree2);运算结果：(4)验证二叉树的性质3：n0=n2+1/验证二叉树的性质3的递归算法publicclass Property3<T> /验证二叉树的性质3,n0=n2+1privatestaticintn0=0,n2=0;/声明并初始化2度结点数n2,0度结点数n0(0度结点数即是叶子结点数)publicstatic<T> void count(BinaryTree<T> bitree)/统计二度结点数n2和叶子结点数n0n0=0;n2=0;count(bitree.root);System.out.println("验证二叉树的性质3,n0="+n0+",n2="+n2+",n0=n2+1""+(n0=n2+1);privatestatic<T> void count(BinaryNode<T> 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);publicstaticvoid main(String args)/测试String prelist="A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E" /以一维数组String prelist存储二叉树的标明空子树的先根遍历序列BinaryTree<String> bitree=new BinaryTree<String>(prelist);/以先根遍历序列prelist构造二叉树bitreebitree.preOrder();/先根次序遍历的递归算法count(bitree);String prelist2="A","B",null,null,"C"/以一维数组String prelist2存储二叉树的标明空子树的先根遍历序列2BinaryTree<String> bitree2=new BinaryTree<String>(prelist2);/以先根遍历序列构造二叉树bitree2bitree2.preOrder();/先根次序遍历的递归算法count(bitree);运算结果：(5)判断一棵二叉树bitree是否与当前二叉树的一棵子树匹配。方法一：publicclass BoolIsSubTree_1 publicstaticvoid main(String args)String prelist="A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"BinaryTree<String> bitree=new BinaryTree<String>(prelist);String prestr=bitree.preOrder(); String instr=bitree.inOrder();String prelist2="C","E","F" String inlist="E","C","F" BinaryTree<String> bitree2=new BinaryTree<String>(prelist2,inlist);if(inlist.toString().inde*Of(instr)!=-1&&(prelist.toString().inde*Of(prestr)!=-1) System.out.println("bitree2是bitree的子树"); else System.out.println("bitree2不是bitree的子树");运算结果：方法二：/判断一棵二叉树是否为另一颗二叉树的子树的递归算法publicclass BoolIsSubTree publicstaticvoid main(String args)String prelist="A","B","D",null,"G",null,null,null,"C","E",null,null,"F","E"/先根遍历序列BinaryTree<String> bitree=new BinaryTree<String>(prelist);/以先根遍历序列构造一棵二叉树String inlist="E","C","F"/中根遍历序列String prelist2="C","E","F"/先根遍历序列BinaryTree<String> bitree2=new BinaryTree<String>(prelist2,inlist);/以中根遍历序列和先根遍历序列构造一棵子树BinaryNode<String> p = null;BinaryNode<String> q = null;bitree.postOrder(p, q, bitree2);运算结果：辅助类：BinaryNodepublicclass BinaryNode<T>/二叉树的二叉链表结点类public T data;/数据域public BinaryNode<T> left,right;/链域,分别指向左右孩子结点/构造结点,参数分别指定元素和左右孩子结点public BinaryNode(T data,BinaryNode<T> left,BinaryNode<T> 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); /空的结点 publicboolean isLeaf() / TODO Auto-generated method stubBinaryNode<T> p=null;if(p.left=null&&p.right=null)returntrue;elsereturnfalse;public BinaryNode<T> getRightChild() /获取当前结点的右孩子结点returnthis.left;public BinaryNode<T> getLeftChild() /获取当前节点的左孩子结点returnthis.right;publicvoid setLeftChild(BinaryNode<T> rightChild) /设置当前节点的右孩子结点this.left=rightChild;publicvoid setRightChild(BinaryNode<T> leftChild) /设置当前结点的左孩子结点this.right=leftChild;辅助类：BinaryTreeimport java.util.LinkedList;/线性链表import java.util.Stack;/栈public class BinaryTree<T> implements BinaryTTree<T> public BinaryNode<T> 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<T> 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<T> 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<T> 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<T> p,BinaryNode<T> q,BinaryTree<T> 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<T> p,BinaryTree<T> bitree2)BinaryNode<T> q=bitree2.root;postOrder(p.left);postOrder(p.right);if(p.data=q.data)return postOrder(p.)*/public void postOrder(BinaryNode<T> 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<T> search(T key) /查找并返回首次出现的关键字为key的元素结点/ TODO Auto-generated method stubreturn search(root,key); public BinaryNode<T> search(BinaryNode<T> p,T key) if(p=null|key=null)/如果p为空或者key为空则此算法无法实现 return null; if(p.data.equals(key) return p;/查找成功,返回找到的结点 BinaryNode<T> find=search(p.left,key);/在左子树中查找,递归调用 if(find=null)/假设在左子树中未找到 find=search(p.right,key); /则继续在右子树中查找,递归调用 return find;/返回查找的结果 Overridepublic BinaryNode<T> getParent(BinaryNode<T> node) / TODO Auto-generated method stubreturn null;Overridepublic void insertRoot() / TODO Auto-generated method stubOverridepublic BinaryNode<T> insertChild(BinaryNode<T> p, T *, boolean leftChild) / TODO Auto-generated method stubreturn null;Overridepublic void removeChild(BinaryNode<T> p, boolean leftChild) / TODO Auto-generated method stubOverridepublic void removeAll() / TODO Auto-generated method stubpublic void inOrderTraverse()/中根次序遍历的非递归算法System.out.print("中根次序遍历(非递归): ");LinkedStack<BinaryNode<T>> stack=new LinkedStack();/创造空的链式栈存储二叉树结点BinaryNode<T>BinaryNode<T> 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()/先根次序遍历的非递归算法LinkedStack<BinaryNode<T>> stack=new LinkedStack();/创造空的链式栈存储二叉树结点BinaryNode<T>public void postOrderTraverse()/后根次序遍历的非递归算法LinkedStack<BinaryNode<T>> stack=new LinkedStack();/创造空的链式栈存储二叉树结点BinaryNode<T>public void leaf()/遍历输出叶子结点leaf(root);public void leaf(BinaryNode<T> 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<T> 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<T> create(T prelist,T inlist,int preStart,int inStart,int n)if(n<=0)return null;T elem=prelistpreStart;/临时变量elem存储子树根结点值prelistpreStartBinaryNode<T> p=new BinaryNode<T>(elem);/创立叶子结点int i=0;/while(i<n&&!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)方法创立一棵二叉树的子树/以标明空子树的先根遍历序列构造二叉树/以标明空子树的先根遍历序列构造一棵子二叉树,子二叉树的根结点值是prelisti,返回所创立的子二叉树的根结点private int i=0;/私有成员变量(全局变量)i,由于参数按层次变化,因此i同时充当计数变量private BinaryNode<T> create(T prelist)/create(T prelist)是递归方法BinaryNode<T> p=null;/二叉树结点指针p初始化为空if(i<prelist.length)/i的值从0prelist.length-1T elem=prelisti;/elem保存子树的根结点值prelisti,临时变量elem存储prelist数组的所有元素值i+;if(elem!=null)/不能使elem!="",因为T不一定是Stringp=new BinaryNode<T>(elem);/创立叶子结点 p.left=create(prelist);/创立p的左子树 p.right=create(prelist);/创立p的右子树return p;/比拟两棵二叉树是否相等public boolean equals(Object obj) if(obj=this)return true;if(obj instanceof BinaryTree)BinaryTree<T> bitree=(BinaryTree) obj;return equals(this.root,bitree.root);return false;public boolean equals(BinaryNode<T> p,BinaryNode<T> q)/判断两棵子树是否相等,递归方法if(p=null&&q=null)return true;if(p!=null&&q!=null)return (p.data.equals(q.data)&&equals(p.right,q.right)&&equals(p.left,q.left);/递归调用return false;三、 实验结果和数据处理截图说明实验结果的正确性，如果有错误分析错误原因 (1)运算结果:(2)运算结果： (3)运算结果：(4)运算结果：5运算结果：四、 总结谈谈自己在实验中遇到的问题，解决的方法、在二叉链表表示的二叉树中增加上述的五个成员方法，在构造一棵二叉树的时候均采用了先根遍历序列的构造方法，遍历这棵二叉树的时候都是采用了先根次序遍历的递归算法，并且成员方法都是采用了递归算法。五、 问题与讨论1、 什么样的二叉树可以采用顺序存储构造？完全二叉树2、 二叉树层次序列为：ABCDEFGHIJK,中序序列为DBGEHJACIKF,能唯一确定一棵二叉树吗？如果能，请构造之。可以。         A                                 /                                      B        C                               /                                        D     E       K                                   /                                        G    H  I F                                                                                  J. z.