《12信管实验报告材料树与二叉树地基本操作.doc》由会员分享，可在线阅读，更多相关《12信管实验报告材料树与二叉树地基本操作.doc（26页珍藏版）》请在课桌文档上搜索。
1、实验报告一、 实验目的与要求1. 本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概念、存储结构与操作要求，体会顺序和链式两种存储结构的特点；2. 根据操作的不同要求，选择适宜的存储结构，设计并实现算法，对算法进展时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。二、 实验内容1. 在一棵二叉链表表示的二叉树中,实现以下操作，并说明采用哪种遍历算法,其他遍历算法是否可行。（1） 输出叶子结点/求二叉树叶子结点个数的递归算法（2） publicclass leaf /输出叶子结点（3） publicstatic voidleaf(BinaryTree bitree
2、)（4） leaf(bitree.root);（5） （6） publicstatic voidleaf(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） publicstaticvoid main(String args)（17） String prelist=A,B,D,null,G,null,null,null,C,E,null,nul
3、l,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
4、）（27） （28） 运算结果：(2)求二叉树中叶子节点的个数/求二叉树中叶子结点的个数的递归算法publicclass getLeavespublicstatic intgetLeaves(BinaryTree bitree)returngetLeaves(bitree.root);publicstatic intgetLeaves(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
5、;publicstaticvoid 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);运算结果：
6、(3)将每个结点的左子树和右子树交换/将二叉树的每个结点的左右子树交换的递归算法/交换二叉树的左右子树的递归算法的实现publicclass Bitree_revolutepublicstatic voidBitree_revolute(BinaryTree bitree)Bitree_revolute(bitree.root);/从bitree树的根结点开始遍历publicstatic voidBitree_revolute(BinaryNode p)if(p!=null)p.setLeftChild(p.getRightChild();/交换左右子树p.setRightChild(p.ge
7、tLeftChild();/交换左右子树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 bitree=new Binary
8、Tree(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的递归算法publicclass Property3 /验证二叉树的性质3,n0=n2+1privatestaticintn0=0,n2=0;/声明并
9、初始化2度结点数n2,0度结点数n0(0度结点数即是叶子结点数)publicstatic 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);privatestatic void count(BinaryNode p)/统计二度结点数n2和叶子结点数n0/以p结点为根的子树的结点数if(p!=null)if(p.left=null&p.right=null)/叶子结点n
10、0+;/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 bitree=new BinaryTree(prelist);/以先根遍历序列prelist构造二叉树bitreebitree.preOrder();/先根次序
11、遍历的递归算法count(bitree);String prelist2=A,B,null,null,C;/以一维数组String prelist2存储二叉树的标明空子树的先根遍历序列2BinaryTree bitree2=new BinaryTree(prelist2);/以先根遍历序列构造二叉树bitree2bitree2.preOrder();/先根次序遍历的递归算法count(bitree);运算结果：(5)判断一棵二叉树bitree是否与当前二叉树的一棵子树匹配。方法一：publicclass BoolIsSubTree_1 publicstaticvoid main(String
12、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
13、)!=-1&(prelist.toString().indexOf(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;/先根遍历序列BinaryTr
14、ee 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);运算结果：辅助类：BinaryNodepublicclass BinaryNode/二叉树的二叉链表结
15、点类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 Binary
16、Node()/调用二叉树结点的构造方法this(null,null,null); /空的结点 publicboolean isLeaf() / TODO Auto-generated method stubBinaryNode p=null;if(p.left=null&p.right=null)returntrue;elsereturnfalse;public BinaryNode getRightChild() /获取当前结点的右孩子结点returnthis.left;public BinaryNode getLeftChild() /获取当前节点的左孩子结点returnthis.righ
17、t;publicvoid setLeftChild(BinaryNode rightChild) /设置当前节点的右孩子结点this.left=rightChild;publicvoid setRightChild(BinaryNode leftChild) /设置 当前结点的左孩子结点this.right=leftChild;辅助类：BinaryTreeimport java.util.LinkedList;/线性链表import java.util.Stack;/栈public class BinaryTree implements BinaryTTree public BinaryNod
18、e 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=
19、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 pres
20、tr=;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(
21、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.l
22、eft);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(Bin
23、aryNode 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
24、) /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 pos
25、tOrder(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()+);Overr
26、idepublic 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(k
27、ey) 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() / T
28、ODO 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-generat
29、ed 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
30、;/进入左子树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 v
31、oid 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
32、()/求一棵二叉树中所有叶子结点的个数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);
33、/以先根和中根序列创造一棵子树,子树根结点值是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)
34、/在中根序列中寻找根结点的所在位置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)方法创建一棵二叉树的子树/以标明空子树的先根遍历序列构
35、造二叉树/以标明空子树的先根遍历序列构造一棵子二叉树,子二叉树的根结点值是prelisti,返回所创建的子二叉树的根结点private int i=0;/私有成员变量(全局变量)i,由于参数按层次变化,因此i同时充当计数变量private BinaryNode create(T prelist)/create(T prelist)是递归方法BinaryNode p=null;/二叉树结点指针p初始化为空T elem=prelisti;/elem保存子树的根结点值prelisti,临时变量elem存储prelist数组的所有元素值i+;if(elem!=null)/不能使elem!=,因为T不一
36、定是Stringp=new BinaryNode(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 bitree=(BinaryTree) obj;return equals(this.root,bitree.root);return false;publ
37、ic boolean equals(BinaryNode p,BinaryNode 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/BC/DEK/GHI FJ
