Бинарное дерево

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 14.12.2011
Размер файла 81,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Министерство образования Республики Беларусь

Учреждение образования

Белорусский государственный университет информатики и радиоэлектроники

Факультет непрерывного и дистанционного обучения

Кафедра программного обеспечения информационных технологий

Контрольная работа

Бинарные деревья

Минск - 2011

Введение

Цель работы:

1) Изучить нелинейные динамические структуры данных в виде бинарного дерева.

2) Научиться решать прикладные задачи с помощью структуры данных бинарное дерево.

Построить дерево двоичного поиска, вывести его на экран компьютера любым способом (графически, вложенными скобками или отступами)

Текст программы размещен в приложении.

бинарный дерево компьютер программа

Построение дерева

Построение дерева состоит в последовательном вводе простых чисел из массива в следующей последовательности: 5, 4, 8, 6, 1, 7, 3, 9. Дерево строится, начиная с корня. Алгоритм построения:

Если узел пустой, то число помещается в него.

Если же он непустой, то входное число сравнивается с числом узла. В случае, если он больше, то он рекурсивно переносится в правое поддерево; если же меньше - в левое.

Таким образом, мы получим бинарное дерево поиска (рис. 1).

Рисунок 1 - Построенное бинарное дерево

В представлении дерева применялись отступы. Перед представлением необходимо определить высоту дерева. Высота дерева определяется как максимальный путь ее прохождения сверху-вниз. В данном случае высота дерева (переменная h) равна 4.

Представление дерева строится на двух массивах и на цикле, начиная со значения высоты дерева до 1. При данной итерации из одного массива в выходную строку с установленными отступами при помощи функции sc(s), где s - число, определяемое значением итерации (уровнем дерева) в зависимости от местоположения узла (листа) в дереве, выносятся узлы (листья) дерева одного уровня. При этом потомки этих узлов заносятся в другой массив (т.е. в массив помещаются узлы и листья следующего уровня по итерации). Первоначально в один массив заносится корень дерева, а его потомки в другой массив. Если у узла нет потомка, в массив заносится цифра 0 (либо два нуля, если это лист). Если же вместо узла - 0, то здесь проверяется последний ли уровень дерева. В случае отрицательного ответа - в массив помещаются два нуля. Это необходимо, чтобы корректно рассчитать количество отступов на данном уровне дерева, в частности между листьями 3 и 7. В конечном счете, получаем представление дерева, показанное на рис. 2

Рисунок 2 - Представление дерева

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

Рисунок 3 - Обход сверху-вниз

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

Рисунок 4 - Обход слева-направо

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

Рисунок 5 - Обход снизу-вверх

Выполнить симметричноправую прошивку дерева.

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

Рисунок 6 - Симметричноправая прошивка дерева

Процедура прошивки, в которой осуществляется обход, проводит поиск листьев и узлов, для которых требуется прошивка (в частности это листья 3, 7, 9 и узел 4). Когда этот лист или узел обнаруживается, инициализируется дополнительная процедура, которая таким же обходом находит узел, к которому прошивается лист или узел, найденный первичной процедурой (3, 7, 9 и 4). Такими узлами являются 4, 5 и 8.

Выводы:

- в ходе выполнения работы были изучены нелинейные динамические структуры данных в виде бинарного дерева;

- была решена задача, связанная со структурой данных - бинарное дерево (создание, представление, обходы и прошивка дерева).

Приложение

program bin_tree;

const n = 8;

type pnode = ^node;

node = record

v : integer;

right, left : pnode;

lf, rf : boolean;

end;

var root : pnode;

st : boolean; {флажок для определения прошито ли дерево}

v : integer;

right, left : pnode;

j, h, i, answ, answ2 : integer;

const m : array[1..n] of integer = (5,4,8,6,1,7,3,9);

{------------ create of tree -------------}

procedure Insert(var root: pnode; X: integer);

{Дополнительная процедура, создающая и инициирующая новый узел}

procedure CreateNode(var p : pnode; n : integer);

begin

new(p);

p^.v := n;

p^.left := nil;

p^.right := nil;

end;

begin

if root = nil then

CreateNode(root, X) {создаем новый узел дерева}

else

with root^ do

begin

if v < X then

Insert(right, X)

else

if v > X then

Insert(left, X)

else

{Действия, производимые в случае повторного внесения

элементов в дерево}

begin

writeln('Такой элемент уже есть');

exit;

end;

end;

end;

{--------- View of tree --------------------}

procedure ViewTree(root : pnode);

var mas1, mas2 : array[1..8] of integer;

q, m1, m2 : integer;

Sch, Chl, Chr : pnode;

{функция для определения количества отступов}

function sc(s : integer) : integer;

var c, c1, w : integer;

begin

c := 0;

sc := 0;

s := s-1;

if s = 0 then

exit;

for w := 1 to s do

begin

c1 := 1+2*c;

c := c1;

end;

sc := c1;

end;

{поиск узла или листа дерева по значению v}

procedure Search(root : pnode; s : integer);

begin

if root^.v = s then

begin

Sch := root;

exit;

end;

if root = nil then

exit

else

begin

Search(root^.right, s);

Search(root^.left, s);

end;

end;

{занесение потомков узлов дерева одного уровня во 2-ой массив}

procedure ToMas2;

begin

if Sch^.left <> nil then

begin

Chl := Sch^.left;

m2 := m2+1;

mas2[m2] := Chl^.v;

end

else

begin

m2 := m2+1;

mas2[m2] := 0;

end;

if Sch^.right <> nil then

begin

Chr := Sch^.right;

m2 := m2+1;

mas2[m2] := Chr^.v;

end

else

begin

m2 := m2+1;

mas2[m2] := 0;

end;

end;

{занесение потомков узлов дерева следующего уровня в первый массив}

procedure ToMas1;

begin

if Sch^.left <> nil then

begin

Chl := Sch^.left;

m1 := m1+1;

mas1[m1] := Chl^.v;

end

else

begin

m1 := m1+1;

mas1[m1] := 0;

end;

if Sch^.right <> nil then

begin

Chr := Sch^.right;

m1 := m1+1;

mas1[m1] := Chr^.v;

end

else

begin

m1 := m1+1;

mas1[m1] := 0;

end;

end;

{если уровень дерева не является последним - заносим 2 нуля в первый массив}

procedure NilToMas1;

begin

if i > 1 then

begin

m1 := m1+1;

mas1[m1] := 0; {первый ноль}

m1 := m1+1;

mas1[m1] := 0; {второй ноль}

end;

end;

{если уровень не последний - заносим нули во второй массив}

procedure NilToMas2;

begin

if i > 1 then

begin

m2 := m2+1;

mas2[m2] := 0;

m2 := m2+1;

mas2[m2] := 0;

end;

end;

begin

mas1[1] := root^.v;

m1 := 1;

m2 := 0;

for i := h downto 1 do

begin

writeln;

{отображаем первый элемент уровня}

if mas1[1] = 0 then

begin

NilToMas2;

write('':(sc(i)+1));

end

else

begin

write('':sc(i), mas1[1]);

Search(root, mas1[1]);

ToMas2;

end;

{отображаем остальные элементы, если уровень дерева не содержит корень}

if m1 > 1 then

begin

for q := 2 to m1 do

if mas1[q] = 0 then

begin

NilToMas2;

write('':(sc(i+1)+1));

end

else

begin

write('':sc(i+1), mas1[q]);

Search(root, mas1[q]);

ToMas2;

end;

end;

m1 := 0;

{на следующий уровень}

if i = 1 then

break

else

i := i-1;

writeln;

if mas2[1] = 0 then

begin

NilToMas1;

write('':(sc(i)+1));

end

else

begin

write('':sc(i), mas2[1]);

Search(root, mas2[1]);

ToMas1;

end;

for q := 2 to m2 do

begin

if mas2[q] = 0 then

begin

NilToMas1;

write('':(sc(i+1)+1));

end

else

begin

write('':sc(i+1), mas2[q]);

Search(root, mas2[q]);

ToMas1;

end;

end;

m2 := 0;

{на следующий уровень}

end;

end;

{------------- Прямой порядок прохождения -------------}

procedure PrintDown(level : integer; root : pnode);

{в этом обходе заодно рассчитаем высоту дерева h для его представления}

begin

if root = nil then

exit;

with root^ do

begin

{для прошивки дерева устанавливаем флажки}

if right = nil then

rf := false;

lf := false;

{определяем высоту дерева}

if (left = nil) and (right = nil) then

begin

j := j+1;

if h < j then

{высотой дерева является его максимальный путь прохождения}

h := j;

j := 0;

end;

writeln('':2*level, v);

j := j+1;

PrintDown(level+1, left);

PrintDown(level+1, right)

end;

end;

{--------------- Симметричный порядок прохождения -------}

procedure PrintLex(level : integer; root : pnode);

begin

if root = nil then

exit;

with root^ do

begin

PrintLex(level+1, left);

writeln('':2*level, v);

PrintLex(level+1, right);

end

end;

{----------- Концевой порядок прохождения ----------}

procedure PrintUp(level : integer; root : pnode);

begin

if root = nil then

exit;

with root^ do

begin

PrintUp(level+1, left);

PrintUp(level+1, right);

writeln('':2*level, v);

end

end;

{------------ прошивка ------------------------------}

procedure Threading(x : pnode);

var p : pnode;

stop : boolean;

{устанавливаем указатель}

procedure rightPointer(y : pnode; i : integer);

begin

if stop = true then

exit;

j := j+1; {подсчитываем число рекурсий}

if y = nil then

exit;

with y^ do

begin

rightPointer(left, i);

if (j > i) and (rf = true) then

begin

j := 0;

writeln('Прошиваем ', x^.v, ' элемент с ', v);

x^.right := y;

{сворачиваем рекурсию}

stop := true;

{помечаем, что узел или лист прошит}

x^.lf := true;

exit;

end;

if lf = true then

exit;

rightPointer(right, i);

end

end;

begin

i := i+1; {подсчитываем число рекурсий}

if x = nil then

exit;

with x^ do

begin

rf := true; {помечаем, что узел или лист посещался}

Threading(left);

if (rf = true) and (right = nil) then

{если узел не прошит}

begin

stop := false;

{прошиваем его}

rightPointer(root, i);

end;

if (left = nil) and (right = nil) then

{прошиваем лист}

begin

stop := false;

rightPointer(root, i);

end;

writeln(' ',v);

if lf = true then {если узел или лист прошит}

exit; {выходим}

Threading(right);

end;

end;

{------------- формирование дерева ---------------}

procedure Cycle;

begin

for i := 1 to n do

Insert(root, m[i]);

end;

{----------------------------------------------------}

begin

Cycle;

{определим высоту дерева обходом сверху-вниз}

PrintDown(1, root);

writeln('Выберите действие');

while true do

begin

writeln('1 - провести обход, 2 - отобразить дерево, 3 - выполнить прошивку, 4 - выход');

readln(answ);

case answ of

1 :

begin

if st = true then

writeln('Обход невозможен - дерево прошито')

else

begin

writeln('Выберите обход: 1 - сверху-вниз, 2 - слева-направо, 3 - снизу-вверх');

readln(answ2);

case answ2 of

1 :

begin

writeln('Обход сверху-вниз:');

PrintDown(1, root);

end;

2 :

begin

writeln('Обход слева-направо:');

PrintLex(1, root);

end;

3 :

begin

writeln('Обход снизу-вверх:');

PrintUp(1, root);

end;

end;

end;

end;

2 :

if st = true then

writeln('Дерево прошито - его представление невозможно')

else

begin

writeln('Представление дерева:');

{вызоваем процедуру представления дерева}

ViewTree(root);

end;

3 :

begin

if st = true then

writeln('Дерево уже прошито')

else

begin

writeln('Прошивка:');

i := 0;

j := 0;

Threading(root);

st := true;

end;

end;

4 : exit;

end;

writeln;

end;

end.

Размещено на Allbest.ru


Подобные документы

  • Разработка программы на языке С#, которая будет заниматься построением бинарного дерева для исходных данных и их редактированием, поиском информации о товарах по заданному ключу. Графические схемы алгоритмов поиска и удаления элемента бинарного дерева.

    курсовая работа [796,9 K], добавлен 22.02.2016

  • Описание процедуры выбора структуры хранения данных. Программная реализация одномерного неоднородного массива. Представление бинарного дерева в виде динамической структуры данных. Изучение способов поиска в упорядоченном дереве. Содержание базы данных.

    практическая работа [850,0 K], добавлен 16.04.2015

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

    курсовая работа [426,0 K], добавлен 24.06.2013

  • Организация данных с помощью бинарных деревьев. Определение бинарного дерева. Упорядоченное двоичное дерево поиска и его свойства. Программная реализация добавления данных в упорядоченное двоичное дерево с использованием динамических структур данных.

    курсовая работа [459,0 K], добавлен 09.08.2012

  • Описание структуры бинарного дерева поиска на языке C# среды Visual Studio. Требования к интерфейсу пользователя, структуре данных и программным средствам. Компоненты программных средств, результаты тестирования, диаграммы вариантов использования классов.

    курсовая работа [968,2 K], добавлен 26.01.2013

  • Составление программной функции, которая вычисляет среднее арифметическое элементов непустого списка. Функция, которая находит наименьший элемент дерева. Нахождение искомых элементов, добавление элементов в дерево. Выведение состояния дерева на экран.

    лабораторная работа [636,3 K], добавлен 02.04.2014

  • Древовидная структура – "Бинарное дерево поиска", его структура и взаимосвязь основных компонентов, исследование в глубину. Описание разработанного программного продукта. Главные функции редактирования исходных данных и принципы работы с файлами.

    курсовая работа [1,6 M], добавлен 13.06.2014

  • Понятие и базовые свойства ориентированного дерева. Обходы (способы нумерации вершин) в глубину и ширину. Представление бинарных графов с помощью указателей и массива, скобочной записи, списком прямых предков. Сбалансированность дерева двоичного поиска.

    презентация [330,6 K], добавлен 19.10.2014

  • Общая характеристика организации массива в виде двоичного дерева. Особенности линейного и двоичного поиска заданного элемента массива. Методика упорядочения массива методом сортировки деревом. Инструкции и текст программы для нечисленной обработки данных.

    курсовая работа [242,3 K], добавлен 12.11.2010

  • Исследование особенностей основных файловых менеджеров, разработанных под операционную систему Windows. Изучение порядка заполнения элементов бинарного дерева. Обзор приложения, реализующего графический интерфейс доступа пользователя к папкам и файлам.

    курсовая работа [2,9 M], добавлен 11.07.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.