forked from xurui1995/Sword-pointing-to-offer
-
Notifications
You must be signed in to change notification settings - Fork 0
/
No06.java
87 lines (68 loc) · 1.49 KB
/
No06.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
public class No06 {
/**
* 根据前序遍历和中序遍历建立树
*/
public static void main(String[] args) {
String preOrder="12473568";
String midOrder="47215386";
BiTree tree=new BiTree(preOrder, midOrder, preOrder.length());
tree.postRootTraverse(tree.root);
}
}
class BiTree{
TreeNode root;
public BiTree(String preOrder,String midOrder,int count){
if(count<=0){
return;
}
char c=preOrder.charAt(0);
int i=0;
for(;i<count;i++){
if(midOrder.charAt(i)==c)
break;
}
root=new TreeNode(c);
root.setLchild(new BiTree(preOrder.substring(1,i+1), midOrder.substring(0,i), i).root);
root.setRchild(new BiTree(preOrder.substring(i+1), midOrder.substring(i+1), count-i-1).root);
}
public void postRootTraverse(TreeNode root) {
if(root!=null){
postRootTraverse(root.getLchild());
postRootTraverse(root.getRchild());
System.out.print(root.getData());
}
}
}
class TreeNode{
char data;
TreeNode Lchild;
TreeNode Rchild;
public TreeNode(char data) {
super();
this.data = data;
}
public TreeNode(char data, TreeNode lchild, TreeNode rchild) {
super();
this.data = data;
Lchild = lchild;
Rchild = rchild;
}
public char getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public TreeNode getLchild() {
return Lchild;
}
public void setLchild(TreeNode lchild) {
Lchild = lchild;
}
public TreeNode getRchild() {
return Rchild;
}
public void setRchild(TreeNode rchild) {
Rchild = rchild;
}
}