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

数据结构课程设计实验报告题 目 二叉树与二叉排序树的建立及其应用 学 院 商学院 专 业 信息系统与信息管理 班 级 信息101 学 号 201052275115 学生姓名 徐鸽 同组成员 王超男 何艳 李梦雪 关冬 张卫芳 韦露莎 指导教师 刘小晶 编写日期 2012年6月27日 一、 问题描述：1.二叉树的操作及应用 在此次课程设计中实现二叉树的建立，建立二叉树以后对该二叉树进行 先根遍历、中根遍历、后根遍历操作。然后再应用这些遍历操作来实现二叉树的查找操作，并且根据两种遍历操作来判断两棵树是否相等。2.二叉排序树的有关操作根据二叉排序树的结构特征建立二叉排序树。并且在已有二叉排序树的基础上，根据二叉排序树的特点，对其进行查找操作、插入操作、删除操作。二、 问题分析： 问题为：编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两颗二叉树，并判断这两颗二叉树是否相等。在整个课程设计中，我主要是负责二叉树相关应用内容里的建立两颗二叉树的工作。（1） 首先取先跟遍历序列中的第一个字符作为根结点的数据域值建立根结点；（2） 在中根遍历序列中查找确定这个根结点在中根遍历序列中的位置，由此得到在根结点左边的序列即为此根结点左子树的中根遍历序列，而右边的序列即为此根结点右子树的中根遍历序列。（3） 根据左、右子树的中根遍历序列中的字符个数再在先序遍历序列中确定左、右子树的先序遍历序列。（4） 根据（2）（3）确定的左、右子树的先根和中根遍历序列采用递归调用的方法建立根结点的左、右子树。 要实现上述建立的二叉树的步骤，需要引入5个参数：preOrder,inOrder,preIndex,inIndex和count。其中：参数preOrder是整棵树的先跟遍历序列；inPrder是整棵树的中根遍历序列；preIndex是先跟遍历序列在preOrder中的开始位置：inIdex是中根遍历序列在inOrder中的开始位置；count表示树种结点的个数。三、 数据结构描述：二叉链式存储结构Public class BiTree Private BiTreeNode root; /树的根结点 Public BiTree() /构造一棵空树 This.root=null;Public BiTree(BiTreeNode root) /构造一棵树 This.root=root;四、 算法设计:1.算法流程图：2.具体算法：（每人负责不同部分）Public BiTree(String preorder,String inOrder,int preIndex,int inIndex,int count) If(count0) /先根和中根非空 Char r = preorder.charAt(preIndex); /取先根字符串中的第一个元素作为根节点 int I = 0; for(;i 0) char r = preOrder.charAt(preIndex);int i = 0;for (; i count; i+)if (r = inOrder.charAt(i + inIndex)break;root = new BiTreeNode1(r);root.setLchild(new creatBSTree1(preOrder, inOrder, preIndex + 1, inIndex,i).root);root.setRchild(new creatBSTree1(preOrder, inOrder, preIndex + i + 1,inIndex + i + 1, count - i - 1).root); public BiTreeNode1 getRoot() return root; public class BiTree private BiTreeNode1 root;public BiTree() this.root=null;public BiTree(BiTreeNode1 root) this.root=root;private static int index=0;public BiTree(String preStr) char c = preStr.charAt(index+); if(c!=#) root = new BiTreeNode1(c); root.setLchild(new BiTree(preStr).root); root.setRchild(new BiTree(preStr).root); else root=null;public void preRootTraverse(BiTreeNode1 T) if(T!=null) System.out.print(T.getData(); preRootTraverse(T.getLchild(); preRootTraverse(T.getRchild(); public void inRootTraverse (BiTreeNode1 T) if (T!=null)inRootTraverse (T.getLchild () );System.out.print (T.getData () );inRootTraverse (T.getRchild () ); public void postRootTraverse(BiTreeNode1 T) if(T!=null) System.out.print(T.getData(); postRootTraverse(T.getLchild(); postRootTraverse(T.getRchild(); public BiTreeNode1 getRoot() return root;public void setRoot(BiTreeNode1 root) this.root=root;import java.util.*;import javax.swing.*;public class BSTree1 BiTreeNode1 root1; static BiTreeNode1 root3, root2; Scanner sc = new Scanner(System.in); public BSTree1() creatBSTree1 T = new creatBSTree1(null, null, 0, 0, 0); root1 = T.getRoot(); public BiTreeNode1 setBSTree1(String preOrder, String inOrder, int i, int j, int k) creatBSTree1 T = new creatBSTree1(preOrder, inOrder, i, j, k); root1 = T.getRoot(); return root1; static boolean isEqual(BiTreeNode1 T1, BiTreeNode1 T2) if (T1 = null & T2 = null) return true; if (T1 != null & T2 != null) if (T1.getData().equals(T2.getData() if (isEqual(T1.getLchild(), T2.getLchild() if (isEqual(T1.getRchild(), T2.getRchild() return true; return false; public static void main() BSTree1 T1 = new BSTree1(); BSTree1 T2 = new BSTree1(); int select; System.out.println(); System.out.println(=二叉树=); System.out.println(); System.out.println( 1-建立 2-遍历 3-比较 0-退出 ); System.out.println(=); select = Integer.parseInt(JOptionPane.showInputDialog(null, 您选择的操作：, 输入, JOptionPane.QUESTION_MESSAGE); while (select != 0) switch (select) case 1: String preOrder = JOptionPane.showInputDialog(null, 请输入建立二叉树T1节点的先根顺序：, 输入, JOptionPane.QUESTION_MESSAGE); String inOrder = JOptionPane.showInputDialog(null, 请输入建立二叉树T1的节点中根顺序：, 输入, JOptionPane.QUESTION_MESSAGE); System.out.println(输入建立的二叉树T1节点的先根顺序是： + preOrder); System.out.println(输入建立的二叉树T1节点的节点的中根顺序是： + inOrder); root2 = T1.setBSTree1(preOrder, inOrder, 0, 0, preOrder.length(); System.out.println(树T1创建成功！); String preOrder1 = JOptionPane.showInputDialog(null, 请输入建立二叉树T2节点的节点的先根顺序：, 输入, JOptionPane.QUESTION_MESSAGE); String inOrder1 = JOptionPane.showInputDialog(null, 请输入建立二叉树T2节点的中根顺序：, 输入, JOptionPane.QUESTION_MESSAGE); System.out.println(输入建立的二叉树T2节点的节点的先根顺序是： + preOrder1); System.out.println(输入建立的二叉树T2节点的中根顺序是： + inOrder1); root3 = T2.setBSTree1(preOrder1, inOrder1, 0, 0, preOrder1.length(); System.out.println(树T2创建成功！); break; case 2: BiTree T = new BiTree(); System.out.println(1-先根遍历 2-中根遍历 3-后根遍历 4-退出); System.out.print(请输入选择(1-4); int select1 = Integer.parseInt(JOptionPane.showInputDialog(null, 您选择的操作：, 输入, JOptionPane.QUESTION_MESSAGE); while (select1 != 4) switch (select1) case 1: System.out.print(先跟遍历为:); T.preRootTraverse(root3); System.out.println(); break; case 2: System.out.print(中根遍历为:); T.inRootTraverse(root3); System.out.println(); break; case 3: System.out.print(后跟遍历为:); T.postRootTraverse(root3); System.out.println(); break; System.out.println(1-先根遍历 2-中根遍历 3-后根遍历 4-退出); System.out.print(请输入选择(1-4); select1 = Integer.parseInt(JOptionPane.showInputDialog(null, 您选择的操作：, 输入, JOptionPane.QUESTION_MESSAGE); break; case 3: if (isEqual(root2, root3) = true) System.out.println(T1和T2的关系是：T1=T2); else System.out.println(T1和T2的关系是：T1!=T2); break; case 0: System.exit(0); break; default: System.out.println(没有您选择的操作！); return; System.out.println(); System.out.println(=二叉树=); System.out.println(); System.out.println( 1-建立 2-遍历 3-比较 0-退出 ); System.out.println(=); select = Integer.parseInt(JOptionPane.showInputDialog(null, 您选择的操作：, 输入, JOptionPane.QUESTION_MESSAGE); /二叉排序树的基本操作与应用import java.util.*;import javax.swing.*;public class BSTree2 protected BiTreeNode2 root; private StringBuffer insert = new StringBuffer(); public BSTree2() root = null; public BSTree2(BiTreeNode2 root) this.root = root; public BiTreeNode2 getRoot() return root; public void setRoot(BiTreeNode2 root) this.root = root; public StringBuffer inOrderTraverse(BiTreeNode2 p) if (p != null) inOrderTraverse(p.getLchild(); insert.append(p.getkey().append( ); inOrderTraverse(p.getRchild(); return insert; public BiTreeNode2 searchBST(int key) return searchBST(root, key); /二叉排序树上的递归查找算法 private BiTreeNode2 searchBST(BiTreeNode2 p, int key) if (p != null) if (key = p.getkey() /查找成功 return p; /System.out.print(RecordNode)p.getData().getKey()+?); else if (key p.getkey() return searchBST(p.getLchild(), key); /在左子树中查找 else return searchBST(p.getRchild(), key); /在右子树中查找 return null; public boolean insertBST(int key) if (root = null) root = new BiTreeNode2(key); return true; return insertBST(root, key); private boolean insertBST(BiTreeNode2 p, int key) if (key = p.getkey() return false; if (key p.getkey() if (p.getLchild() = null) p.setLchild(new BiTreeNode2(key); return true; else return insertBST(p.getLchild(), key); else if (p.getRchild() = null) p.setRchild(new BiTreeNode2(key); return true; else return insertBST(p.getRchild(), key); public BiTreeNode2 removeBST(int key) return removeBST(root, key, null); private BiTreeNode2 removeBST(BiTreeNode2 p, int key, BiTreeNode2 parent) if (p != null) if (key p.getkey() return removeBST(p.getRchild(), key, p); else if (p.getLchild() != null & p.getRchild() != null) BiTreeNode2 innext = p.getRchild(); while (innext.getLchild() != null) innext = innext.getLchild(); p.setKey(innext.getkey(); return removeBST(p.getRchild(), p.getkey(), p); else if (parent = null) if (p.getLchild() != null) root = p.getLchild(); else root = p.getRchild(); return p; if (p = parent.getLchild() if (p.getLchild() != null) parent.setLchild(p.getLchild(); else parent.setLchild(p.getRchild(); else if (p.getLchild() != null) parent.setRchild(p.getLchild(); else parent.setRchild(p.getRchild(); return p; return null; public static void main() int input; BSTree2 bstree = new BSTree2(); int select; System.out.println(); System.out.println(=二叉排序树=); System.out.println(); System.out.println( 1-建立 2-查询 3-删除 4-插入 5-遍历 0-退出 ); System.out.println(=); select = Integer.parseInt(JOptionPane.showInputDialog(null, 您选择的操作：, 输入, JOptionPane.QUESTION_MESSAGE); while (select != 0) switch (select) case 1: input = Integer.parseInt(JOptionPane.showInputDialog(null, 请输入二叉排序树的结点个数, 输入, JOptionPane.QUESTION_MESSAGE); System.out.println(输入的二叉排序树结点个数为： + input); StringBuffer str = new StringBuffer(); int key; for (int i = 1; i = input; i+) /输入关键字序列 key = Integer.parseInt(JOptionPane.showInputDialog(null, 请输入结点的关键字序列：, 输入, JOptionPane.QUESTION_MESSAGE); bstree.insertBST(key); str.append(key).append( ); System.out.println(输入的结点关键字序列为： + str); break; case 2: input = Integer.parseInt(JOptionPane.showInputDialog(null, 请输入待查找的关键字：, 输入, JOptionPane.QUESTION_MESSAGE); BiTreeNode2 found = bstree.searchBST(input); System.out.println(输入的待查找关键字是： + input); if (found != null) System.out.println(查找成功！); else System.out.println(查找失败！); break; case 3: input = Integer