Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

ВАРИАНТ 8. Найти элемент, среднее арифметическое элементов, находящихся до этого элемента равно 12. Если таких элементов нет, выдать сообщение.

ВАРИАНТ 9. Найти максимальный элемент, делящийся на 10. Если такого элемента нет, выдать сообщение.

ВАРИАНТ 10. Найти элемент, разность соседних элементов которого четное число и делится на 3. Если такого элемента нет, выдать сообщение.

ВАРИАНТ 11. Найти элемент, среднее квадратичное элементов, находящихся после этого элемента меньше 10. Если таких элементов несколько, выбрать максимальный элемент. Если таких элементов нет, выдать сообщение.

ВАРИАНТ 12. Найти значение tg (x) от каждого элемента и переставить на 1 место элемент, значение функции от которого максимально.

Лабораторная работа № 12. «ПОИСК ПО ДЕРЕВУ С ВКЛЮЧЕНИЕМ»

Цель работы: освоить алгоритм  и  метод вставки элементов бинарного дерева.

Задача работы: овладеть навыками написания программ по исследованию методов вставки элементов бинарного дерева на языке программирования ПАСКАЛЬ .

Порядок работы :
изучить описание лабораторной работы;
по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
написать программу на языке ПАСКАЛЬ;
отладить программу;
решить задачу;
оформить отчет.

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

ПОИСК ПО БИНАРНОМУ ДЕРЕВУ
Для вставки элемента в дерево сначала нужно осуществить поиск в дереве по заданному ключу. Если такой ключ имеется, то программа завершается, если нет то происходит вставка. Длительность операции поиска (число узлов, которые надо перебрать для этой цели) зависит от структуры дерева. Действительно, деревом может быть вырождено в однонаправленный список (иметь единственную ветвь) — такое дерево может возникнуть, если элементы поступали в дерево в порядке возрастания (убывания) их, ключей. В этом случае время поиска будет такое же, как и однонаправленном списке, т.е. в среднем придется перебрать N/2  элементов. Наибольший эффект использования дерева достигается в том случае, когда дерево «сбалансировано». В этом случае для поиска придется перебрать не более log2N.

ВКЛЮЧЕНИЕ ЭЛЕМЕНТА В ДЕРЕВО
Для включения новой записи в дерево, прежде всего нужно найти тот узел, к которому можно «подвесить»(присоединить) новый элемент. Алгоритм поиска нужного узла тот же самый, что и при поиске узла с заданным ключом. Этот узел будет найден в тот момент, когда в качестве очередной ссылки, определяющий ветвь дерева, в которое надо продолжить поиск, окажется ссылка NIL.
Однако, непосредственно использовать процедуру поиска     нельзя, потому что по окончанию вычисления ее значение не  фиксирует тот узел, из которого была выбрана ссылка NIL. Модифицируем описание процедуры поиска так, чтобы в качестве ее побочного эффекта фиксировалась ссылка на узел, в котором был найден заданный ключ (в случае успешного поиска), или ссылка на узел, после обработки которого поиск прекращен (в случае неуспешного поиска).

Алгоритм

Рассмотрим алгоритм вставки узла в бинарное дерево.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники