русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Прохождение бинарных деревьев


Дата добавления: 2013-12-23; просмотров: 2398; Нарушение авторских прав


End;

Begin

Var

Begin

Begin

Var

S: string;

N:integer;

Var

End;

pnt_s,current_s,root: pointer;

pnt,current:^node;

procedure node_search (pnt_s:pointer; var current_s:pointer);

{Поиск узла по содержимому}

pnt_n:^node;

pnt_n:=pnt_s; writeln(pnt_n^.name);

if not (pnt_n^.name=s) then

if pnt_n^.left <> nil then

node_search (pnt_n^.left,current_s);

if pnt_n^.right <> nil then

node_search (pnt_n^.right,current_s);

end

else current_s:=pnt_n;

end;

procedure node_list (pnt_s:pointer);

{Вывод списка всех узлов дерева}

pnt_n:^node;

pnt_n:=pnt_s; writeln(pnt_n^.name);

if pnt_n^.left <> nil then node_list (pnt_n^.left);

if pnt_n^.right <> nil then node_list (pnt_n^.right);

procedure node_dispose (pnt_s:pointer);

{Удаление узла и всех его потомков в дереве}

var

pnt_n:^node;

begin

if pnt_s <> nil then

begin

pnt_n:=pnt_s; writeln(pnt_n^.name);

if pnt_n^.left <> nil then

node_dispose (pnt_n^.left);

if pnt_n^.right <> nil then

node_dispose (pnt_n^.right);

dispose(pnt_n);

end

end;

begin

new(current);root:=current;

current^.name:='root';

current^.left:=nil;

current^.right:=nil;

repeat

writeln('текущий узел -',current^.name);

writeln('1-присвоить имя левому потомоку');

writeln('2-присвоить имя правому потомку');

writeln('3-сделать узел текущим');

writeln('4-вывести список всех узлов');

writeln('5-удалить потомков текущего узла');

read(n);

if n=1 then

begin {Создание левого потомка}

if current^.left= nil then new(pnt)

else pnt:= current^.left;

writeln('left ?');

readln;



read(s);

pnt^.name:=s;

pnt^.left:=nil;

pnt^.right:=nil;

current^.left:= pnt;

end;

if n=2 then

begin {Создание правого потомка}

if current^.right= nil then new(pnt)

else pnt:= current^.right;

writeln('right ?');

readln;



read(s);

pnt^.name:=s;

pnt^.left:=nil;

pnt^.right:=nil;

current^.right:= pnt;

end;

if n=3 then

begin {Поиск узла}

writeln('name ?');

readln;



read(s);

current_s:=nil; pnt_s:=root;

node_search (pnt_s, current_s);

if current_s <> nil then current:=current_s;

end;

if n=4 then

begin {Вывод списка узлов}

pnt_s:=root;

node_list(pnt_s);

end;

if n=5 then

begin {Удаление поддерева}

writeln('l,r ?');

readln;



read(s);

if (s='l') then

begin {Удаление левого поддерева}

pnt_s:=current^.left;

current^.left:=nil;

node_dispose(pnt_s);

end

else

begin {Удаление правого поддерева}

pnt_s:=current^.right;

current^.right:=nil;

node_dispose(pnt_s);

end;

end;

until n=0

end.

 

В виде массива проще всего представляется полное бинарное дерево, так как оно всегда имеет строго определенное число вершин на каждом уровне. Вершины можно пронумеровать слева направо последовательно по уровням и использовать эти номера в качестве индексов в одномерном массиве.

Рис.4.5. Представление бинарного дерева в виде массива

Если число уровней дерева в процессе обработки не будет существенно изменяться, то такой способ представления полного бинарного дерева будет значительно более экономичным, чем любая списковая структура.

Однако далеко не все бинарные деревья являются полными. Для неполных бинарных деревьев применяют следующий способ представления. Бинарное дерево дополняется до полного дерева, вершины последовательно нумеруются. В массив заносятся только те вершины, которые были в исходном неполном дереве. При таком представлении элемент массива выделяется независимо от того, будет ли он содержать узел исходного дерева. Следовательно, необходимо отметить неиспользуемые элементы массива. Это можно сделать занесением специального значения в соответствующие элементы массива. В результате структура дерева переносится в одномерный массив. Адрес любой вершины в массиве вычисляется как

адрес = 2к-1+i-1,

где k-номер уровня вершины, i- номер на уровне k в полном бинарном дереве. Адрес корня будет равен единице. Для любой вершины можно вычислить адреса левого и правого потомков

адрес_L = 2к+2(i-1)

адрес_R = 2к+2(i-1)+1

Главным недостатком рассмотренного способа представления бинарного дерева является то, что структура данных является статической. Размер массива выбирается исходя из максимально возможного количества уровней бинарного дерева. Причем чем менее полным является дерево, тем менее рационально используется память.

В ряде алгоритмов обработки деревьев используется так называемое прохождение дерева. Под прохождением бинарного дерева понимают определенный порядок обхода всех вершин дерева. Различают несколько методов прохождения.

Прямой порядок прохождения бинарного дерева можно определить следующим образом

1. попасть в корень

2. пройти в прямом порядке левое поддерево

3. пройти в прямом порядке правое поддерево

Рис.4.6. Прямой порядок прохождения бинарного дерева

Прохождение бинарного дерева в обратном порядке можно определить в аналогичной форме

1. пройти в обратном порядке левое поддерево

2. пройти в обратном порядке правое поддерево

3. попасть в корень

Рис.4.7. Обратный порядок прохождения бинарного дерева

Определим еще один порядок прохождения бинарного дерева, называемый симметричным.

1. пройти в симметричном порядке левое поддерево

2. попасть в корень

3. пройти в симметричном порядке правое поддерево

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

Представление деревьев в виде массивов также допускает хранение порядка прохождения дерева. Для этого вводится дополнительный массив, в который записываются адрес вершины в основном массиве, следующей за данной вершиной.

Рис.4.8. Представление симметрично прошитого бинарного дерева в виде массивов

Такие структуры данных получили название прошитых бинарных деревьев. Указатели или адреса, определяющие порядок обхода называют нитями. При этом в соответствии с порядком прохождения вершин

различают право прошитые, лево прошитые и симметрично прошитые бинарные деревья.

4.4. Алгоритмы на деревьях

4.4.1. Сортировка с прохождением бинарного дерева

В качестве примера использования прохождения бинарного дерева можно привести один из способов сортировки. Допустим, мы имеем некоторый массив и пытаемся упорядочить его элементы по возрастанию. Сама сортировка при этом распадается на две фазы

1. построение дерева

2. прохождение дерева

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

Рис.4.9. Сортировка по возрастанию с прохождением бинарного дерева

Для создания очередного узла происходят сравнения элемента со значениями существующих узлов, начиная с корня.

Во время второй фазы происходит прохождение дерева в симметричном порядке. Результатом сортировки является последовательность значений элементов, извлекаемых их пройденных узлов.

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



<== предыдущая лекция | следующая лекция ==>
Представление бинарных деревьев | Применение бинарных деревьев для сжатия информации


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.