Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Структуры данных бинарное упорядоченное несбалансированное дерево
Раздел: Рефераты по информатике
Тип: реферат Добавлен 09:32:55 02 марта 2011 Похожие работы
Просмотров: 7 Комментариев: 27 Оценило: 2 человек Средний балл: 5 Оценка: неизвестно     Скачать

Казанский Государственный Технический Университет

им. А. Н. Туполева

Курсовая работа

по программированию

на тему

Структуры данных:

бинарное упорядоченное несбалансированное дерево

Выполнил: Зверев И. М.

Проверил: Рахматуллин А. И.

Казань

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 Add(Key: TInfo);

procedure Del(Key: TInfo);

procedure View;

procedure Exist(Key: TInfo);

destructor Destroy; override;

end;

//-------------------------------------------------------------

constructor TTree.Create;

begin

Root := nil;

end;

//-------------------------------------------------------------

procedure TTree.Add(Key: TInfo);

procedure IniTree(var P: PItem; X: TInfo); //создание корня дерева

begin

New(P);

P^.Key :=X;

P^.Left := nil;

P^.Right := nil;

end;

procedure InLeft (var P: PItem; X : TInfo); //добавление узла слева

var R : PItem;

begin

New(R);

R^.Key := X;

R^.Left := nil;

R^.Right := nil;

P^.Left := R;

end;

procedure InRight (var P: PItem; X : TInfo); //добавить узел справа

var R : PItem;

begin

New(R);

R^.Key := X;

R^.Left := nil;

R^.Right := nil;

P^.Right := R;

end;

procedure Tree_Add (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 //левый узел -лист и надо добавить к нему элемент

InLeft(P, X); //и конец

OK := true

end;

end; //цикла while

end;

begin

if Root = nil

then IniTree(Root, Key)

else Tree_Add(Root, Key);

end;

//-------------------------------------------------------------

procedure TTree.Del(Key: TInfo);

procedure Delete (var P: PItem; X: TInfo);

var Q: PItem;

procedure Del(var R: PItem);

//процедура удаляет узел имеющий двух потомков, заменяя его на самый правый

//узел левого поддерева

begin

if R^.Right <> nil then //обойти дерево справа

Del(R^.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

Delete(P^.Left, X)

else

if X > P^.Key then

Delete(P^.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 //узел имеет двух потомков

Del(Q^.Left);

Dispose(Q);

end

else

WriteLn('Такого элемента в дереве нет');

end;

begin

Delete(Root, Key);

end;

//-------------------------------------------------------------

procedure TTree.View;

procedure PrintTree(R: PItem; L: Byte);

var i: Byte;

begin

if R <> nil then begin

PrintTree(R^.Right, L + 3);

for i := 1 to L do

Write(' ');

WriteLn(R^.Key);

PrintTree(R^.Left, L + 3);

end;

end;

begin

PrintTree (Root, 1);

end;

//-------------------------------------------------------------

procedure TTree.Exist(Key: TInfo);

procedure Search(var 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

Search(Root, Key);

end;

//-------------------------------------------------------------

destructor TTree.Destroy;

procedure Node_Dispose(P: PItem);

//Удаление узла и всех его потомков в дереве

begin

if P <> nil then begin

if P^.Left <> nil then

Node_Dispose (P^.Left);

if P^.Right <> nil then

Node_Dispose (P^.Right);

Dispose(P);

end;

end;

begin

Node_Dispose(Root);

end;

//-------------------------------------------------------------

procedure InputKey(S: String; var Key: TInfo);

begin

WriteLn(S);

ReadLn(Key);

end;

var

Tree: TTree;

N: Byte;

Key: TInfo;

begin

Tree := TTree.Create;

repeat

WriteLn('1-Добавить элемент в дерево');

WriteLn('2-Удалить элемент');

WriteLn('3-Вывести узлы дерева');

WriteLn('4-Проверить существование узла');

WriteLn('5-Выход');

ReadLn(n);

with Tree do begin

case N of

1: begin

InputKey('Введите значение добавляемого элемента', Key);

Add(Key);

end;

2: begin

InputKey('Введите значение удаляемого элемента', Key);

Del(Key);

end;

3: View;

4: begin

InputKey('Введите элемент, существование которого вы хотите проверить', Key);

Exist(Key);

end;

end;

end;

until N=5;

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 Add(TInfo Key);

void Del(TInfo Key);

void View();

void Exist(TInfo Key);

~TTree();

};

//-------------------------------------------------------------

TTree::TTree()

{

Root = NULL;

}

//-------------------------------------------------------------

static void IniTree(PItem& 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 Tree_Add (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 { //левый узел -лист и надо добавить к нему элемент

Iendleft(P, X); //и конец

OK = true;

}

} //цикла while

}

void TTree::Add(TInfo Key)

{

if (Root == NULL)

IniTree(Root, Key);

else Tree_Add(Root, Key);

}

//-------------------------------------------------------------static void delete_ (PItem& P, TInfo X);

static void Del(PItem& R, PItem& Q)

//процедура удаляет узел имеющий двух потомков, заменяя его на самый правый

//узел левого поддерева

{

if (R->Right != NULL) //обойти дерево справа

Del(R->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)

delete_(P->Left, X);

else

if (X > P->Key)

delete_(P->Right, X); //искать в правом поддереве

else {

//узел найден, надо его удалить

//сохранить ссылку на удаленный узел

Q = P;

if (Q->Right == NULL)

//справа NULL

//и ссылку на узел надо заменить ссылкой на этого потомка

P = Q->Left;

else

if (Q->Left == NULL)

//слева NULL

//и ссылку на узел надо заменить ссылкой на этого потомка

P = P->Right;

else //узел имеет двух потомков

Del(Q->Left, Q);

delete Q;

}

else

cout << "Такого элемента в дереве нет" << endl;

}

void TTree::Del(TInfo Key)

{

delete_(Root, Key);

}

//-------------------------------------------------------------

static void PrintTree(PItem R, TInfo L)

{

int i;

if (R != NULL) {

PrintTree(R->Right, L + 3);

for( i = 1; i <= L; i ++)

cout << ' ';

cout << R->Key << endl;

PrintTree(R->Left, L + 3);

}

}

void TTree::View()

{

PrintTree (Root, 1);

}

//-------------------------------------------------------------

static void Search(PItem& 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 TTree::Exist(TInfo Key)

{

Search(Root, Key);

}

//-------------------------------------------------------------

static void Node_Dispose(PItem P)

//Удаление узла и всех его потомков в дереве

{

if (P != NULL) {

if (P->Left != NULL)

Node_Dispose (P->Left);

if (P->Right != NULL)

Node_Dispose (P->Right);

delete P;

}

}

TTree::~TTree()

{

Node_Dispose(Root);

}

//-------------------------------------------------------------

void inputKey(string S, TInfo& Key)

{

cout << S << endl;

cin >> Key;

}

TTree *Tree = new TTree;

int N;

TInfo Key;

int main(int 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->Add(Key);

}

break;

case 2: {

inputKey("Введите значение удаляемого элемента", Key);

Tree->Del(Key);

}

break;

case 3: Tree->View(); break;

case 4: {

inputKey("Введите элемент, существование которого вы хотите проверить", Key);

Tree->Exist(Key);

}

break;

}

}

} while (!(N==5));

return EXIT_SUCCESS;

}

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита10:54:38 05 ноября 2021
.
.10:54:36 05 ноября 2021
.
.10:54:35 05 ноября 2021
.
.10:54:34 05 ноября 2021
.
.10:54:32 05 ноября 2021

Смотреть все комментарии (27)
Работы, похожие на Реферат: Структуры данных бинарное упорядоченное несбалансированное дерево

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(291944)
Комментарии (4203)
Copyright © 2005-2022 BestReferat.ru support@bestreferat.ru реклама на сайте

Рейтинг@Mail.ru