-
Notifications
You must be signed in to change notification settings - Fork 0
/
Tree.java
executable file
·113 lines (100 loc) · 3.71 KB
/
Tree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package BFS;
import java.util.ArrayList;
public class Tree implements Cloneable{
String root = null;
Tree lefTree, rigTree;
public Tree() {
}
public Tree(String root){
this.root = root;
}
public void buildTree(ArrayList<String> ope,Tree tree) throws CloneNotSupportedException {
if (ope.size()==0) {
return;
}
Tree tree1 = (Tree) tree.clone();
Tree tree2 = (Tree) tree.clone();
tree1.root=ope.get(0);
tree2.root=ope.get(0);
ope.remove(0);
buildTree(ope, tree1.lefTree);
buildTree(ope, tree2.rigTree);
}
//read sequence: inOrder
public static void inOrder(Tree currentNode) {
if (currentNode != null && currentNode.lefTree != null && currentNode.rigTree != null) {
System.out.print("(");
inOrder(currentNode.lefTree);
System.out.print(currentNode.root + "");
inOrder(currentNode.rigTree);
System.out.print(")");
}
else {
System.out.print(currentNode.root);
}
}
//read whole tree
public static String treeToStr(Tree currentNode, String tree) {
if (currentNode != null && currentNode.lefTree != null && currentNode.rigTree != null) {
if (currentNode.root.equals("+")) {
return treeToStr(currentNode.lefTree,tree)+currentNode.root+treeToStr(currentNode.rigTree,tree);
}
else if (currentNode.root.equals("-")) {
if (currentNode.rigTree.root.equals("-")||currentNode.rigTree.root.equals("+")) {
return treeToStr(currentNode.lefTree, tree)+currentNode.root+"("+treeToStr(currentNode.rigTree, tree)+")";
}
else {
return treeToStr(currentNode.lefTree,tree)+currentNode.root+treeToStr(currentNode.rigTree,tree);
}
}
else if (currentNode.root.equals("*")) {
if (currentNode.lefTree.root.equals("+")||currentNode.lefTree.root.equals("-")) {
if (currentNode.rigTree.root.equals("+")||currentNode.rigTree.root.equals("-")) {
return "("+treeToStr(currentNode.lefTree,tree)+")"+currentNode.root+"("+treeToStr(currentNode.rigTree,tree)+")";
}
else{
return "("+treeToStr(currentNode.lefTree,tree)+")"+currentNode.root+treeToStr(currentNode.rigTree,tree);
}
}
else {
if (currentNode.rigTree.root.equals("+")||currentNode.rigTree.root.equals("-")) {
return treeToStr(currentNode.lefTree,tree)+currentNode.root+"("+treeToStr(currentNode.rigTree,tree)+")";
}
else{
return treeToStr(currentNode.lefTree,tree)+currentNode.root+treeToStr(currentNode.rigTree,tree);
}
}
}
else {
if (currentNode.lefTree.root.equals("+")||currentNode.lefTree.root.equals("-")) {
if (currentNode.rigTree.root.equals("+")||currentNode.rigTree.root.equals("-")||currentNode.rigTree.root.equals("*")||currentNode.rigTree.root.equals("/")) {
return "("+treeToStr(currentNode.lefTree,tree)+")"+currentNode.root+"("+treeToStr(currentNode.rigTree,tree)+")";
}
else{
return "("+treeToStr(currentNode.lefTree,tree)+")"+currentNode.root+treeToStr(currentNode.rigTree,tree);
}
}
else {
if (currentNode.rigTree.root.equals("+")||currentNode.rigTree.root.equals("-")||currentNode.rigTree.root.equals("*")||currentNode.rigTree.root.equals("/")) {
return treeToStr(currentNode.lefTree,tree)+currentNode.root+"("+treeToStr(currentNode.rigTree,tree)+")";
}
else{
return treeToStr(currentNode.lefTree,tree)+currentNode.root+treeToStr(currentNode.rigTree,tree);
}
}
}
}
else {
return currentNode.root;
}
}
//read tree just contains operation
static public String ReadInOrder(Tree currentNode){
if (currentNode == null){
return "";
}
else {
return "(" +ReadInOrder(currentNode.lefTree) + currentNode.root + ReadInOrder(currentNode.rigTree) + ")";
}
}
}