主题：问几个问题（＋分）
fxzxg
[专家分：430] 发布于 2006-03-03 13:32:00
1、读入一字符串，表示二叉树（链表）的先序遍历，保证每个非空节点的左右子树都包含在该串中，空树用“*”表示。以此建立二叉树，并输出其中序遍历。
如：读入：ab**cd**e**
树为：
a
/ \
b c
/ \
d e
输出：badce
2、若由a、b承担n个任务。设第i个任务交给a做需ai天，交给b做需bi天。既不能将一任务分开由两个人处理，也没有一人能同时处理两任务。读入n及n个ai、bi，输出最短时间。（二人可并行工作）
如：读入：2
2 3
5 4
解为a先做1，同时b做2，最短时间为4天。
输出：4
回复列表 （共7个回复）
沙发
Benix [专家分：720] 发布于 2006-03-07 14:01:00
第一题
第一个字符肯定是根节点着不用说了吧
剩下的根据叶子与节点的数值关系算出哪些是左子树 哪些是右子树（字符是节点，*是叶子） 然后递归
板凳
fxzxg [专家分：430] 发布于 2006-03-07 14:05:00
这个我知道,可编起来却出现奇怪的问题~~~~~~~~~~~~~
可否给出程序?
3 楼
Benix [专家分：720] 发布于 2006-03-09 13:27:00
先读入一个串 利用叶子比节点多一的规律 去找
这个规律只有在除叶子节点外 其它节点都有两个子树的时候才成立
4 楼
Benix [专家分：720] 发布于 2006-03-09 13:33:00
程序
pro Print(s:string);
int i,l,nw,ns；
{
if s<>'*' then
{
l=length(s)
nw=0 ns=0
for i=2 to l
{
if s[i]='*' then inc(ns) else inc(nw)
if ns-nw=1 then break
}
print(copy(s,2,i-1))
write(s[1])
print(copy(s,i+1,l-i))
}
}
5 楼
fxzxg [专家分：430] 发布于 2006-03-11 15:50:00
program tree;
type point=^node;
node=record
data:char;
lc,rc:point;
end;
var f1,f2:text;
s:point;
c:char;
ch:string;
i:integer;
procedure init;
begin
assign(f1,'tree.in');
reset(f1);
readln(f1,c);
readln(f1,ch);
close(f1);
i:=1;
new(s);
end;
procedure xianj(bt:point);
var p:point;
begin
if i>length(ch)
then bt:=nil
else if ch[i]='*'
then begin
bt:=nil;
i:=i+1;
end
else begin
bt^.data:=ch[i];
i:=i+1;
new(p);
bt^.lc:=p;
xianj(bt^.lc);
new(p);
bt^.rc:=p;
xianj(bt^.rc);
end;
end;
procedure zhongj(bt:point);
var p:point;
begin
if i>length(ch)
then bt:=nil
else if ch[i]='*'
then begin
bt:=nil;
i:=i+1;
end
else begin
new(p);
bt^.lc:=p;
zhongj(bt^.lc);
bt^.data:=ch[i];
i:=i+1;
new(p);
bt^.rc:=p;
zhongj(bt^.rc);
end;
end;
procedure houj(bt:point);
var p:point;
begin
if i>length(ch)
then bt:=nil
else if ch[i]='*'
then begin
bt:=nil;
i:=i+1;
end
else begin
new(p);
bt^.lc:=p;
houj(bt^.lc);
new(p);
bt^.rc:=p;
houj(bt^.rc);
bt^.data:=ch[i];
i:=i+1;
end;
end;
procedure print;
procedure xian(bt:point);
begin
if bt<>nil
then begin
write(f2,bt^.data);
xian(bt^.lc);
xian(bt^.rc);
end;
end;
procedure zhong(bt:point);
begin
if bt<>nil
then begin
zhong(bt^.lc);
write(f2,bt^.data);
zhong(bt^.rc);
end;
end;
procedure hou(bt:point);
begin
if bt<>nil
then begin
hou(bt^.lc);
hou(bt^.rc);
write(f2,bt^.data);
end;
end;
begin
assign(f2,'tree.out');
rewrite(f2);
xian(s);
writeln(f2);
zhong(s);
writeln(f2);
hou(s);
writeln(f2);
close(f2);
end;
begin
init;
case c of
'X':xianj(s);
'Z':zhongj(s);
'H':houj(s);
end;
print;
end.
为什么错？
6 楼
Benix [专家分：720] 发布于 2006-03-14 09:58:00
程序太长+思路不清
如果你的程序能加上注释 会好得多
我看不懂你的程序什么意思
这一题好像没有那么难吧
7 楼
fxzxg [专家分：430] 发布于 2006-03-17 13:26:00
procedure xianj(bt:point);
var p:point;
begin
if i>length(ch)
then bt:=nil
else if ch[i]='*'
then begin
bt:=nil;
i:=i+1;
end
else begin
bt^.data:=ch[i];
i:=i+1;
new(p);
bt^.lc:=p;
xianj(bt^.lc);
new(p);
bt^.rc:=p;
xianj(bt^.rc);
end;
end;
这一部分有错
我来回复
您所在位置：