15_Рекурсивная процедура обхода дерева

1. Рекурсивная процедура обхода дерева

1

2.

Главная программа. Раздел описания
const
s= 0 ;
признак конца последовательности
type
point = ^node;
node = record
a: integer;
l, r: point
end;
var
i, n: integer; n - очередное число,
i –номер строки memo1
r2: point;
r2 – дерево
2

3. Главная программа Создание корня и ввод n

begin
1 i:=0;
2 r2:= nil;
3 n:=strtoint(memo1.Lines[0]);
4 if n <> s then begin
5
new (r2);
6
with r2^ do begin
7
a:= n;
8
l:= nil;
9
r:=nil
10
end;
11 i:=i+1;
12 n:=strtoint(memo1.Lines[i]);
3

4. Главная программа

Цикл вставки элементов последовательно в
непустое дерево
13 while n <> s do begin
14
vstavka (r2, n);
15
i:=i+1;
16
n:=strtoint(memo1.Lines[i]);
17
end
(* while *)
18 end;
(* if *)
Дерево сформировано. Обход дерева и
вывод хранящихся в узлах чисел
19 rod (r2)
20 end;
4

5. Процедура obxod

procedure obxod (r1:point);
const limit=100;
var this: point;
no : 0 .. limit; no - номер адреса
adr: array [1..limit] of point; массив адресов
begin
1 this:=r1;
2 no:= 0 ;
3 while (this <> nil) or (no <> 0 ) do begin
4
if this <>nil then begin
5
no:= no + 1;
6
adr [no]:= this;
7
this:= this^.l
8
end
(* then *)
9
else begin
10
this:=adr [no];
11
no:=no-1;
12
Memo1.Lines.Add(inttostr(this^.a));
13
this:=this^.r
14
end
(* else *)
15
end
(* while *)
16 end;
5

6. Рекурсивная процедура обхода дерева

1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l); 1 рекурсивный вызов
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r); 2 рекурсивный вызов
7 end;
8 end;
6

7.

Если дерево не пусто, процедура порождает
помощника - свою копию – и посылает его для обхода левого
поддерева, сама же остается ждать. Помощник вернулся процедура выводит значение из корневого узла, порождает
нового помощника и посылает его по правому поддереву.
Дождавшись его возвращения, процедура завершает работу.
Так происходит на каждом уровне вызова.
Таким образом, во время обхода дерева одновременно
существует несколько копий процедуры, из которых одна
активна (проверяет дерево на пустоту, порождает новую
копию или выводит значение), а все остальные пассивны –
ждут завершения работы порожденных ими копий. В каждой
из них параметр R1 имеет свое значение и указывает на
корень того поддерева, которое поручено обойти данной
копии. Тем самым адреса разветвлений запоминаются
автоматически.
7

8.

r1
1 вызов
r1^.l
1 вызов rod(r1)
r1^.r
5
r1^.l^.l
r1^.r^.r
r1^.l^.r
3
r1^.r^.l
r1^.l^.l^.r
.
2
r1^.l^.l^.l
.
.
r1^.l^.r^.l
4
.
r1^.l^.r^.r
. 7
.
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
8

9.

2 вызов
1 вызов rod(r1)
2 вызов rod(r1^.l)
r1^.l
3 вызов rod(r1^.l^.l)
r1^.l^.l
3
.
2
.
.
4
.
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
9

10.

1 вызов rod(r1)
3 вызов
2 вызов rod(r1^.l)
r1^.l^.l
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
r1^.l^.l^.l
.
2
.
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
10

11.

1 вызов rod(r1)
4 вызов
r1^.l^.l^.l
.
2 вызов rod(r1^.l)
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7 end;
8 end;
11

12.

1 вызов rod(r1)
3 вызов
2 вызов rod(r1^.l)
r1^.l^.l
3 вызов rod(r1^.l^.l)
r1^.l^.l^.a
.
r1^.l^.l^.r
2
.
4 вызов rod(r1^.l^.l^.l)
5 вызов rod(r1^.l^.l^.r)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
12

13.

1 вызов rod(r1)
5 вызов
2 вызов rod(r1^.l)
r1^.l^.l^.r
.
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
5 вызов rod(r1^.l^.l^.r)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
13

14.

2 вызов
1 вызов rod(r1)
2 вызов rod(r1^.l)
r1^.l
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
r1^.l^.a
3
5 вызов rod(r1^.l^.l^.r)
r1^.l^.r
6 вызов rod(r1^.l^.r)
.
2
.
.
4
.
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
14

15.

6 вызов
1 вызов rod(r1)
2 вызов rod(r1^.l)
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
r1^.l^.r
5 вызов rod(r1^.l^.l^.r)
6 вызов rod(r1^.l^.r)
.
r1^.l^.r^.l
4
.
7 вызов rod(r1^.l^.r^.l)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
15

16.

1 вызов rod(r1)
7 вызов
2 вызов rod(r1^.l)
r1^.l^.r^.l
.
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
5 вызов rod(r1^.l^.l^.r)
6 вызов rod(r1^.l^.r)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
7 вызов rod(r1^.l^.r^.l)
16

17.

6 вызов
1 вызов rod(r1)
2 вызов rod(r1^.l)
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
5 вызов rod(r1^.l^.l^.r)
r1^.l^.r
6 вызов rod(r1^.l^.r)
r1^.l^.r^.r
.
4
r1^.l^.r^.a
7 вызов rod(r1^.l^.r^.l)
.
1
2
3
4
5
6
7
8
8 вызов rod(r1^.l^.r^.r)
procedure rod(r1:point);
begin
if r1<>nil then begin
rod(r1^.l);
memo1.Lines.Add(inttostr(r1^.a));
rod(r1^.r);
end;
17
end;

18.

1 вызов rod(r1)
8 вызов
2 вызов rod(r1^.l)
r1^.l^.r^.r
.
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
5 вызов rod(r1^.l^.l^.r)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
6 вызов rod(r1^.l^.r)
7 вызов rod(r1^.l^.r^.l)
8 вызов rod(r1^.l^.r^.r)
18

19.

r1
1 вызов
r1^.a
r1^.l
r1^.r
1 вызов rod(r1)
2 вызов rod(r1^.l)
3 вызов rod(r1^.l^.l)
5
4 вызов rod(r1^.l^.l^.l)
.
3
7
.
5 вызов rod(r1^.l^.l^.r)
6 вызов rod(r1^.l^.r)
.
2
.
.
4
.
7 вызов rod(r1^.l^.r^.l)
8 вызов rod(r1^.l^.r^.r)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
9 вызов rod(r1^.r)
19

20.

9 вызов
1 вызов rod(r1)
r1^.r
2 вызов rod(r1^.l)
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
r1^.r^.l
. 7
.
5 вызов rod(r1^.l^.l^.r)
6 вызов rod(r1^.l^.r)
7 вызов rod(r1^.l^.r^.l)
8 вызов rod(r1^.l^.r^.r)
9 вызов rod(r1^.r)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
10 вызов rod(r1^.r^.l)
20

21.

10 вызов
1 вызов rod(r1)
r1^.r^.l
.
2 вызов rod(r1^.l)
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
5 вызов rod(r1^.l^.l^.r)
6 вызов rod(r1^.l^.r)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
7 вызов rod(r1^.l^.r^.l)
8 вызов rod(r1^.l^.r^.r)
9 вызов rod(r1^.r)
10 вызов rod(r1^.r^.l)
21

22.

9 вызов
1 вызов rod(r1)
r1^.r
2 вызов rod(r1^.l)
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
5 вызов rod(r1^.l^.l^.r)
6 вызов rod(r1^.l^.r)
7 вызов rod(r1^.l^.r^.l)
8 вызов rod(r1^.l^.r^.r)
9 вызов rod(r1^.r)
10 вызов rod(r1^.r^.l)
11 вызов rod(r1^.r^.r)
. 7
.
r1^.r^.r
r1^.r^.a
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
22

23.

1 вызов rod(r1)
11 вызов
r1^.r^.r
.
2 вызов rod(r1^.l)
3 вызов rod(r1^.l^.l)
4 вызов rod(r1^.l^.l^.l)
5 вызов rod(r1^.l^.l^.r)
1 procedure rod(r1:point);
2 begin
3
if r1<>nil then begin
4
rod(r1^.l);
5
memo1.Lines.Add(inttostr(r1^.a));
6
rod(r1^.r);
7
end;
8 end;
6 вызов rod(r1^.l^.r)
7 вызов rod(r1^.l^.r^.l)
8 вызов rod(r1^.l^.r^.r)
9 вызов rod(r1^.r)
10 вызов rod(r1^.r^.l)
11 вызов rod(r1^.r^.r)
23