Курс лекций мдк 01. 02 «Прикладное программирование» пм 01 «Разработка программных модулей программного обеспечения для компьютерных систем»

Имя типа: Дерево двоичного поиска


Свойства типа: -Двоичное дерево является или пустым набором узлов
(пустым деревом),

или набором узлов с одним узлом, обозначенным в

качестве корня.

-Каждый узел имеет ровно два исходящих из него дерева, названные левым поддеревом и правым поддеревом.

-Каждое поддерево само является двоичным деревом, которое можетбыть пустым деревом.

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

Операции с типом: Инициализация дерева пустым набором.
Определение того, является ли дерево пустым.
Определение того, является ли дерево полным.
Определение количества элементов в дереве
Добавление элемента к дереву.
Удаление элемента из дерева.

Поиск элемента в дереве.

Посещение каждого элемента в дереве.


Тема «Создание класса ‘стек’»


Стек (stack)- это список элементов, доступных только в одном конце списка. Элементы удаляются или добавляются из списка только в вершине стека (top).

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

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

Рис. 11 Пример стека.
44

• 
  структуре стека важнейшее место занимают операции добавления и удаления элементов. Операция Push добавляет элемент в вершину стека. Об операции удаления Pop из стека говорят как об извлечении из стека. На рисунке приведена последовательность операций Push и Pop .
  

				С