Презентация на тему Задание бинарных деревьев с помощью массивов

дерева поиска
Обходы дерева

представить полное бинарное дерево, так как оно всегда имеет

строго определенное количество вершин на каждом уровне, кроме последнего уровня (например, число узлов в дереве, имеющем три уровня, может быть от 4 до 7).
Для задания полного дерева используем три массива: key (для хранения ключей), left (для хранения ссылок на левых потомков вершин), и right (для хранения ссылок на правых потоков вершин).
Пронумеруем вершины полного дерева так, чтобы левый помок любой i – ой вершины имел адрес 2i, а правый потомок любой i – ой вершины имел адрес 2i + 1.
При задании дерева воспользуемся прямым левым обходом. Сначала задаем количество вершин в нашем дереве (n), формируем корень дерева.

корня, проверяем:
1) если 2i

вершины есть левый потомок, т.е. в массив left на i – ое место записываем адрес 2i. Переходим на вершину с адресом 2i. Задаем число, хранящееся в данной вершине и пункт 1) иначе, если 2i > n, значит, у данной вершины нет левого потомка, т.е. в массив left на i – ое место запишем 0 и пункт 2);
2) если 2i+1 < n, значит, у данной вершин есть правый потомок, т.е. в массив right на i – ое место записываем адрес 2i+1. Переходим на вершину с адресом 2i+1. Задаем число, хранящееся в данной вершине и пункт 1) иначе, если 2i+1 > n , значит, у данной вершины нет правого потомка, т.е. в массив right на i – ое место запишем 0. Переходим на предыдущую вершину, для которой условия пункта 1) уже проверены, а условия пункта 2) еще нет.

Программа задания полного дерева на языке Паскаль

иной задачи требуется задать не полное, а произвольное (неполное)

дерево.
Пусть нужно задать произвольное дерево
(см. рис.):

Значения, хранящиеся в узлах дерева, не имеют принципиального значения, т.е. их можно сгенерировать случайным образом. Для нумерации вершин используем прямой левый обход, поэтому вершины пронумеруем соответственно ( см. рис.).

на каждом уровне (кроме нулевого уровня) может быть различное

количество вершин, поэтому вид дерева нужно задавать вручную. Сделать это можно с помощью последовательности, например, 0 и 1 (можно использовать любые символы), хранящейся в текстовом файле.
Составляется данная последовательность следующим образом: идем по дереву прямым левым обходом:
встаем на первую вершину и смотрим, слева есть вершина, значит, ставим 1 и переходим на вторую вершину;
у второй вершины слева есть вершина, ставим 1 и переходим на третью вершину;
у третьей вершины слева нет вершины, значит, ставим 0, справа у данной вершины тоже нет другой вершины, ставим 0 и возвращаемся на вторую вершину;
у второй вершины справа есть вершина, ставим 1 и переходим на четвертую вершину и т.д.
Процесс закончится когда мы обойдем все вершины.
В результате в нашем файле должна быть записана следующая последовательность: 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0.

сын». Для хранения левых и правых ссылок используем массивы

left и right соответственно. Заполнение данных массивов происходит следующим образом:
стоим на первой вершине и считываем из ранее заготовленного файла первый элемент, т.е. 1, а это значит, что у первой вершины есть левый потомок – вершина №2, следовательно, в массив left на первое место запишется 2;
переходим на вторую вершину и считываем из файла второй элемент, т.е. 1, значит, что у второй вершины есть левый потомок – вершина №3, следовательно, в массив left на второе место запишется 3;
переходим на третью вершину и считываем из файла третий элемент, т.е. 1, значит, что у третьей вершины есть левый потомок – вершина №4, следовательно, в массив left на третье место запишется 1;
переходим на четвертую вершину и считываем из файла четвертый элемент, т.е. 0, значит, что у четвертой вершины нет левого потомка, следовательно, в массив left на четвертое место запишется 0;

элемент из файла, т.е. 0, значит, что у четвертой

вершины нет правого потомка, следовательно, в массив right на четвертое место запишется 0;
возвращаемся на третью вершину и считываем следующий элемент из файла, т.е. 0, значит, что у третьей вершины нет правого потомка, следовательно, в массив right на третье место запишется 0;и т.д.
Процесс закончится, когда мы прямым левым обходом обойдем все вершины дерева.
В результате наше дерево будет задано с помощью трех массивов:
Key – в данном массиве будут храниться значения узлов дерева;
Left = [2 3 4 0 0 7 0 0 0 0] – массив правых ссылок;
Right = [9 5 0 0 6 8 0 0 10 0] – массив правых ссылок.

Назад

Меню

Программа задания произвольного дерева на языке Паскаль

с помощью массивов.
Как и в предыдущих случаях для хранения

значений узлов, левых и правых ссылок выделяем массивы key, left и right соответственно. Значения элементов, из которых нужно построить дерево поиска удобно хранить в текстовом файле.
Пусть нужно построить дерево поиска для следующего набора элементов: 20 15 32 17 13 23 28 16.

Назад

Меню

дерева. Для корня левую и правую ссылки объявляем равными

нулю, т.е. пока кроме корня других вершин нет.
Берем второй элемент и сравниваем его с корнем: 15<20 и левая ссылка у корня = 0 т.е. слева у 20 нет вершины, поэтому нужно эту вершину создать, записать в неё 15, обнулить левую и правую ссылки второй вершины и создать связь между этими вершинами т.е. в массив left на первое место записать 2.
Берем третий элемент и сравниваем его с элементами нашего дерева, начиная с корня: 32>20, правая ссылка у корня = 0. Следовательно, справа от корня создаем вершину, записываем в неё 32, обнуляем левую и правую ссылки третьей вершины и создаем связь между этими вершинами, т.е. в массив right на первое место записать 3.
Берем четвертый элемент и сравниваем его с элементами нашего дерева, начиная с корня: 17<20, но слева у 20 уже есть вершина №2 (в ней записано 15), поэтому нужно перейти на эту вершину и сравнить ее значение с взятым элементом. 17>15, правая ссылка у второй вершины = 0. Следовательно, справа от неё создаем вершину, записываем в неё 17, обнуляем левую и правую ссылки четвертой вершины и создаем связь между этими вершинами, т.е. в массив right на второе место записываем 4 и т.д. Процесс закончится, когда мы переберем все элементы файла.

Назад

Меню

рис.), заданное с помощью массивов:
Key = [20 15 32

17 13 23 28 16];
Left = [2 5 6 8 0 0 0 0];
Right = [3 4 0 0 0 7 0 0].

20

15

13

17

32

16

23

1

2

5

4

8

3

6

28

7

Программа задания двоичного дерева поиска на языке Паскаль

вершин построенного дерева, найти нужный элемент в дереве, отсортировать

элементы дерева и во многих других задачах необходимо совершить так называемый обход дерева (посетить каждую его вершину, причем производить какие-то действия с каждой вершиной можно только 1 раз).
В случае, когда бинарное дерево пусто, оно обходится без выполнения каких- либо действий. Чтобы обойти непустое дерево существует несколько алгоритмов.
Рекурсивные алгоритмы прохождения каждого дерева по каждому из способов включают 3 одинаковых процедуры, где нужно найти корень поддерева, левое поддерево текущего корня и правое поддерево текущего корня. Направление обхода однозначно определяет последовательность выполнения указанных процедур.

Назад

Меню

левый обход
Обратный правый обход
Внутренний левый обход
Внутренний правый обход
По уровням

слева на право сверху вниз

По уровням справа налево сверху вниз

По уровням слева на право снизу вверх

По уровням справа налево снизу вверх

корень;
Обойти левое поддерево;
Обойти правое поддерево.
Процедура прохождения дерева прямым левым

обходом на языке Паскаль:
procedure obxod_1(i:integer);
begin
if i<>0 then begin write(key[i]:4); obxod_1(left[i]); obxod_1(right[i]); end;
end;

Назад

Меню

Список обходов

корень;
Обойти правое поддерево;
Обойти левое поддерево.
Процедура прохождения дерева прямым правым

обходом на языке Паскаль:
procedure obxod_2(i:integer);
begin
if i<>0 then
begin
write(key[i]:4);
obxod_2(right[i]);
obxod_2(left[i]);
end;
end;

Назад

Меню

используя прямой правый обход, получим последовательность:
A E G

I H F B D C

Назад

Меню

A

E

B

C

D

F

G

I

H

Список обходов

на части
стратегия "разделяй и властвуй" (Сортировка Фон Hеймана,

быстрая сортировка, одновременное нахождение максимума и минимума последовательности чисел, умножение длинных чисел).

Назад

Меню

Список обходов

правое поддерево;
Посетить корень.
Процедура прохождения дерева обратным левым обходом на

языке Паскаль:
procedure obxod_3(i:integer);
begin
if i<>0 then
begin
obxod_3(left[i]);
obxod_3(right[i]);
write(key[i]:4);
end;
end;

Назад

Меню

используя обратный левый обход, получим последовательность:
C D B F

H I G E A

Назад

Меню

A

E

B

C

D

F

G

I

H

Список обходов

левое поддерево;
Посетить корень.
Процедура прохождения дерева обратным правым обходом на

языке Паскаль:
procedure obxod_4(i:integer);
begin
if i<>0 then
begin
obxod_4(right[i]);
obxod_4(left[i]);
write(key[i]:4);
end;
end;

Назад

Меню

рис.), используя обратный правый обход, получим последовательность:
I H

G F E D C B A

Назад

Меню

A

E

B

C

D

F

G

I

H

Список обходов

корень;
Обойти правое поддерево.
Процедура прохождения дерева внутренним левым обходом на

языке Паскаль:
procedure obxod_5(i:integer);
begin
if i<>0 then
begin
obxod_5(left[i]);
write(key[i]:4);
obxod_5(right[i]);
end;
end;

Назад

Меню

используя внутренний левый обход, получим последовательность:
C B D

A F E H G I

Назад

Меню

Список обходов

корень;
Обойти левое поддерево.
Процедура прохождения дерева внутренним правым обходом на

языке Паскаль:
procedure obxod_6(i:integer);
begin
if i<>0 then
begin
obxod_6(right[i]);
write(key[i]:4);
obxod_6(left[i]);
end;
end;

Назад

Меню

рис.), используя внутренний правый обход, получим последовательность:
I G

H E F A D B C

Назад

Меню

Список обходов

из четырех обходов дерева по уровням необходимо знать, сколько

уровней в дереве (высоту дерева), которое нужно обойти. Если дерево неполное и содержит большое количество вершин, то считать количество уровней вручную очень сложно. Рационально будет использовать специальную процедуру, которая определяет высоту любого бинарного дерева.
Процедура вычисления высоты бинарного дерева на языке Паскаль:
procedure H_tree(i,u:integer);
begin
if i<>0 then begin if hend;
По окончанию работы данной процедуры в переменной h будет храниться высота дерева, которое нужно обойти.

Назад

Меню