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

《数据结构》课程设计

实验报告

题 目 二叉树与二叉排序树的建立及其应用 学 院 商学院 专 业 信息系统与信息管理 班 级 信息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(count>0){ //先根和中根非空 Char r = preorder.charAt(preIndex);

//取先根字符串中的第一个元素作为根节点 int I = 0; for(;i//寻找根结点在中根遍历字符串中的索引

if(r==inOrder.charAt(i+inIndex)) break;

root=new BiTreeNode(r); //建立树的根结点

root.setLchild(new BiTree(preorder,inOrder,preIndex+1.index,i).root);

//建立树的左子树 root.setRchild(new

BiTree(preorder,inOrder,preIndex+i+1,inIndex+i+1,count-i-1).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; } }

五 详细程序清单

class BiTreeNode1 {

private Object data;

private BiTreeNode1 root;

private BiTreeNode1 lchild,rchild; public BiTreeNode1() { this(null); }

public BiTreeNode1(Object data) { this(data,null,null); }

public BiTreeNode1 (Object data, BiTreeNode1 lchild,BiTreeNode1 rchild){ this.data=data; this.lchild=lchild; this.rchild=rchild; }

public Object getData() { return data;

}

public void setData(Object data) { this.data = data; }

public BiTreeNode1 getLchild() { return lchild; }

public void setLchild(BiTreeNode1 lchild) { this.lchild = lchild; }

public BiTreeNode1 getRchild() { return rchild; }

public void setRchild(BiTreeNode1 rchild) { this.rchild = rchild; }

public BiTreeNode1 getRoot(){ return root; }

public void setRoot(BiTreeNode1 root){ this.root=root; } }

class BiTreeNode2 { private int key;

private BiTreeNode2 lchild, rchild; private Object data;

public BiTreeNode2(){ this(0,null,null); }

public BiTreeNode2(int key){ this(key,null,null); }

public BiTreeNode2(int lchild,BiTreeNode2 rchild){

this.key=key;

this.lchild=lchild;

key,BiTreeNode2

this.rchild=rchild; }

public int getkey(){ return key; }

public BiTreeNode2 getLchild(){ return lchild; }

public BiTreeNode2 getRchild(){ return rchild; }

public void setKey(int key){ this.key=key; }

public void setLchild(BiTreeNode2 lchild){ this.lchild=lchild; }

public void setRchild(BiTreeNode2 rchild){ this.rchild=rchild; }

public Object getData(Object data) {

return data; }

public void setData(Object data) { this.data = data; } }

class creatBSTree1{

private BiTreeNode1 root; public creatBSTree1(String preOrder, String inOrder, int preIndex, int inIndex,

int count){ if (count > 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, \"您选择的操作：\\"输入\

while (select != 0) { switch (select) { case 1: { String preOrder = JOptionPane.showInputDialog(null, \"请输入建立二叉树T1节点的先根顺序：\\"输入\

String inOrder = JOptionPane.showInputDialog(null, \"请输入建立二叉树T1的节点中根顺序：\\"输入\

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节点的节点的先根顺序：\输入\

String inOrder1 = JOptionPane.showInputDialog(null, \"请输入建立二叉树T2节点的中根顺序：\\"输入\

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, \"您选择的操作：\\"输入\

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, \"您选择的操作：\\"输入\

} 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, \"您选择的操作：\\"输入\

} } }

//二叉排序树的基本操作与应用 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(), //在左子树中查找

} 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) {

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.getLchild(), key, p); } else if (key > p.getkey()) {

return removeBST(p.getRchild(), key, p); } {

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; }

else if (p.getLchild() != null && p.getRchild() != 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, \"您选择的操作：\\"输入\

while (select != 0) { switch (select) { case 1: { input = Integer.parseInt(JOptionPane.showInputDialog(null, \"请输入二叉排序树的结点个数\输入\

System.out.println(\"输入的二叉排序树结点个数为：\" + input);

StringBuffer str = new StringBuffer(); int key;

for (int i = 1; i <= input; i++) {//输入关键字序列

key

=

Integer.parseInt(JOptionPane.showInputDialog(null, \"请输入结点的关键字序列：\输入\

bstree.insertBST(key);

str.append(key).append(\" \"); } System.out.println(\"输入的结点关键字序列为：\" + str);

}

break; case 2: { input = Integer.parseInt(JOptionPane.showInputDialog(null, \"请输入待查找的关键字：\输入\

BiTreeNode2 found = bstree.searchBST(input);

System.out.println(\"输入的待查找关键字是：\" + input);

if (found != null) {

System.out.println(\"查找成功！\"); } else {

System.out.println(\"查找失败！\"); } }

break; case 3: { input

=

Integer.parseInt(JOptionPane.showInputDialog(null, \"请输入待删除的关键字:\输入\

System.out.println(\"输入的待删除关键字是:\" + input);

BiTreeNode2 found1 = bstree.removeBST(input); if (found1 != null) {

System.out.println(\"删除成功！\"); } else {

System.out.println(\"删除失败！\"); } }

break; case 4: { input

=

Integer.parseInt(JOptionPane.showInputDialog(null, \"请输入待插入的关键字:\输入\

System.out.println(\"输入的待插入关键字是:\" + input);

bstree.insertBST(input); System.out.println(\"插入成功！\"); }

break; case 5: {

StringBuffer str1 bstree.inOrderTraverse(bstree.getRoot());

=

System.out.println(\"创建的二叉排序树的序遍历序列为：\" + str1);

}

break; case 0:

System.exit(0); break;

default:

System.out.println(\"没有您选择的操作！\"); return; }

System.out.println();

System.out.println(\" 1--建立 2--查询 3--删除 4--插入 5--遍历 0--退出 \");

System.out.println(\"=====================================================\");

select = Integer.parseInt(JOptionPane.showInputDialog(null, \"您选择的操作：\\"输入\

} } }

import java.util.*; import javax.swing.*;

public class MyJava { public MyJava(){ int select; while(true){

System.out.println(); System.out.println(\"==========二叉树、二叉排序树基本操作与应用=============\");

System.out.println(); System.out.println(\" 1--二叉树 2--二叉排序树 3--退出 \");

System.out.println(\"=====================================================\");

select=Integer.parseInt(JOptionPane.showInputDialog(null, \"请选择操作\输入\

switch(select){ case 1:

BSTree1.main(); break; case 2:

BSTree2.main(); break;

case 3: return; } } }

public static void main(String args[]){ MyJava mj=new MyJava(); } }

六 程序运行结果

1、主界面

在doc命令窗口下运行主程序MyJava.java

2、二叉树基本操作与应用

1）在主界面下选择1，进入二叉树菜单界面；选择1，建立两棵二叉树

2）建树成功，选择2对树T2进行遍历

a)选择1进行先根遍历

b)选择2进行中根遍历

c)选择3进行后根遍历

d)选择4返回二叉树基本操作菜单界面

2）选择3对两棵树进行比较

3）选择0退出二叉树基本操作界面，返回主界面

3、二叉排序树基本操作与应用

1）在主界面选择2进入二叉排序树基本操作菜单界面

2）选择1建立一棵二叉排序树

3）选择2对新建的树进行查询节点2

4）由查询结果可知该树没有节点2，选择4，插入节点2

5）选择5对树进行遍历，查看遍历结果中是否成功插入节点2

6）由遍历结果可知，节点2已成功插入该树。选择3删除新插入的节点2

7）选择2，查询刚删除的节点2

8）由查询结果可知，节点2已成功删除。选择5，遍历所有操作后的树的情况

9）由遍历结果可知，以上所有操作均已成功执行！选择0退出二叉排序树基本操作菜单界面，返回主界面。

10）在主菜单界面下选择3，退出系统。

七 心得体会：

此次课程设计我们小组的题目是《二叉树的相关操作及其应用》，我们利用

典型问题做了研究，我们首先分析了课程设计的任务、要求和目的，经过小组讨论，明确了题目的含义、所需要的知识，最终确定了问题的解决方案。我们主要是对二叉树中节点所在的层次数进行求解，以及完成二叉树在现实生活中的具体

应用实例的设计，虽然同为二叉树的内容，但是具体方面有些差异，所以经过小组讨论分工以共同努力努力完成了课程设计。

通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。 总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。