数据结构课程设计——二叉树与二叉排序树

《数据结构课程设计——二叉树与二叉排序树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》课程设计实验报告题目二叉树与二叉排序树的建立及其应用学院商学院专业信息系统与信息管理班级信息101学号201052275115学生姓名徐鸽同组成员王超男何艳李梦雪关冬张卫芳韦露莎指导教师刘小晶编写日期2012年6月27日一、问题描述：1.二叉树的操作及应用在此次课程设计中实现二叉树的建立，建立二叉树以后对该二叉树进行先根遍历、中根遍历、后根遍历操作。然后再应用这些遍历操作来实现二叉树的查找操作，并且根据两种遍历操作来判断两棵树是否相等。2.二叉排序树的有关操作根据二叉排序树的结构特征建立二叉排序树。并且在已有二叉排序树的基础上，根据二叉排序树的特点，对其进行查找操作

2、、插入操作、删除操作。二、问题分析：问题为：编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两颗二叉树，并判断这两颗二叉树是否相等。在整个课程设计中，我主要是负责二叉树相关应用内容里的建立两颗二叉树的工作。（1）首先取先跟遍历序列中的第一个字符作为根结点的数据域值建立根结点；（2）在中根遍历序列中查找确定这个根结点在中根遍历序列中的位置，由此得到在根结点左边的序列即为此根结点左子树的中根遍历序列，而右边的序列即为此根结点右子树的中根遍历序列。（3）根据左、右子树的中根遍历序列中的字符个数再在先序遍历序列中确定左、右子树的先序遍历序列。（4）根据（2）（3）确定的左、右子树的

3、先根和中根遍历序列采用递归调用的方法建立根结点的左、右子树。要实现上述建立的二叉树的步骤，需要引入5个参数：preOrder,inOrder,preIndex,inIndex和count。其中：参数preOrder是整棵树的先跟遍历序列；inPrder是整棵树的中根遍历序列；preIndex是先跟遍历序列在preOrder中的开始位置：inIdex是中根遍历序列在inOrder中的开始位置；count表示树种结点的个数。三、数据结构描述：二叉链式存储结构PublicclassBiTree{PrivateBiTreeNoderoot;//树的根结点PublicBiTree(){/

4、/构造一棵空树This.root=null;}PublicBiTree(BiTreeNoderoot){//构造一棵树This.root=root;}一、算法设计:1.算法流程图：2.具体算法：（每人负责不同部分）PublicBiTree(Stringpreorder,StringinOrder,intpreIndex,intinIndex,intcount){If(count>0){//先根和中根非空Charr=preorder.charAt(preIndex);//取先根字符串中的第一个元素作为根节点intI=0;for(;i

5、符串中的索引if(r==inOrder.charAt(i+inIndex))break;root=newBiTreeNode(r);//建立树的根结点root.setLchild(newBiTree(preorder,inOrder,preIndex+1.index,i).root);//建立树的左子树root.setRchild(newBiTree(preorder,inOrder,preIndex+i+1,inIndex+i+1,count-i-1).root);//建立树的右子树}}遍历publicclassBiTree{privateBiTreeNode1root;pu

6、blicBiTree(){this.root=null;}publicBiTree(BiTreeNode1root){this.root=root;}privatestaticintindex=0;publicBiTree(StringpreStr){charc=preStr.charAt(index++);if(c!='#'){root=newBiTreeNode1(c);root.setLchild(newBiTree(preStr).root);root.setRchild(newBiTree(preStr).root);}elseroot=null;}publicvoi

7、dpreRootTraverse(BiTreeNode1T){if(T!=null){System.out.print(T.getData());preRootTraverse(T.getLchild());preRootTraverse(T.getRchild());}}publicvoidinRootTraverse(BiTreeNode1T){if(T!=null){inRootTraverse(T.getLchild());System.out.print(T.getData());