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

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: сочинение, диплом государственного образца
| Добавил(а) на сайт: Светозар.

Del – удаление элемента из дерева.

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

[pic]

[pic]Например, если просто удалить узел с ключом N, то левый указатель узла с ключом Т должен указывать одновременно на К и R что не возможно. В этом случае удаляемый узел нужно заменить на другой узел из дерева. Возникает вопрос, каким же узлом его заменить? Этот узел должен обладать двумя свойствами: во-первых, он должен иметь не более одного потомка; во-вторых, для сохранения упорядоченности ключей, он должен иметь ключ либо не меньший, чем любой ключ левого поддерева удаляемого узла, либо не больший, чем любой ключ правого поддерева удаляемого узла. Таким свойствам обладают два узла, самый правый узел левого поддерева удаляемого узла и самый левый узел его правого поддерева. Любым из этих узлов им можно заменить удаляемый узел. Например, на рисунке это узлы М и Р.

[pic]Необходимо различать три случая:

1. Узла с ключем, равным х, нет.

2. Узел с ключем, равным х, имеет не более одного потомка.

3. Узел с ключем, равным х, имеет двух потомков

Вспомогательная рекурсивная процедура del вызывается только в случае, когда удаляемый узел имеет двух потомков. Она “спускается вдоль” самой правой ветви левого поддерева удаляемого узла q^ (при вызове процедуры ей передается в качестве параметра указатель на левое поддерево) и, затем, заменяет существенную информацию (в нашем случае ключ data) в q^ соответствующим значением самого правого узла r^ этого левого поддерева, после чего от r^ можно освободиться.

View - печать дерева, обходя его справа налево. Чем дальше элемент от корня, тем больше ему будет предшествовать пробелов, т. о. путём несложного алгоритма получается вполне удобно читаемое дерево.

Exist – проверка существования элемента с заданным ключом. Ищем элемент, двигаясь от корня и переходя на левое или правое поддерево каждого узла в зависимости от его ключа.

Destroy – удаление дерева. Обходя дерево слева направо, удаляет элементы. Сначала удаляются потомки узла, затем сам узел.

Различия между описаниями кодов программах на разных языках относятся в основном к конструкторам и деструкторам. В .pas программах они определяются директивами и вызываются явно как методы класса из программы, а в .cpp конструктор вызывается при создании элемента класса и деструктор автоматически при выходе из программы (для чего объект класса размещается в памяти динамически).

3. Код программы

|program PTree; |#include |
| | |
|{$APPTYPE CONSOLE} |#pragma hdrstop |
| | |
|type |typedef int TInfo; |
|TInfo = Byte; |typedef struct Item* PItem; |
|PItem = ^Item; |struct Item TInfo Key; ; |
|end; |class TTree void Exist(TInfo Key); ; |
|end; | |
|//----------------------------------|//----------------------------------|
|--------------------------- |--------------------------- |
|constructor TTree.Create; |TTree::TTree() |
|begin | |
|//----------------------------------|//----------------------------------|
|--------------------------- |--------------------------- |
|procedure TTree.Add(Key: TInfo); |static void IniTree(PItem& P, TInfo |
| |X) //создание корня дерева |
|procedure IniTree(var P: PItem; X: |TInfo); //создание корня дерева |
|P^.Right := nil; | |
|end; |static void Iendleft (PItem& P, |
| |TInfo X) //добавление узла слева |
|procedure InLeft (var P: PItem; X : |
|
|end; | |
| |static void InRight (PItem& P, TInfo|
|procedure InRight (var P: PItem; X :|X) //добавить узел справа |
|TInfo); //добавить узел справа | |
| | |
|procedure Tree_Add (P: PItem; X : |static void Tree_Add (PItem P, TInfo|
|TInfo); |X) |
|var OK: Boolean; |{ |
|begin |int OK; |
|OK := false; |OK = false; |
|while not OK do begin |while (! OK) { |
|if X > P^.Key then //посмотреть |if (X > P->Key) //посмотреть |
|направо |направо |
|if P^.Right nil //правый узел не |if (P->Right != NULL) //правый узел |
|nil |не NULL |
|then P := P^.Right //обход справа |P = P->Right; //обход справа |
|else begin //правый узел - лист и |else InRight (P, X); //и конец |
|else //посмотреть налево |else //посмотреть налево |
|if P^.Left nil //левый узел не |if (P->Left != NULL) //левый узел не|
|nil |NULL |
|then P := P^.Left //обход слева |P = P->Left; //обход слева |
|else begin //левый узел -лист и надо|else |
|end; //цикла while |} //цикла while |
|end; |} |
| | |
|begin |void TTree::Add(TInfo Key) |
|if Root = nil | |
|then IniTree(Root, Key) |//---------------------------------- |
|procedure TTree.Del(Key: TInfo); |//----------------------------------|
| |---------------------------static |
|procedure Delete (var P: PItem; X: |void delete_ (PItem& P, TInfo X); |
|TInfo); | |
|var Q: PItem; |static void Del(PItem& R, PItem& Q) |
| |//процедура удаляет узел имеющий |
|procedure Del(var R: PItem); |двух потомков, заменяя его на самый |
|//процедура удаляет узел имеющий |правый |
|двух потомков, заменяя его на самый |//узел левого поддерева |
|правый |{ |
|//узел левого поддерева |if (R->Right != NULL) //обойти |
|begin |дерево справа |
|if R^.Right nil then //обойти |Del(R->Right, Q); |
|дерево справа |else Del(R^.Right) |
|Q := R; |} //Del |
|R := R^.Left; | |
|end; |static void delete_ (PItem& P, TInfo|
|end; //Del |X) |
| |{ |
|begin //Delete |PItem Q; |
|if P nil then //искать удаляемый |//Delete |
|узел |if (P != NULL) //искать удаляемый |
|if X < P^.Key then |узел |
|Delete(P^.Left, X) |if (X < P->Key) |
|else |delete_(P->Left, X); |
|if X > P^.Key then |else |
|Delete(P^.Right, X) //искать в |if (X > P->Key) |
|правом поддереве |delete_(P->Right, X); //искать в |
|else begin |правом поддереве |
|//узел найден, надо его удалить | |
|//сохранить ссылку на удаленный узел|else end |
|нет'); |else |
|end; |cout Key) |
|end; |Search (P-> Left, X); |
| |else |
|begin |cout Left); |
|end; |if (P->Right != NULL) |
| |Node_Dispose (P->Right); |
|begin |delete P; |
|Node_Dispose(Root); |} |
|end; |} |
|//----------------------------------| |
|--------------------------- |TTree::~TTree() |
|procedure InputKey(S: String; var | |
|Key: TInfo); |WriteLn(S); |
|ReadLn(Key); |//----------------------------------|
|end; |--------------------------- |
| |void inputKey(string S, TInfo& Key) |
|var |
|
|begin | |
|Tree := TTree.Create; |TTree *Tree = new TTree; |
|repeat |int N; |
|WriteLn('1-Добавить элемент в |TInfo Key; |
|дерево'); |int main(int argc, const char* |
|WriteLn('2-Удалить элемент'); |argv[]) |
|WriteLn('3-Вывести узлы дерева'); |{ |
|WriteLn('4-Проверить существование |do { |
|узла'); |cout