Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 590????Accepted Submission(s): 241
?? 本題如果學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的話，應(yīng)該問(wèn)題不大，就是給一個(gè)先序遍歷，一個(gè)中序遍歷，求后序遍歷，一般我們做的時(shí)候就是根據(jù)先序遍歷和中序遍歷建造一個(gè)樹(shù)，然后再對(duì)這個(gè)樹(shù)進(jìn)行后序遍歷輸出就行了。后序遍歷樹(shù)很簡(jiǎn)單，我們就不多說(shuō)了，關(guān)鍵是怎樣建樹(shù)。首先我們應(yīng)該搞清楚先序遍歷和中序遍歷，在中序遍歷中如果這個(gè)數(shù)出現(xiàn)在某個(gè)節(jié)點(diǎn)的前面就表明此數(shù)在這個(gè)節(jié)點(diǎn)的左邊，如果這個(gè)數(shù)出現(xiàn)在某個(gè)節(jié)點(diǎn)的后面就表明此數(shù)出現(xiàn)在這個(gè)節(jié)點(diǎn)的右邊。
代碼：
?
1
#include
<
stdio.h
>
2
#include
<
stdlib.h
>
3
?
int
n,pre[
1005
],
in
[
1005
];
4
typedef
struct
node
5
{
6
int
data;
7
int
index;
8
struct
node
*
Lchild,
*
Rchild;
9
}bitree,
*
Tree;
10
?
void
dfs(Tree
&
root,
int
index)
11
{
12
if
(root
==
NULL)
13
{
14
root
=
(Tree)malloc(
sizeof
(bitree));
15
root
->
data
=
in
[index];
16
root
->
index
=
index;
17
root
->
Lchild
=
NULL;
18
root
->
Rchild
=
NULL;
19
return
;
20
}
21
else
22
{
23
if
(index
<
root
->
index)
24
dfs(root
->
Lchild,index);
25
else
26
dfs(root
->
Rchild,index);
27
}
28
}
29
void
createbitree(Tree
&
root)
30
{
31
int
i,j,index;
32
root
=
(Tree)malloc(
sizeof
(bitree));
33
for
(i
=
1
;i
<=
n;i
++
)
34
if
(
in
[i]
==
pre[
1
])
35
{
36
root
->
data
=
pre[
1
];
37
root
->
index
=
i;
38
root
->
Lchild
=
NULL;
39
root
->
Rchild
=
NULL;
40
break
;
41
}
42
index
=
i;
43
for
(i
=
2
;i
<=
n;i
++
)
44
for
(j
=
1
;j
<=
n;j
++
)
45
if
(
in
[j]
==
pre[i])
46
{
47
if
(j
<
index)
48
dfs(root
->
Lchild,j);
49
else
50
dfs(root
->
Rchild,j);
51
break
;
52
}
53
}
54
void
post(Tree root,
int
x)
55
{
56
if
(root
==
NULL)
57
return
;
58
post(root
->
Lchild,x
+
1
);
59
post(root
->
Rchild,x
+
1
);
60
if
(x
==
0
)
61
printf(
"
%d
"
,root
->
data);
62
else
63
printf(
"
%d
"
,root
->
data);
64
}
65
int
main()
66
{
67
int
i;
68
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
69
{
70
Tree root;
71
for
(i
=
1
;i
<=
n;i
++
)
72
scanf(
"
%d
"
,
&
pre[i]);
73
for
(i
=
1
;i
<=
n;i
++
)
74
scanf(
"
%d
"
,
&
in
[i]);
75
createbitree(root);
76
post(root,
0
);
77
printf(
"
\n
"
);
78
}
79
return
0
;
80
}
81
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
