Структуры данных бинарное упорядоченное несбалансированное дерево

Казанский Государственный Технический Университет им. А. Н. Туполева Курсовая работа по программированию на тему Структуры данных: бинарное упорядоченное несбалансированное дерево Выполнил: Зверев И. М. Проверил: Рахматуллин А. И. Казань 2003 План работы: 1)      2)      3)      Pascal и С++ 1.                  Требуется написать программу, реализующую основные

операции работы с деревом. Причём, обязательным условием является использование структуры данных класс для описания дерева и методов работы с ним. 2.                  Описание ведётся для кода на Pascalе, отличия для С++ будут указаны ниже. В программе основным элементом является класс TTree. Его методы – это основные процедуры работы с деревом: Create – конструктор класса – процедура, создающая

дерево, Add – метод добавления элемента в дерево, Del – метод удаления элемента из дерева, View – метод вывода элементов дерева на экран, Exist – метод проверки существования элемента с некоторым ключом, по сути поиск элемента, Destroy – деструктор класса – процедура, удаляющая дерево. Рассмотрим алгоритмы работы процедур. Create – создание дерева. Присваивает полю Root (корень) значение nil – указателя, который никуда не указывает. Add –

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

соответственно справа или слева. Del – удаление элемента из дерева. Удаление узла довольно просто если он является листом или имеет одного потомка. Например, если требуется удалить узел с ключом М надо просто заменить правую ссылку узла К на указатель на L. Трудность заключается в удалении узла с двумя потомками, поскольку мы не можем указать одним указателем на два направления. Узла с ключем, равным х, нет. Узел с ключем, равным х,