已经中序，后序，求先序。
先序的顺序为：先根节点，后左子树，后右子树。
|
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
|
package
whut.tree;
//利用java api来进行遍历
////已知二叉树后序和中序，求先序
public
class
MiddleAfterTree {
//全局变量存放后序序列
//先写根，后写左子树，最后写右子树
public
static
String res =
""
;
//两个字符串是否包含了相同的字符
public
static
boolean
StringEquals(String a1, String a2) {
boolean
state =
true
;
if
(a1.length() != a2.length()) {
state =
false
;
}
if
(a1.length() == a2.length()) {
for
(
int
i =
0
; i < a1.length(); i++) {
if
(a2.indexOf(a1.charAt(i)) == -
1
)
state =
false
;
}
}
return
state;
}
//进行遍历输出
//参数依此为中序序列，后序序列
public
static
void
cal_tree(String smid, String slast) {
boolean
state = StringEquals(smid, slast);
if
(state ==
false
)
return
;
if
(smid.length() ==
0
)
return
;
//每次添加都是添加中序的字符，当中序字符串长度为1的时候，就返回
if
(smid.length() ==
1
) {
res += smid;
return
;
}
//后序序列中最后一个就是根
char
root = slast.charAt(slast.length()-
1
);
//获取字符在中序序列总的位置
//mid代表的是索引
int
mid = smid.indexOf(root);
//中序序列的左子树
String c=smid.substring(
0
, mid);
//中序序列的右子树
String d = smid.substring(mid+
1
);
//写入根
res += String.valueOf(root);
//中序左子树，后序左子树
cal_tree(c,slast.substring(
0
, c.length()));
//中序右子树，后序右子树,注意这里后序的右子树要最大为slast.length()-1
cal_tree(d,slast.substring(c.length(),slast.length()-
1
));
return
;
}
public
static
void
main(String[] agrs) {
//cal_tree("ADEFGHMZ","AEFDHZMG");=GDAFEMHZ
//cal_tree("CDBEAGF","DCEBGFA");=ABCDEFG
String s1 =
"ADEFGHMZ"
;
String s2 =
"AEFDHZMG"
;
cal_tree(s1, s2);
if
(res.length() != s1.length())
{
System.out.println(
"wrong tree list!"
);
}
else
{
System.out.println(res);
}
}
}
|
本文转自 zhao_xiao_long 51CTO博客，原文链接:http://blog.51cto.com/computerdragon/1305991
