20202312郭威 实验八 《面向对象程序设计》实验报告
20202312 2021-2022-1 实验八 《树》实验报告
课程:《程序设计与数据结构》
班级: 2023
姓名: 郭威
学号:20202312
实验教师:王志强
实验日期:2021年11月18日
必修/选修: 必修
1.实验内容
1.参考教材PP16.1,完成链树LinkedBinaryTree的实现(getRight,contains,toString,preorder,postorder)
用JUnit或自己编写驱动类对自己实现的LinkedBinaryTree进行测试,提交测试代码运行截图,要全屏,包含自己的学号信息
课下把代码推送到代码托管平台
2.基于LinkedBinaryTree,实现基于(中序,先序)序列构造唯一一棵二?树的功能,比如给出中序HDIBEMJNAFCKGL和后序ABDHIEJMNCFGKL,构造出附图中的树
用JUnit或自己编写驱动类对自己实现的功能进行测试,提交测试代码运行截图,要全屏,包含自己的学号信息
课下把代码推送到代码托管平台
3.自己设计并实现一颗决策树
提交测试代码运行截图,要全屏,包含自己的学号信息
课下把代码推送到代码托管平台
4.输入中缀表达式,使用树将中缀表达式转换为后缀表达式,并输出后缀表达式和计算结果(如果没有用树,正常评分。如果用到了树,即使有小的问题,也酌情给满分)
提交测试代码运行截图,要全屏,包含自己的学号信息
2.实验过程及结果
1.参考教材PP16.1,完成链树LinkedBinaryTree的实现(getRight,contains,toString,preorder,postorder)
用JUnit或自己编写驱动类对自己实现的LinkedBinaryTree进行测试,提交测试代码运行截图,要全屏,包含自己的学号信息
课下把代码推送到代码托管平台
package Week11;
public class BinaryTreeNode {
protected T element;
protected BinaryTreeNode left, right;
public BinaryTreeNode() {
element = null;
left = null;
right = null;
}
public BinaryTreeNode(T element) {
this.element = element;
left = right = null;
}
public BinaryTreeNode getLeft() {
return left;
}
public BinaryTreeNode getRight() {
return right;
}
public T getElement() {
return element;
}
public void setLeft(BinaryTreeNode left) {
this.left = left;
}
public void setRight(BinaryTreeNode right) {
this.right = right;
}
public BinaryTreeNode find(T target) {
BinaryTreeNode result = null;
if (element.equals(target)) return this;
else {
if (left != null) result = left.find(target);
if (right != null) result = right.find(target);
}
return result;
}
public int count() {
int counter = 1;
if (left != null) counter += left.count();
if (right != null) counter += right.count();
return counter;
}
public int level() {
int level = 1, max = 0;
if (left != null) {
max = left.level();
}
if (right != null && right.level() > max) max = right.level();
return level + max;
}
public String IteratorInOrder() {
String s = "";
if (left != null) s += left.IteratorInOrder();
s += this.element.toString() + " ";
if (right != null) s += right.IteratorInOrder();
return s;
}
public String IteratorPreOrder() {
String s = "";
s += this.element.toString() + " ";
if (left != null) s += left.IteratorPreOrder();
if (right != null) s += right.IteratorPreOrder();
return s;
}
public String IteratorPostOrder() {
String s = "";
if (left != null) s += left.IteratorPostOrder();
if (right != null) s += right.IteratorPostOrder();
s += this.element.toString() + " ";
return s;
}
public BinaryTreeNode Insert(char s) {
BinaryTreeNode result = null;
if (left == null) {
left = new BinaryTreeNode(s);
result=left;
}
else if(!left.element.equals('#'))result=left.Insert(s);
if(result==null){
if (right == null) {
right= new BinaryTreeNode(s);
result=right;
}
else if(!right.element.equals('#'))result=right.Insert(s);
}
return result;
}
public void Insert1(String a,String b) {
int i = 0, j;
for (j = 0; b.charAt(j) != a.charAt(i) && j < b.length(); j++) ;
if (left == null) {
if(j!=0) {
left = new BinaryTreeNode(a.charAt(1));
left.Insert1(a.substring(i + 1, j + 1), b.substring(0, j)); }
}
if (right == null) {
if(j!=b.length()-1) {
right = new BinaryTreeNode(a.charAt(j + 1));
right.Insert1(a.substring(j + 1), b.substring(j + 1)); }
}
}
}
package Week11; import java.util.Scanner; public class LinkedBinaryTreeimplements BinaryTreeADT { BinaryTreeNode root; public LinkedBinaryTree(){ root=null; } public LinkedBinaryTree(T element){ root=new BinaryTreeNode(element); } public LinkedBinaryTree(T element,LinkedBinaryTree left,LinkedBinaryTree right){ root=new BinaryTreeNode(element); root.setLeft(left.root); root.setRight(right.root); } @Override public T getRootElement() { if(root==null)return null; return (T) root.element; } @Override public boolean isEmpty() { if(root==null)return true; else return false; } public LinkedBinaryTree getLeft(){ if(root==null)return null; LinkedBinaryTree result = new LinkedBinaryTree(); result.root = root.getLeft(); return result; } public LinkedBinaryTree getRight(){ if(root==null)return null; LinkedBinaryTree result = new LinkedBinaryTree(); result.root = root.getRight(); return result; } public void CreateTree(String s){//前序遍历插入,以#表示空 root=new BinaryTreeNode(s.charAt(0)); for(int i=1;i public void CreateTree1(String a,String b){//通过前序,中序确定一棵树 root=new BinaryTreeNode(a.charAt(0)); root.Insert1(a,b); } public void CreateTree2(){//决策树 String s1="今天吃火锅了吗?"; String s2="点了虾滑和鹌鹑蛋吗?"; String s3="点的是整份吗?"; String s4="今天是不幸的一天。"; String s5="今天是不完整的一天。"; String s6="今天是幸福但不完整的一天。"; String s7="今天是幸福又充实的一天"; BinaryTreeNode n1,n2,n3,n4,n5,n6,n7; n1=new BinaryTreeNode(s1); n2=new BinaryTreeNode(s2); n3=new BinaryTreeNode(s3); n4=new BinaryTreeNode(s4); n5=new BinaryTreeNode(s5); n6=new BinaryTreeNode(s6); n7=new BinaryTreeNode(s7); n1.setLeft(n2); n1.setRight(n4); n2.setLeft(n3); n2.setRight(n5); n3.setLeft(n7); n3.setRight(n6); root=n1; decision(root); } public void decision(BinaryTreeNode root){ Scanner scan=new Scanner(System.in); BinaryTreeNode current=root; while(current.left!=null||current.right!=null){ System.out.print(current.getElement()+"(请输入Y/N): "); if(scan.next().equalsIgnoreCase("y"))current=current.left; else current=current.right; } System.out.println(current.getElement()); } @Override public int size() { if(root==null)return 0; return root.count(); } @Override public int height() { if(root==null)return 0; return root.level(); } @Override public boolean contains(Object target) { if(root==null)return false; T a=(T)target; if(root.find(a)==null)return false; else return true; } @Override public BinaryTreeNode find(Object target) { if(root==null)return null; T a=(T)target; return root.find(a); } @Override public String IteratorInorder() { if(root==null)return null; else return root.IteratorInOrder(); } @Override public String IteratorPreorder() { if(root==null)return null; else return root.IteratorPreOrder(); } @Override public String IteratorPostorder() { if(root==null)return null; else return root.IteratorPostOrder(); } @Override public String IteratorLevel() { String s=""; int i,j,count=1; int t[]=new int[20]; BinaryTreeNode m[]=new BinaryTreeNode [20]; m[0]=root; t[0]=count; for(i=0,j=1,count=2;i!=j;i++){ if(m[i].left!=null){m[j]=m[i].left;t[j]=t[i]+1;j++;} if(m[i].right!=null){m[j]=m[i].right;t[j]=t[i]+1;j++;} s+=m[i].element+" "; if(t[i+1]!=t[i]) s+="\n"; } return s; } public String ToString(){ return root.IteratorPreOrder(); } }){ root.Insert(s.charAt(i)); } }
结果截图
2.基于LinkedBinaryTree,实现基于(中序,先序)序列构造唯一一棵二?树的功能,比如给出中序HDIBEMJNAFCKGL和后序ABDHIEJMNCFGKL,构造出附图中的树
用JUnit或自己编写驱动类对自己实现的功能进行测试,提交测试代码运行截图,要全屏,包含自己的学号信息
课下把代码推送到代码托管平台
package Week11; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; import java.util.StringTokenizer; public class BTtree{ BinaryTreeNode root; public BTtree (){ root=null; } public void CreateTree(String s){ Stack if(s.charAt(i)=='+'||s.charAt(i)=='-'||s.charAt(i)=='*'||s.charAt(i)=='/') op.offer(new BinaryTreeNode(s.charAt(i))); } while(!op.isEmpty()){ temp=op.poll(); if(op.isEmpty()){ temp.left=num.pop(); temp.right=num.pop(); num.push(temp); break; } if(pri(temp.element.toString().charAt(0),op.peek().element.toString().charAt(0))){ temp.left=num.pop(); temp.right=num.pop(); num.push(temp); } else{ temp.left=num.pop(); temp.right=op.peek(); int count=0; while(count==0){ temp1=op.poll(); if(op.isEmpty()){ temp1.left=num.pop(); temp1.right=num.pop(); num.push(temp1); break; } if(pri(temp1.element.toString().charAt(0),op.peek().element.toString().charAt(0))){ temp1.left=num.pop(); temp1.right=num.pop (); count=1; } else{ temp1.left=num.pop(); temp1.right=op.peek(); } } num.push(temp); } } root=num.peek(); } public String IteratorPostorder() { if(root==null)return null; else return root.IteratorPostOrder(); } public boolean pri(char a,char b){ boolean result=true; if(a=='+'||a=='-'){ switch(b){ case '+':result=true;break; case '-':result=true;break; case '*':result=false;break; case '/':result=false;break; default:result=false;break; } } if(a=='*'||a=='/'){ switch(b){ case '+':result=true;break; case '-':result=true;break; case '*':result=true;break; case '/':result=true;break; default:result=false;break; } } return result; } }num= new Stack (); Stack num1= new Stack (); Queue op=new LinkedList (); BinaryTreeNode temp,temp1; StringTokenizer str=new StringTokenizer(s,"+-*/",false); while(str.hasMoreTokens()){num1.push(new BinaryTreeNode(str.nextToken()));} while(!num1.isEmpty()){num.push(num1.pop());} for(int i=0;i ){
3.自己设计并实现一颗决策树
提交测试代码运行截图,要全屏,包含自己的学号信息
课下把代码推送到代码托管平台
4.输入中缀表达式,使用树将中缀表达式转换为后缀表达式,并输出后缀表达式和计算结果(如果没有用树,正常评分。如果用到了树,即使有小的问题,也酌情给满分)
提交测试代码运行截图,要全屏,包含自己的学号信息
package Week11;
import java.util.Stack;
public class Fix {
static Stack op = new Stack<>();
public static Float getv(char op, Float f1, Float f2) {
if (op == '+') return f2 + f1;
else if (op == '-') return f2 - f1;
else if (op == '*') return f2 * f1;
else if (op == '/') return f2 / f1;
else return Float.valueOf(-0);
}
public static float calrp(String rp) {
Stack v = new Stack<>();
char[] arr = rp.toCharArray();
int len = arr.length;
for (int i = 0; i < len; i++) {
Character ch = arr[i];
if (ch >= '0' && ch <= '9') v.push(Float.valueOf(ch - '0'));
else v.push(getv(ch, v.pop(), v.pop()));
}
return v.pop();
}
public static String getrp(String s) {
char[] arr = s.toCharArray();
int len = arr.length;
String out = "";
for (int i = 0; i < len; i++) {
char ch = arr[i];
if (ch == ' ') continue;
if (ch >= '0' && ch <= '9') {
out += ch;
continue;
}
if (ch == '(')
op.push(ch);
if (ch == '+' || ch == '-') {
while (!op.empty() && (op.peek() != '('))
out += op.pop();
op.push(ch);
continue;
}
if (ch == '*' || ch == '/') {
while (!op.empty() && (op.peek() == '*' || op.peek() == '/'))
out += op.pop();
op.push(ch);
continue;
}
if (ch == ')') {
while (!op.empty() && op.peek() != '(')
out += op.pop();
op.pop();
continue;
}
}
while (!op.empty()) out += op.pop();
return out;
}
}
## 3. 实验过程中遇到的问题和解决过程
- 问题1:因为课上时讲的树的内容有限,自己有许多相关知识不是很了解
- 问题1解决方案:自己在网上找一些树的知识进行学习。
## 其他(感悟、思考等)
课程越来越难,但还是需要努力前进
## 参考资料
- [《Java程序设计与数据结构教程(第二版)》](https://book.douban.com/subject/26851579/)
- [《Java程序设计与数据结构教程(第二版)》学习指导](http://www.cnblogs.com/rocedu/p/5182332.html)
- ...