[问题描述]求一棵树的深度与宽度。共15分(2+2+3+2+2+2+2=15分)
[算法说明]树可用数组tree:array[1..n,1..5]of integer;
其中:tree[I,1]表示结点号;tree[I,2]——tree[I,5]所属结点
如上图可表示为:
1 2 3 4 0
2 5 6 7 0
3 8 0 0 0
4 9 10 0 0
5 0 0 0 0
6 0 0 0 0
7 11 12 0 0
8 0 0 0 0
9 0 0 0 0
10 0 0 0 0
11 0 0 0 0
12 13 0 0 0
13 0 0 0 0
在求解的过程中,用到数组G:ARRAY[1..N,1..7]OF INTEGER;
其中:G[I,1]表示父结点,G[I,2]表示层次,
G[I,3]表示本结点号,G[I,4]——G[I,7]表示子女结点;
同时,设2个指针SP1(取数指针),SP2(存数指针)
program exGp3;
const n=13;
var i,j,k,sp1,sp2,n1,n2,jmax,p:integer;
tree:array[1..n,1..5]of integer;
g:array[1..n,1..7]of integer;
begin
for i:=1 to n do
begin
tree[i,1]:=i;
for j:=2 to 5 do read (tree[i,j]);readln;
end;
sp1:=1;sp2:=1;g[1,1]:=0;g[1,2]:=1;g[1,3]:=1;
for i:=4 to 7 do g[1,i]:=tree[1,i-2];
while sp1<=sp2 do
begin
p:=g[sp1,2];n2:=g[sp1,3]; p:=p+1 ;j:=4;
while g[sp1,j]<>0 do
begin
n1:=g[sp1,j];j:=j+1; sp2:=sp2+1 ;
g[sp2,1]:=n2;g[sp2,2]:=p;g[sp2,3]:=n1;
for i:=1 to 4 do g[sp2,i+3]:=tree[n1,i+1];
end;
sp1:=sp1+1 ;
end;
writeln('maxd=',g[sp2,2]); j:=1;k:=g[1,2];jmax:=0;
for i:=2 to sp2 do
if k=g[i,2] then j:=j+1
else begin
if j>jmax then jmax:=j;
j:=1 ;k:=g[I,2];
end;
if j>jmax then jmax:=j;
writeln('max1=',jmax);
end.