38023

ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ «БИНАРНОГО ДЕРЕВА»

Лабораторная работа

Информатика, кибернетика и программирование

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

Русский

2013-09-25

197.5 KB

8 чел.

11

Лабораторная работа № 4

«ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ «БИНАРНОГО ДЕРЕВА»»

Цель работы: исследовать и изучить АТД «дерево».

Задача работы: овладеть навыками составления структур АТД «дерево» и написания программ по исследованию АТД «дерево» на любом языке программирования.

Порядок работы :

  1.  изучить описание лабораторной работы;
  2.  по заданию, данному преподавателем, разработать структуру АТД «дерево»;
  3.  написать программу на языке ПАСКАЛЬ;
  4.  отладить программу;
  5.  решить задачу;
  6.  оформить отчет.

Краткая теория

Бинарные деревья поиска. Данные деревья обычно используются для работы с множествами. Множество – это некая совокупность элементов, где каждый элемент или сам является множеством, или является примитивным элементом, называемым атомом. Все элементы любого множества различны, т. е. нет копий одного и того же элемента. Когда множества используются в качестве инструмента при разработке алгоритмов и структур данных, атомами являются целые числа, символы, строки символов и т. д. Все элементы одного множества имеют одинаковый тип данных. Атомы упорядочены с помощью отношений < и >, которые означают «меньше чем» (предшествует) и «больше чем» (следует после).

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

Тип для дерева бинарного поиска будет иметь определённый вид, если учесть, что каждый узел «дерева» состоит из трёх полей. Первое поле element – это поле, в котором храниться значение самого элемента множества. А второе и третье поля – это leftchild и rightchild. Они содержат указатели на левого и правого сына узла.

type

TREE=^pTREE;

pTREE = record

element: integer;

leftchild, rightchild: TREE;

end;

Тогда рекурсивная функция LOCATE, будет осуществлять проверку принадлежности элемента x множеству A и возвращать true, если элемент принадлежит множеству, и false, если нет, т.е. поиск заданного значения в имеющемся множестве. Данная процедура рекурсивная и осуществляет переход вправо или влево от узла, спускаясь вниз, в соответствии с характеристическим свойством дерева. При этом передаётся в функцию значение указателя на правого или левого сына при её рекурсивном вызове. Начальное значение A – это указатель на корень дерева.

function LOCATE(x: integer; var A:TREE): boolean;

begin

if A=nil then LOCATE:=false

else if x=A^.element

then LOCATE:=true

else if x<A^.element

{переход влево от узла}

then LOCATE (x, A^.leftchild)

else LOCATE (x, A^.righttchild);

{переход вправо от узла}

end; {LOCATE}

Процедура INSERT, в отличие от LOCATE, после поиска элемента в бинарном дереве осуществляет вставку элемента, если его нет в множестве. Её первое действие – это проверка на наличие элемента в множестве. Если элемента нет, то создаётся узел, содержащий x, и осуществляется его присоединение в нужное место через указатель A на этот элемент, при этом учитывается характеристическое свойство дерева. Т.е. в процессе проверки наличия элемента в множестве, происходит перемещение по бинарному дереву. Если в предполагаемом месте нахождения элемент не оказался, но был достигнут nil, то он заменяется на указатель A, который указывает на новый узел, содержащий новый элемент x.

procedure INSERT (x: integer; var A:TREE);

begin

if A=nil then begin {создание и заполнение новой ячейки}

new(A);

A^.element:=x;

A^.leftchild:=nil;

A^.righttchild:=nil;

end

else if x<A^.element then {переход к левому сыну}

INSERT(x, A^.leftchild)

else if x>A^.element then {переход к правому сыну}

INSERT(x, A^.righttchild)

end; {INSERT}

Процедура INSERT очень универсальная, так как может быть использована и для формирования бинарного дерева. Это возможно потому, что сам принцип формирования дерева (найти место в бинарном дереве для вставки нового элемента в соответствии с характеристическим свойством дерева и вставить его, если ещё такого элемента нет) схож с принципом, заложенным в поиск и вставку элемента (найти место в бинарном дереве, где может находиться искомый элемент, в соответствии с характеристическим свойством дерева, и вставить его, если элемента там нет).

Удаление элемента представляет некоторые трудности. Очень просто удалить элемент, если он является листом. А вот если элемент – это промежуточный узел, то его неправильное удаление может нарушить структуру дерева. Если узел промежуточный, то ищется самый левый потомок его правого сына или самый правый потомок его левого сына, а потом, после его отделения от дерева, вставляется на место удаляемого узла. Эти потомки должны быть «листами». В противном случае необходимо переформировать дерево.

Ниже приводим функцию, которая определяет самого левого потомка для бравого сына удаляемого узла.

function FOUND_LEFT(var A:TREE): integer;

begin

if A^.leftchild=nil

then begin

{A указывает на самого левого потомка}

FOUND_LEFT:=A^.element;

{замена узла правым сыном}

A:=A^.rightchild;

end

else FOUND_LEFT:= FOUND_LEFT(A^.leftchild);

{узел не самый левый потомок, поэтому происходит переход}

end; { FOUND_LEFT }

Данную функцию можно легко переделать и под определение самого правого потомка левого сына удаляемого узла.

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

procedure DELETE (x: integer; var A: TREE);

begin

if A<>nil then

if x<A^.element

then DELETE(x, A^.leftchild)

else

if x>A^.element

then DELETE(x, A^.rightchild)

else

if (A^.leftchild=nil) and (A^.rightchild=nil)

then A:=nil {удаление листа, содержащего x}

else

if A^.leftchild=nil

then A:=A^.rightchild

else

if A^.rightchild=nil

then A:=A^.leftchild

else {у узла оба сына}

A^.element:= FOUND_LEFT(A^.rightchild);

end; {DELETE}

Так же необходимы операторы SIM_OBX, PR_OBX и OBR_OBX, которые осуществляют обходы деревьев в симметричном, прямом и обратном порядке.

Procedure SIM_OBX(var A: TREE); {Симметричный обход}

Var

If x<A^.element then SIM_OBX(A^.leftchild);   {1}

{переход влево от узла}

Writeln(A^.element);                                             {2}

If x>A^.element then SIM_OBX(A^.rightchild); {3}

{переход вправо от узла}

End;

Procedure PR_OBX(var A: TREE); {Прямой обход}

Var

Writeln(A^.element);                                              {1}

If x<A^.element then PR_OBX(A^.leftchild);      {2}

{переход влево от узла}

If x>A^.element then PR_OBX(A^.rightchild);    {3}

{переход вправо от узла}

End;

Procedure OBR_OBX(var A: TREE); {Обратный обход}

Var

If x<A^.element then OBR_OBX(A^.leftchild);    {1}

{переход влево от узла}

If x>A^.element then OBR_OBX(A^.rightchild);  {2}

{переход вправо от узла}

Writeln(A^.element);                                               {3}

End;

Операторы обходов рекурсивны, что значительно упрощает код программы. Если необходимо выводить данные в обратном порядке, с помощью симметричного обхода, то необходимо в операторе SIM_OBX поменять местами первую и третью строку. Когда необходимо в прямом и обратном обходах сначала посещать правые узлы, а потом левые, меняют местами строки 2 и 3 в операторе PR_OBX и строки 1 и 2 в операторе OBR_OBX.

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

Если таблица данных задана в виде односвязного списка, то производится последовательный поиск в списке. Так как список – это динамическая структура, то при последовательном переборе всех элементов списка должен использоваться цикл с пред или пост условием. Для перехода от одного элемента к другому необходимо переприсвоить указатель с одного элемента списка на другой, взяв его из поля next текущего элемента. Проход по списку будет прекращён тогда, когда в поле последнего элемента будет найден конец списка nil. Если в списке искомого элемента нет, то он будет вставлен в конец списка.

Индексно-последовательный поиск. Данный поиск является улучшенным вариантом линейного поиска. Для этого все данные в таблице со своими ключами сортируют и номеруют индексами от 1 до n – максимального количества элементов. Задаются определённым шагом, с которым будут выбраны ключи из таблицы данных со своими ключами, а так же соответствующие им индексы элементов в массиве. Эти ключи и индексы помещают в отдельную таблицу индексов. Данные выбранные ключи как бы делят всю последовательность элементов на равные части и являются крайними точками интервалов, в пределах которых и может находиться потенциальный искомый элемент. Первоначально ищут интервал, в котором как раз и может находиться искомый элемент. Для этого искомый ключ сравнивают с ключами в таблице индексов. После прохода по таблице индексов известны индексы минимального ключа min и максимального max из найденного интервала. Далее уже ищется ключ в таблице данных со своими ключами только в чётко выбранном интервале от min до max.

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

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

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

Рассмотрим пример использования индексно-последовательного поиска в массиве. На рисунке 4.1 приведена таблица данных со своими ключами и таблица индексов. В таблицу индексов были помещены данные с шагом равным трём из таблицы данных со своими ключами. Проанализируем последовательность действий при поиске заданного данного с ключом равным 186. Для этого найдём интервал, в котором оно может находиться. Пройдя по таблице индексов, получаем, что 101<186<407. Следовательно, минимальный индекс min=3, а максимальный max=6. Поэтому заданное данное будем искать среди элементов массива с индексами 3, 4, 5 и 6, т.е. от 3 до 6. Действительно186 имеет индекс 4.

Для данного примера можно составить списковую структуру (рис. 4.2). Название полей ячейки будем использовать те же, что и на рис. 4.1.


Задания по вариантам:

Составить программу, которая создает из заданного множества (табл. 4.1) бинарное дерево. Необходимо осуществить заданный в соответствии с вариантом (табл. 4.2) обход бинарного дерева. Список обхода нужно занести в заданную структуру (табл. 4.3). К полученному списку обхода применить предложенный в вашем варианте метод поиска (табл. 4.4).

Таблица 4.1

Выбор заданного множества

Вариант

Множество

1

2

1

1, 0, -3, 4, 15, 56, 38, 80, 23, 100

2

45, 56, 77, 123, 7, 12, 20, 4, 5, 0

3

32, 8, 17, 25, 78, 35, 16, 34, 3, 91

4

40, 68, 93, 79, 12, 13,18,25, 33, 7

5

16, 70, 53, 69, 12, 3, 9, 2, 1, 0

6

44, 23, 22, 20, 21, 5, 78, 69, 55, 43

7

56, 78, 90, 100, 99, 63, 95, 54, 46, 47

8

6, 2, 7, 90, 35, 67, 0, -3, -5, -1

9

0, -3, -10, -5, -7, 11, 56, 47, 100, 101

10

67, 78, 70, 74, 123, 120, 54, 57, 34, 7

11

300, 456, 400, 367, 432, 3, 8, 10, 0, 1

12

50, 47, 23, 45, 10, 1, 67, 89, 170, 152

13

5, 90, 67, 70, 141, 0, -30, -5, -1, -28

14

-4, 0, 45, -3, -50, 43, 38, 34, 36, -44

15

700, 734, 708, 711, 767, 567, 32, 45, 0, 1

16

8, 16, 17, 15, 0, 1, -6, -8, -5, -4

17

39, 38, 40, 15, 18, 16, 3, 700, 800, 739

18

22, 27, 25, 38, 35, 36, 11, 12, 13, 10

19

771, 79, 19, 90, 0, 1, -5, 789, 300, 181

20

37, 89, 10, 13, 56, 16, 30, 40, 32, 31

21

99, 16, 39, 14, 18, 125, 209, 300, 274, 0

22

40, 50, 34, 48, 31, 29, 14, 16, 11, 12

23

61, 400, 387, 301, 305, 6, 17, 10, 9, -2

24

-3, 0, 1, 8, 7, -14, -16, -10, 10, 18

25

500, 511, 501, 635, 607, 100, 55, 104, 0, 5

Продолжение таблицы 4.1

1

2

26

89, 300, 305, 99, 100, 74, 72, 10, 11, 32

27

45, 87, 35, 23, 89, 900, 131, 456, 500, 5

28

76, 33, 25, 67, 78, 152, 450, 324, 7, 3

29

3, -3, 6, -5, 70, -2, 45, -1, 55, -10

30

55, -4, 0, -100, -67, 13, 59, 16, 10, 9

31

21, 90, 54, 7, 12, 3, 16, 46, 400, 321

32

5, 0, 12, -4, -10, -5, -2, 9, 26, 87

33

83, 14, 47, 831, 704, 0, -4, -1, 9, 10

34

79, 78, 70, 75, 65, 68, 60, 0, 1, 3

35

91, 99, 90, 84, 8, -3, 0, -2, 54, 4

36

34, 69, 90, -4, 0, -56, -3, 45, 33, 13

37

800, 1000, 805, 954, 3, 2, 0, -4, 15, -18

38

349, 703, 477, 568, 500, 0, -3, -2, 5, 24

39

48, 54, 9, 90, -6, 93, 5, 55, 7, 0

40

1, 5, 2, 80, 0, -5, -6, -13, -2, -100

41

88, 46, 34, 126, 68, 3, 7, 2, 99, 137

42

274, 569, 56, 344, 434, 121, 156, 65, 35, 8

43

34, 30, 27, 67, 2, 0, 79, -5, -3, 21

44

-9, -5, -1, -6, -7, 0, 13, 32, 45, 77

45

0, -2, 9, -5, 87, -4, 74, -21, 33, -1

46

55, 57, 50, 78, 43, 44, 14, 8, 5, 3

47

5, 0, 1, 3, 2, 7, 6, 8, 10, 9

48

14, 11,12, 10, 15, 52, 45, 46, 33, -4

49

7, 21, 56, 78, 60, 50, 3, 12, 0, 5

50

31, 87, 74, 43, 56, 60, 58, 57, 11, 29

Таблица 4.2

Выбор обхода бинарного дерева

Вариант

Название обхода

1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49

симметричный

2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50

в прямом порядке

3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48

в обратном порядке

Таблица 4.3

Выбор структуры для списка обхода

Вариант

Название структуры

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49

массив

2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50

список

Таблица 4.4

Выбор метода поиска

Вариант

Название поиска

2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50

последовательный

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49

индексно-последовательный


 

А также другие работы, которые могут Вас заинтересовать

52198. Наука и технология 188.5 KB
  Тексты: Science Technology Лексика chievement достижение аlwаys всегда аpproаch подход between между brаnch отрасль науки знания cleаr ясный difference different различие разный engineering техника essentiаl существенный exаmple e. for exаmple пример например field поле сфера область деятельности high высокий humn человеческий hypothesis pl hypotheses гипотеза importаnt важный impossible невозможный investigаtion исследование knowledge знание lаw закон mаin главный ...
52199. Personal Presentation 94 KB
  I am Ivan Dmitrenko. I am 17. I am a first-year student of National Technical University “Kharkiv Polytechnic Institute”. I study at the Department of Mechanical Engineering. My major (speciality) is the Technology of Cutting. I am from Kharkiv.
52200. Электроника 249.5 KB
  Most analog electronic devices, such as radio receivers, have combinations of a few types of basic circuits. There are a great number of different analog circuits, because circuits are very different - from a single component, to systems with thousands of components. Good examples of analog circuits are vacuum tube and transistor amplifiers, operational amplifiers and oscillators.
52201. Компьютеры 204.5 KB
  Тексты: Computers The Internet Лексика ccording to согласно чемулибо uxiliry вспомогательный cretion создание decision решение enough достаточно equipment оборудование hrdwre аппаратные средства however однако input output ввод вывод keybord клавиатура liquid жидкий memory память ЗУ запоминающее устройство outside внешний rpidly быстро ry луч rule правило sme the тот же самый set набор simple простой softwre программное обеспечение source источник throughout в...
52202. Робототехника 200 KB
  Тексты: Robotics Technicl Prmeters of Robots Лексика re область зона rtificil искусственный ttchment прикрепление xis pl. Переведите следующие словосочетания на русский язык: set of instructions; the bility of extreme decentrliztion of informtion nd dt; typicl pplictions of robots; investigtions into new types of robots; number of discrete voltge levels; little mount of different instructions; n ctive re of reserch; stories of rtificil helpers; mss production of consumer nd industril goods; high...
52203. Космонавтика 192 KB
  Тексты: History of spce explortion in the 20th Century Explortion of the Moon Лексика bord на борту lone единственно только ssumption допущение предположение being существо body тело celestil небесный crew команда экипаж durtion длительность Erth Земля experience опыт fmous знаменитый fr далеко flight полет hlf половина hrd твердый het тепло honor честь kind тип вид mgnificent величественный member член команды элемент конструкции milestone веха этап...
52204. Ракетостроение 206.5 KB
  Выражение to be going to Тексты: Spce Sttions Spcecrft Modifictions nd their Subsystems Лексика lso также тоже prt на части pproprite соответствующий verge средний cpcity способность; мощность closed закрытый замкнутый direction направление during в течение entry вход вхождение environment окружающая среда forwrd вперед frequently часто ground земля; основание height высота lunch vehicle ракетаноситель long term shortterm долгосрочный краткосрочный nked зд....