面向对象核心概念-Java实验三.docx

广东工业大学实验报告
_____自动化______学院_11_网络工程__专业__3___ 班 学号_3111001381 姓名__何宇航____ 成绩评定_______
实验__三__题目_____面向对象核心概念____________________________ 课程名称 Java与面向对象程序设计
一．实验目的
掌握Java的面向对象核心概念。
二．实验软件环境
Oracle Netbeans IDE 7
三．实验内容
1．（必做）编程题：由数据结构可知，已知一棵二叉树的前序和中序遍历序列，则可以唯一还原出一棵二叉树请编写一个Java的GUI程序，要达到以下两个目标：
A．在界面上有两个输入框，分别接受前序和中序的字符串输入（用大写字母表示树中结点），有一个按钮Run，按下之后在一个Label处显示出该二叉树的后序序列。
B．在A的基础上，把二叉树用一种可视化的方式画出来。如：

以上“可视化”的二叉树是程序根据你所输入的前序和中序列自动生成的，可以考虑自己编程实现，也可以考虑使用现成的Java Tree控件。请自行在互联网上查找可用的实现。

2．（必做）设计题：请设计一组类、类的继承层次和接口，对上述的可视化二叉树进行封装，然后用该封装好的可视化二叉树模块来展示一个堆排序的过程和一个哈夫曼树的构造过程。本题的重点是对可视化二叉树进行设计和包装，然后再设计一个堆排序的类和一个哈夫曼树的类，若两者都能使用同一个可视化的二叉树类（或其子类），那你的设计就是成功的了。
请给出框架性代码（类定义、方法定义、成员变量定义），界面设计，方法调用序列，以及必要的文字和图表说明来细化你的设计。
四．实验的结果及分析
1、前序后序字符串生成程序：
程序的设计思路：
程序包含一个节点类（BiTreeNode）和一个树类（BiTree），前序遍历字符串储存为一个队列，中序遍历字符串储存为一个字符串。根据二叉树的Top-down递归构造过程，树的生成叫由节点递归进行，前序字符串队列在每生成一个节点后就将该节点出队而中序字符串则会以该节点的字符进行二分。

BiTreeNode类成员一览：

主要类成员说明：
strLeftSubTree对象和strRightSubTree对象：分别是左右子树的中序历遍字符串。
构造方法：
private BiTreeNode(String strOriTree, final BiTreeNode btnParent, String strInputedNodeData) {
this.btnRoot = btnParent;
String[] strArrSplited = strOriTree.split(strInputedNodeData, 2); //局限：不能识别重复的元素
this.strLeftSubTree = strArrSplited[0];
this.strNodeData = strInputedNodeData;
this.strRightSubTree = strArrSplited[1];
}
btnNewNode方法：改方法调用类的构造方法，返回新的节点，并对节点进行计数。

public static BiTreeNode btnNewNode(String strOriTree, final BiTreeNode btnParent, String strInputedNodeData) {
BiTreeNode btnNewNode = new BiTreeNode(strOriTree, btnParent, strInputedNodeData);
intNodesNum++; //节点计数
return btnNewNode;
}

isFind方法：在字符串中查找队列首个元素，并返回布尔值结果。
private static boolean isFind(String strInputed, final LinkedList queInputed) {
if(queInputed.isEmpty()) {
return false;
}
else if(strInputed.indexOf(queInputed.peek()) == -1) {
return false;
}
else {
return true;
}
}

GenerateSubTree方法：由上自下递归创建子树。
public void GenerateSubTree(LinkedList quePreorder) {

BiTreeNode btnSubNode;

if(BiTreeNode.isFind(this.strLeftSubTree, quePreorder)) { //weird 不能用matches
btnSubNode = BiTreeNode.btnNewNode(this.strLeftSubTree, this, quePreorder.poll());
this.btnLeftChild = btnSubNode;
btnSubNode.GenerateSubTree(quePreorder);
}
if(BiTreeNode.isFind(this.strRightSubTree, quePreorder)) {
btnSubNode = BiTreeNode.btnNewNode(this.strRightSubTree, this, quePreorder.poll());
this.btnRightChild = btnSubNode;
btnSubNode.GenerateSubTree(quePreorder);
}
}
BiTree类成员一览：

主要类成员说明：
quePreOrder对象和strMidOrder对象：分别以队列形式和字符串形式存放树的前序和中序字符串。
StringToQueue静态方法：将输入的前序转换串转换为队列。
private static LinkedList StringToQueue(String strInputedPreOrder) {
LinkedList queOutput = new LinkedList();
for(char c : strInputedPreOrder.toCharArray()) {
queOutput.add(String.valueOf(c));
}
return queOutput;
}
程序测试：
输入前序字符串：ABDEGHJCFI
输入中序字符串：DBGEHJACIF

运行情况：
【第一步】
由后序遍历的最后一个节点可知本树根节点为【A】
加上中序遍历的结果，得知以【A】为根节点时，中序遍历结果被【A】分为两部分【DBGEHJ】【A】【CIF】
于是作出第一幅图如下

【第二步】
将已经确定了的节点从后序遍历结果中分割出去
即【DGJHEBIFC】---【A】
此时，位于后序遍历结果中的最后一个值为【C】
说明节点【C】是某棵子树的根节点
又由于【第一步】中【C】处于右子树，因此得到，【C】是右子树的根节点
于是回到中序遍历结果【DBGEHJ】【A】【CIF】中来，在【CIF】中，由于【C】是根节点，所以【IF】都是这棵子树的右子树，【CIF】子树没有左子树，于是得到下图

【第三步】
将已经确定了的节点从后序遍历中分割出去
即【DGJHEBIF】---【CA】
此时，位于后序遍历结果中的最后一个值为【F】
说明节点【F】是某棵子树的根节点
又由于【第二步】中【F】处于右子树，因此得到，【F】是该右子树的根节点
于是回到中序遍历结果【DBGEHJ】【A】【C】【IF】中来，在【IF】中，由于【F】是根节点，所以【I】是【IF】这棵子树的左子树，于是得到下图

【第四步】
将已经确定了的节点从后序遍历中分割出去
即【DGJHEB】---【IFCA】
此时，位于后序遍历结果中的最后一个值为【B】
说明节点【B】是某棵子树的根节点
又由于【第一步】中【B】处于【A】的左子树，因此得到B】是该左子树的根节点
于是回到中序遍历结果【DBGEHJ】【A】【C】【F】【I】中来，根据【B】为根节点，可以将中序遍历再次划分为【D】【B】【GEHJ】【A】【C】【F】【I】，于是得到下图

【第五步】
将已经确定了的节点从后序遍历中分割出去
即【DGJHE】---【BIFCA】
此时，位于后序遍历结果中的最后一个值为【E】
说明节点【E】是某棵子树的根节点
又由于【第四步】中【E】处于【B】的右子树，因此得到，【E】是该右子树的根节点
于是回到中序遍历结果【D】【B】【GEHJ】【A】【C】【F】【I】中来，根据【B】为根节点，可以将中序遍历再次划分为【D】【B】【G】【E】【HJ】【A】【C】【F】【I】，于是得到下图

【第六步】
将已经确定了的节点从后序遍历中分割出去
即【DGJH】---【EBIFCA】
此时，位于后序遍历结果中的最后一个值为【H】
说明节点【H】是某棵子树的根节点
又由于【第五步】中【H】处于【E】的右子树，因此得到，【H】是该右子树的根节点
于是回到中序遍历结果【D】【B】【G】【E】【HJ】【A】【C】【F】【I】中来，根据【H】为根节点，可以将中序遍历再次划分为【D】【B】【G】【E】【H】【J】【A】【C】【F】【I】，于是得到下图

至此，整棵二叉树已经还原。
2、树设计题:
设计思想
本方案设计了实现同一个接口的两种节点，一棵可以容纳该接口的树。由于哈夫曼树是自底向上生成，而堆排序树是自顶向下生成的，因此通用的树节点接口两种方法都声明了。但是，当实现改接口方法的时候，则每两种节点均实现其中一种方法，另外一个空实现。另外，根据两种节点的输入还设计实现了同一接口的两种输入类。

方案的组成：

主要类和接口间的关系：

节点递归生成子树方法调用序列：
这里给出框架性代码：
1、 堆排序树的：
public void GenerateSubTreeFromTop(Input info) {
this.HeapSort); //堆排序方法
this.tnLeftChild.GenerateSubTreeFromTop(info);
this.tnRightChild.GenerateSubTreeFromTop(info);
}
2、 哈夫曼树的：
public void GenerateSubTreeFromBottom(Input info) {
this.Coding(); //哈夫曼编码方法
this.tnLeftChild.GenerateSubTreeFromTop(info);
this.tnRightChild.GenerateSubTreeFromTop(info);
}
关于Input接口：
Input接口及其实现的包含必须的数据成员的方法，只要将一对前序和中序遍历字符串输入到该接口，就可以得出树生成时所需要的信息。
五．实验心得体会
通过这一次实验，我进一步地了解了Java编程语言，对Java的面向对象的设计方法也有了一定的了解。
9