13_Двоичное (бинарное) дерево(часть 1)

1. Двоичное (бинарное) дерево

(часть 1)
1

2.

4
Корень дерева
Левое поддерево
Правое поддерево
7
2
2
6
8
2

3.

Узел 4 называется корнем дерева.
Бинарное
дерево
есть
конечное
множество узлов, которое либо пусто, либо
состоит
из
корня
и
двух
не
пересекающихся
бинарных
деревьев,
называемых
левым
и
правым
поддеревьями данного корня.
Левая
ветвь,
исходящая
из
произвольного узла, ведет в корень левого
поддерева (если оно не пусто), а правая
ветвь – в корень правого поддерева этого
узла.
3

4.

Пример
Программа сортировки (упорядочения)
последовательности натуральных чисел
4276280
в порядке возрастания. Признак конца
последовательности - число 0.
4

5.

Пример
Программа
сортировки
(упорядочения)
последовательности натуральных чисел
4276280
в порядке возрастания. Признак конца последовательности число 0.
Для решения задачи построим бинарное дерево, каждый
узел которого содержит одно из сортируемых чисел и
указатели на левое и правое поддеревья (запись с тремя
полями).
Дерево строится с соблюдением следующих условий:
• все числа в узлах левого поддерева должны быть меньше,
чем в корне;
• а в узлах правого – больше или равны;
• вход в дерево возможен только через корень.
5

6.

4
427628
Корень дерева
2
Каждое число
сравнивается сначала с
корнем!
6

7.

4
427628
2
Корень дерева
7
7

8.

4
427628
Корень дерева
7
2
6
8

9.

4
427628
Корень дерева
7
2
2
6
9

10.

4
427628
Корень дерева
7
2
2
6
8
10

11.

После
построения
дерева
необходимо вывести значения,
хранящиеся в узлах, в таком
порядке:
• сначала все значения из левого
поддерева узла;
• затем значения из самого узла;
• значения из правого поддерева.
11

12.

2
2
4
6
7
8
4
Корень дерева
7
2
2
6
8
12

13.

Каждый узел содержит указатели на
два
поддерева,
т.е.
является
разветвлением. Спускаясь по его левой
ветви, необходимо запомнить адрес
разветвления, чтобы потом вернуться в
узел, напечатать хранящееся в нем
значение, и отправиться по правой
ветви.
Адреса разветвлений запоминаются в
массиве и извлекаются оттуда по
принципу стека: «последним вошел –
первым вышел».
13

14.

1
Схема главной
программы
Начало
2
Создание корня
n – очередное число
r2 - дерево
3
Ввод n
Процедура vstavka
добавляет узел c
числом n в дерево r2
4
Нет
n<>0
Процедура obxod –
обходит дерево r2
(просматривает все
узлы)
Да
5
vstavka(r2,n)
6
Ввод n
7
obxod(r2)
8
Конец
14

15.

r2
4
. 2
.
2
7
.
. 65
.
. 8
.
15

16.

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

17. Главная программа Создание корня и ввод 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]);
17

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

Цикл вставки элементов последовательно в
непустое дерево
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 obxod (r2)
20 end;
18

19.

Главная программа
Создание корня и ввод n
r2^.l
r2
.
4
.
n=4
r2^.r
r2^.a
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;
19

20. Главная программа Ввод n

n=2
i=1
11 i:=i+1;
12 n:=strtoint(memo1.Lines[i]);
20

21. Процедура vstavka

Процедура добавляет к непустому дереву с
корнем r1 узел, хранящий число n1, причем для
каждого узла выполняется условие, что все
значения в левом поддереве меньше, чем в узле,
а в правом не меньше.
procedure vstavka (r1: point; n1:integer);
var
this, predthis: point;
this ищет в дереве пустую ссылку ( только
туда вместо nil можно поместить новые
значения),
predthis хранит адрес узла, в котором эта
ссылка (nil) найдена
21

22. Процедура vstavka

Begin
поиск места для вставки
1 this:=r1;
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
8 new(this); создание нового узла
9 with this^ do begin
10
a:= n1;
11
l:= nil;
12
r:= nil;
13 end;
привязка нового узла к дереву
14
if n1 < predthis^. a then
15
predthis^ .l:= this
16
else predthis^.r:= this
end;
22

23.

Процедура
vstavka
this
r1
.
4
n1=2
.
predthis
1 this:=r1;
2 while this <> nil do begin
3
predthis:=this;
23

24.

Процедура
vstavka
this^.l
.
.
this
r1
4
this^.a
.
n1=2
predthis
this^.r
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
24

25.

Процедура
vstavka
this
.
r1
.
4
.
n1=2
predthis
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
25

26.

Процедура
vstavka
r1
predthis^.l
this
n1=2
predthis^.a
4
.
predthis
predthis^.r
. 2
.
8 new(this);
9 with this^ do begin
10
a:= n1;
11
l:= nil;
12
r:= nil;
13 end;
привязка нового узла к дереву
14
if n1 < predthis^. a then
15
predthis^ .l:= this
16
else predthis^.r:= this
26

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

n=7
i=2
Главная программа
Цикл вставки элементов последовательно в
непустое дерево
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 *)
27

28.

Процедура
vstavka
r1
this
. 2
4
n1=7
.
predthis
.
1 this:=r1;
2 while this <> nil do begin
3
predthis:=this;
28

29.

Процедура
vstavka
this
r1
this^.l
.
n1=7
this^.a
4
.
predthis
this^.r
. 2
.
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
29

30.

Процедура
vstavka
this
. 2
r1
.
4
.
n1=7
predthis
.
1 this:=r1;
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
30

31.

Процедура
vstavka
n1=7
r1
predthis^.l
predthis^.a
4
predthis
predthis^.r
this
. 2
.
this^.l
. 7
.
this^.a
this^.r
8 new(this);
9 with this^ do begin
10
a:= n1;
11
l:= nil;
12
r:= nil;
13 end;
привязка нового узла к дереву
14
if n1 < predthis^. a then
15
predthis^ .l:= this
16
else predthis^.r:= this
31

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

n=6
i=3
Главная программа
Цикл вставки элементов последовательно в
непустое дерево
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 *)
32

33.

Процедура
vstavka
this^.a
this
. 2
n1=6
r1
this^.r
4
.
predthis
. 7
.
1 this:=r1;
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
33

34.

Процедура
vstavka
n1=6
r1
this^.l
this
this^.a
4
predthis
this^.r
. 2
.
. 7
.
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
34

35.

Процедура
vstavka
n1=6
r1
4
. 2
.
predthis
. 7
.
this
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
35

36.

Процедура
vstavka
n1=6
r1
4
. 2
.
predthis
. 7
.
this
2 while this <> nil do begin
3
predthis:=this;
36

37.

Процедура
vstavka
n1=6
r1
4
predthis
this^.a
. 2
.
this^.l
. 7
.
this
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
37

38.

Процедура
vstavka
n1=6
r1
4
. 2
.
predthis
. 7
.
.
this
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
38

39.

Процедура
vstavka
r1
n1=6
4
predthis
predthis^.a
. 2
.
8 new(this);
9 with this^ do begin
10
a:= n1;
11
l:= nil;
12
r:= nil;
13 end;
привязка нового узла к дереву
14
if n1 < predthis^. a then
15
predthis^ .l:= this
16
else predthis^.r:= this
predthis^.l
7
.
this
this^.l
. 6
.
this^.r
this^.a
39

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

n=2
i=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 *)
40

41.

Процедура
vstavka
r1
n1=2
this^.a
this
4
predthis
this^.l
. 2
.
1 this:=r1;
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
7
. 6
.
.
41

42.

Процедура
vstavka
r1
n1=2
this
4
predthis
this^.l
. 2
.
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
7
. 6
.
.
42

43.

Процедура
vstavka
r1
n1=2
4
. 2
predthis
.
7
.
this
. 6
.
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
43

44.

Процедура
vstavka
r1
n1=2
4
predthis
. 2
.
7
.
this
. 6
.
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
44

45.

Процедура
vstavka
r1
n1=2
4
predthis
. 2
.
7
.
this
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
. 6
.
45

46.

Процедура
vstavka
r1
4
predthis
this
n1=2
. 2
.
this^.a
this^.r
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
7
. 6
.
.
46

47.

Процедура
vstavka
r1
4
predthis
.
n1=2
. 2
.
7
.
this
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
. 6
.
47

48.

Процедура
vstavka
r1
predthis
4
predthis^.a
this
. 2
.
n1=2
2
this^.l this^.a
. this^.r
predthis^.r
7
. 6
.
.
8 new(this);
9 with this^ do begin
10
a:= n1;
11
l:= nil;
12
r:= nil;
13 end;
привязка нового узла к дереву
14
if n1 < predthis^. a then
15
predthis^ .l:= this
16
else predthis^.r:= this
48

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

n=8
i=5
Главная программа
Цикл вставки элементов последовательно в
непустое дерево
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 *)
49

50.

Процедура
vstavka
n1=8
r1
this^.l
this^.r
this
predthis
4
this^.a
. 2
.
2
.
7
. 6
1 this:=r1;
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7
end;
.
.
50

51.

Процедура
vstavka
n1=8
r1
this^.l
this^.r
this
predthis
4
this^.a
. 2
.
2
.
7
. 6
.
.
1 this:=r1;
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
51

52.

Процедура
vstavka
n1=8
r1
predthis
4
this^.r
. 2
7
this^.l
this^.a
.
2
.
. 6
.
this
.
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
52

53.

Процедура
vstavka
n1=8
r1
predthis
4
this^.r
. 2
7
this^.l
this^.a
.
2
.
. 6
.
this
.
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
53

54.

Процедура
vstavka
n1=8
r1
predthis
4
this^.r
. 2
7
this^.l
this^.a
.
2
.
. 6
.
.
this
.
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
54

55.

Процедура
vstavka
n1=8
r1
predthis
4
this^.r
. 2
7
this^.l
this^.a
.
2
.
. 6
.
.
this
.
2 while this <> nil do begin
3
predthis:=this;
4
if n1 < this^ .a then
5
this:= this^ .l
6
else this:= this^ .r
7 end;
55

56.

Процедура
vstavka
n1=8
r1
predthis
4
predthis^.r
. 2
7
this
.
predthis^.a
.
2
. 8 new(this);
. 6
9 with this^ do begin
10
a:= n1;
11
l:= nil;
12
r:= nil;
13 end;
привязка нового узла к дереву
14
if n1 < predthis^. a then
15
predthis^ .l:= this
16
else predthis^.r:= this
.
this^.l
.
8
this^.a
.
this^.r
56

57.

Процедура
vstavka
n1=8
r1
predthis
4
predthis^.r
. 2
this
7
predthis^.a
.
2
. 8 new(this);
. 6
9 with this^ do begin
10
a:= n1;
11
l:= nil;
12
r:= nil;
13 end;
привязка нового узла к дереву
14
if n1 < predthis^. a then
15
predthis^ .l:= this
16
else predthis^.r:= this
.
this^.l
.
8
this^.a
.
this^.r
57

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

n=0
i=6
Главная программа
Цикл вставки элементов последовательно в
непустое дерево
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 obxod (r2)
20 end;
58