Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 590????Accepted Submission(s): 241
?? 本題如果學過數(shù)據(jù)結(jié)構(gòu)的話，應(yīng)該問題不大，就是給一個先序遍歷，一個中序遍歷，求后序遍歷，一般我們做的時候就是根據(jù)先序遍歷和中序遍歷建造一個樹，然后再對這個樹進行后序遍歷輸出就行了。后序遍歷樹很簡單，我們就不多說了，關(guān)鍵是怎樣建樹。首先我們應(yīng)該搞清楚先序遍歷和中序遍歷，在中序遍歷中如果這個數(shù)出現(xiàn)在某個節(jié)點的前面就表明此數(shù)在這個節(jié)點的左邊，如果這個數(shù)出現(xiàn)在某個節(jié)點的后面就表明此數(shù)出現(xiàn)在這個節(jié)點的右邊。
代碼：
?
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號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
