首页 > 试题广场 >

[问题描述]求一棵树的深度与宽度。 [算法说明]树可用数组t

[填空题]
[问题描述]求一棵树的深度与宽度。
[算法说明]树可用数组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__________1_________do
     begin
       p:=g[sp1, 2];
       n2 := g[sp1, 3];
       _________2________;
       j := 4;
       while _________3_________do
         begin
           n1:=g[sp1, j];
           j := j + 1;
           __________4_________;
           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;
       __________5_________;
     end;
     writeln('maxd=',g[sp2, 2]); j:=1; k:=g[1, 2]; jmax:=0;
     for i:=2 to sp2 do
       if __________6__________then j:=j+1
       else
         begin
           if j>jmax then jmax:=j;
           __________7________; k:=g[i, 2];
         end;
   if j>jmax then jmax:=j;
   writeln('max1=',jmax);
 end.

这道题你会答吗?花几分钟告诉大家答案吧!