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

1 Задание бинарных деревьев с помощью массивов Обходы деревьев

2 Содержание Задание полного бинарного дерева Задание произвольного бинарного дерева Задание двоичного дерева поиска Обходы дерева

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

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

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

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

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

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

9 Задание двоичного дерева поиска Рассмотрим задание двоичного дерева поиска с помощью массивов. Как и в предыдущих случаях для хранения значений узлов, левых и правых ссылок выделяем массивы key, left и right соответственно. Значения элементов, из которых нужно построить дерево поиска удобно хранить в текстовом файле. Пусть нужно построить дерево поиска для следующего набора элементов: Назад Меню

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

11 Назад Меню В результате получится следующее двоичное дерево поиска (см. рис.), заданное с помощью массивов: Key = [ ]; Left = [ ]; Right = [ ] Программа задания двоичного дерева поиска на языке Паскаль

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

13 Алгоритмы обхода дерева: Назад Меню Прямой левый обход Прямой правый обход Обратный левый обход Обратный правый обход Внутренний левый обход Внутренний правый обход По уровням слева на право сверху вниз По уровням справа налево сверху вниз По уровням слева на право снизу вверх По уровням справа налево снизу вверх

14 Прямой левый обход дерева Алгоритм прямого левого обхода дерева: 1. Посетить корень; 2. Обойти левое поддерево; 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; Назад МенюСписок обходов

15 Прямой правый обход дерева Алгоритм прямого правого обхода дерева: 1. Посетить корень; 2. Обойти правое поддерево; 3. Обойти левое поддерево. Процедура прохождения дерева прямым правым обходом на языке Паскаль: procedure obxod_2(i:integer); begin if i<>0 then begin write(key[i]:4); obxod_2(right[i]); obxod_2(left[i]); end; Назад Меню

16 Пример Выводя на экран значения вершин бинарного дерева (см.рис.), используя прямой правый обход, получим последовательность: A E G I H F B D C Назад Меню A E B CDFG IH Список обходов

17 Примеры использования прямых обходов: 1. решение задачи методом деления на части 2. стратегия "разделяй и властвуй" (Сортировка Фон Hеймана, быстрая сортировка, одновременное нахождение максимума и минимума последовательности чисел, умножение длинных чисел). Назад МенюСписок обходов

18 Обратный левый обход Алгоритм обратного левого обхода: 1. Обойти левое поддерево; 2. Обойти правое поддерево; 3. Посетить корень. Процедура прохождения дерева обратным левым обходом на языке Паскаль: procedure obxod_3(i:integer); begin if i<>0 then begin obxod_3(left[i]); obxod_3(right[i]); write(key[i]:4); end; Назад Меню

19 Пример Выводя на экран значения вершин бинарного дерева (см.рис.), используя обратный левый обход, получим последовательность: C D B F H I G E A Назад Меню A E B CDFG IH Список обходов

20 Обратный правый обход Алгоритм обратного правого обхода: 1. Обойти правое поддерево; 2. Обойти левое поддерево; 3. Посетить корень. Процедура прохождения дерева обратным правым обходом на языке Паскаль: procedure obxod_4(i:integer); begin if i<>0 then begin obxod_4(right[i]); obxod_4(left[i]); write(key[i]:4); end; Назад Меню

21 Пример Выводя на экран значения вершин бинарного дерева (см. рис.), используя обратный правый обход, получим последовательность: I H G F E D C B A Назад Меню A E B CDFG IH Список обходов

22 Внутренний левый обход Алгоритм внутреннего левого обхода: 1. Обойти левое поддерево; 2. Посетить корень; 3. Обойти правое поддерево. Процедура прохождения дерева внутренним левым обходом на языке Паскаль: procedure obxod_5(i:integer); begin if i<>0 then begin obxod_5(left[i]); write(key[i]:4); obxod_5(right[i]); end; Назад Меню

23 Пример Выводя на экран значения вершин бинарного дерева (см.рис.), используя внутренний левый обход, получим последовательность: C B D A F E H G I Назад Меню A E B CDFG IH Список обходов

24 Внутренний правый обход Алгоритм внутреннего правого обхода: 1. Обойти правое поддерево; 2. Посетить корень; 3. Обойти левое поддерево. Процедура прохождения дерева внутренним правым обходом на языке Паскаль: procedure obxod_6(i:integer); begin if i<>0 then begin obxod_6(right[i]); write(key[i]:4); obxod_6(left[i]); end; Назад Меню

25 Пример Выводя на экран значения вершин бинарного дерева (см. рис.), используя внутренний правый обход, получим последовательность: I G H E F A D B C Назад Меню A E B CDFG IH Список обходов

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