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

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

Код программы на языках Pascal и С 1. Постановка задачи Требуется написать программу, реализующую основные операции работы с деревом. Причм, обязательным условием является использование структуры данных класс для описания дерева и методов работы с ним. 2. Описание программы Описание ведтся для кода на Pascalе, отличия для С будут указаны ниже. В программе основным элементом является класс

TTree. Его методы это основные процедуры работы с деревом Create конструктор класса процедура, создающая дерево, Add метод добавления элемента в дерево, Del метод удаления элемента из дерева, View метод вывода элементов дерева на экран, Exist метод проверки существования элемента с некоторым ключом, по сути поиск элемента, Destroy деструктор класса процедура, удаляющая дерево.

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

то, если узел не лист, обходим его справа. Если добавляемый элемент имеет ключ не больший чем ключ узла, то, если узел не лист, обходим его слева. Если дошли до листа, то добавляем элемент соответственно справа или слева. Del удаление элемента из дерева. Удаление узла довольно просто если он является листом или имеет одного потомка. Например, если требуется удалить узел с ключом М надо просто заменить правую ссылку узла

К на указатель на L. Трудность заключается в удалении узла с двумя потомками, поскольку мы не можем указать одним указателем на два направления. Например, если просто удалить узел с ключом N, то левый указатель узла с ключом Т должен указывать одновременно на К и R что не возможно. В этом случае удаляемый узел нужно заменить на другой узел из дерева. Возникает вопрос, каким же узлом его заменить Этот узел должен обладать двумя свойствами во-первых,

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

Например, на рисунке это узлы М и Р. Необходимо различать три случая 1. Узла с ключем, равным х, нет. 2. Узел с ключем, равным х, имеет не более одного потомка. 3. Узел с ключем, равным х, имеет двух потомков Вспомогательная рекурсивная процедура del вызывается только в случае, когда удаляемый узел имеет двух потомков. Она спускается вдоль самой правой ветви левого поддерева удаляемого узла q при вызове процедуры ей

передается в качестве параметра указатель на левое поддерево и, затем, заменяет существенную информацию в нашем случае ключ data в q соответствующим значением самого правого узла r этого левого поддерева, после чего от r можно освободиться. View - печать дерева, обходя его справа налево. Чем дальше элемент от корня, тем больше ему будет предшествовать пробелов, т. о. путм несложного алгоритма получается вполне удобно читаемое дерево. Exist проверка существования элемента с заданным ключом.

Ищем элемент, двигаясь от корня и переходя на левое или правое поддерево каждого узла в зависимости от его ключа. Destroy удаление дерева. Обходя дерево слева направо, удаляет элементы. Сначала удаляются потомки узла, затем сам узел. Различия между описаниями кодов программах на разных языках относятся в основном к конструкторам и деструкторам. В .pas программах они определяются директивами и вызываются явно как методы класса из программы, а

в .cpp конструктор вызывается при создании элемента класса и деструктор автоматически при выходе из программы для чего объект класса размещается в памяти динамически. 3. Код программы program PTree APPTYPE CONSOLE type TInfo Byte PItem Item Item record Key TInfo Left, Right PItem end TTree class private Root PItem public constructor

Create procedure AddKey TInfo procedure DelKey TInfo procedure View procedure ExistKey TInfo destructor Destroy override end constructor TTree.Create begin Root nil end procedure TTree.AddKey TInfo procedure IniTreevar P PItem X TInfo создание корня дерева begin NewP P.Key X P.Left nil P.Right nil end procedure InLeft var

P PItem X Item begin NewR R.Key X R.Left nil R.Right nil P.Left R end procedure InRight var P PItem X Item begin NewR R.Key X R.Left nil R.Right nil P.Right R end procedure TreeAdd P PItem X TInfo var OK

Boolean begin OK false while not OK do begin if X P.Key then посмотреть направо if P.Right nil правый узел не nil then P P.Right обход справа else begin правый узел - лист и надо добавить к нему элемент InRight P, X и конец OK true end else посмотреть налево if P.Left nil левый узел не nil then P P.Left обход слева else begin левый узел -лист и надо добавить к

нему элемент InLeftP, X и конец OK true end end цикла while end begin if Root nil then IniTreeRoot, Key else TreeAddRoot, Key end procedure TTree.DelKey TInfo procedure Delete var P PItem X TInfo var Q PItem procedure Delvar R PItem процедура удаляет узел имеющий двух потомков, заменяя его на самый правый узел левого поддерева begin if R.Right nil then обойти дерево справа

DelR.Right else begin дошли до самого правого узла заменить этим узлом удаляемый Q.Key R.Key Q R R R.Left end end Del begin Delete if P nil then искать удаляемый узел if X P.Key then DeleteP.Left, X else if X P.Key then DeleteP.Right, X искать в правом поддереве else begin узел найден, надо его удалить сохранить ссылку на удаленный узел Q P if

Q.Right nil then справа nil и ссылку на узел надо заменить ссылкой на этого потомка P Q.Left else if Q.Left nil then слева nil и ссылку на узел надо заменить ссылкой на этого потомка P P.Right else узел имеет двух потомков DelQ.Left DisposeQ end else WriteLnТакого элемента в дереве нет end begin DeleteRoot, Key end procedure TTree.View procedure PrintTreeR

PItem L Byte var i Byte begin if R nil then begin PrintTreeR.Right, L 3 for i 1 to L do Write WriteLnR.Key PrintTreeR.Left, L 3 end end begin PrintTree Root, 1 end procedure TTree.ExistKey TInfo procedure Searchvar P PItem X TInfo begin if P nil then begin WriteLnТакого элемента нет end else if

X P. Key then ищется в правом поддереве Search P. Right, X else if X P. Key then Search P. Left, X else WriteLnЕсть такой элемент end begin SearchRoot, Key end destructor TTree.Destroy procedure NodeDisposeP PItem Удаление узла и всех его потомков в дереве begin if P nil then begin if P.Left nil then NodeDispose P.Left if

P.Right nil then NodeDispose P.Right DisposeP end end begin NodeDisposeRoot end procedure InputKeyS String var Key TInfo begin WriteLnS ReadLnKey end var Tree TTree N Byte Key TInfo begin Tree TTree.Create repeat WriteLn1-Добавить элемент в дерево WriteLn2-Удалить элемент WriteLn3-Вывести узлы дерева

WriteLn4-Проверить существование узла WriteLn5-Выход ReadLnn with Tree do begin case N of 1 begin InputKeyВведите значение добавляемого элемента, Key AddKey end 2 begin InputKeyВведите значение удаляемого элемента, Key DelKey end 3 View 4 begin InputKeyВведите элемент, существование которого вы хотите проверить, Key ExistKey end end end until N5 Tree.Destroy end. include iostream.h pragma hdrstop typedef int

TInfo typedef struct Item PItem struct Item TInfo Key PItem Left, Right class TTree private PItem Root public TTree void AddTInfo Key void DelTInfo Key void View void ExistTInfo Key TTree TTreeTTree Root NULL static void IniTreePItem P, TInfo X создание корня дерева P new

Item P- Key X P- Left NULL P- Right NULL static void Iendleft PItem P, TInfo X добавление узла слева PItem R R new Item R- Key X R- Left NULL R- Right NULL P- Left R static void InRight PItem P, TInfo X добавить узел справа PItem R R new Item R- Key X R- Left NULL R- Right NULL

P- Right R static void TreeAdd PItem P, TInfo X int OK OK false while OK if X P- Key посмотреть направо if P- Right NULL правый узел не NULL P P- Right обход справа else правый узел - лист и надо добавить к нему элемент InRight P, X и конец OK true else посмотреть налево if P- Left NULL левый узел не NULL P P- Left обход слева else левый узел -лист и надо добавить к нему элемент

IendleftP, X и конец OK true цикла while void TTreeAddTInfo Key if Root NULL IniTreeRoot, Key else TreeAddRoot, Key static void delete PItem P, TInfo X static void DelPItem R, PItem Q процедура удаляет узел имеющий двух потомков, заменяя его на самый правый узел левого поддерева if R- Right NULL обойти дерево справа DelR-

Right, Q else дошли до самого правого узла заменить этим узлом удаляемый Q- Key R- Key Q R R R- Left Del static void delete PItem P, TInfo X PItem Q Delete if P NULL искать удаляемый узел if X P- Key deleteP- Left, X else if X P- Key deleteP- Right, X искать в правом поддереве else узел найден, надо его удалить сохранить ссылку на удаленный

узел Q P if Q- Right NULL справа NULL и ссылку на узел надо заменить ссылкой на этого потомка P Q- Left else if Q- Left NULL слева NULL и ссылку на узел надо заменить ссылкой на этого потомка P P- Right else узел имеет двух потомков DelQ- Left, Q delete Q else cout Такого элемента в дереве нет endl void TTreeDelTInfo Key deleteRoot, Key static void PrintTreePItem

R, TInfo L int i if R NULL PrintTreeR- Right, L 3 for i 1 i L i cout cout R- Key endl PrintTreeR- Left, L 3 void TTreeView PrintTree Root, 1 static void SearchPItem P, TInfo X if P NULL cout Такого элемента нет endl else if X P- Key ищется в правом поддереве Search P- Right,

X else if X P- Key Search P- Left, X else cout Есть такой элемент endl void TTreeExistTInfo Key SearchRoot, Key static void NodeDisposePItem P Удаление узла и всех его потомков в дереве if P NULL if P- Left NULL NodeDispose P- Left if P- Right NULL NodeDispose P- Right delete P TTreeTTree NodeDisposeRoot void inputKeystring

S, TInfo Key cout S endl cin Key TTree Tree new TTree int N TInfo Key int mainint argc, const char argv do cout 1-Добавить элемент в дерево endl cout 2-Удалить элемент endl cout 3-Вывести узлы дерева endl cout 4-Проверить существование узла endl cout 5-Выход endl cin N switch N case 1 inputKeyВведите значение добавляемого элемента, Key Tree- AddKey break case 2 inputKeyВведите значение удаляемого элемента,

Key Tree- DelKey break case 3 Tree- View break case 4 inputKeyВведите элемент, существование которого вы хотите проверить, Key Tree- ExistKey break while N5 return EXITSUCCESS