Binary наредено дърво
Дървото е нелинейна динамична структура за съхранение на данни. Дървото се състои от възли или върхове, които съдържат полета с данни и указатели към други възли или върхове.
Възел или връх на двоично дърво съдържа поле за данни и две области с указатели. Полетата, които оставите показалеца указатели се наричат (вляво) и дясно (вдясно), тъй като сочи към лявото и дясното-дървото, съответно. NULL стойност показалка е индикация за празен поддърво.
Коренът на дървото определя на входния пункт и областта на показалеца - следващото ниво на събранията. Полето листо възел (листа) съдържа NULL в левия и десния стрелките.
Клас TreeNode обекти са възли на двоичен дърво (Фигура 8.1).
// указатели наляво и надясно възли за деца
TreeNode (Конст вътр т, TreeNode * LPTR = NULL,
// функционални елементи на достъп до полетата на указатели
TreeNode * наляво () конст;
TreeNode * Право () Конст;
Конструктор инициализира областта на данни и указатели. С помощта на нулев указател NULL възли се инициализират като листа. С показалеца P TreeNode клас обект като параметър, дизайнерът добавя P като ляв или десен дете на новия възел. Функционални елементи Ляв () и десния () връща стойността на области на левия и десния стрелките. С този клас клиентът има достъп до деца на лявата и дясната възела.
// указатели число дърво възел
TreeNode * корен, * LP, * RP;
// създаване на листа, които съдържат 20 и 30, като данните
LP = нов TreeNode (20);
RP = нов TreeNode (30);
// създаде корен, съдържащ номера 10 и две потомци
корен = нов TreeNode (10, LP, RP);
Фигура 8.1 - двоично дърво
директорията за> данни = 50; // определя основата 50
// конструктор инициализира полетата с данни и индекси
// NULL стойност съответства на празна поддърво
TreeNode. TreeNode (Конст вътр т, TreeNode * LP,
TreeNode * RP): данни (т), наляво (LP), десен (RP)
Binary наредено дърво (дървото за търсене)
Binary търсене дърво - структура (фигура 8.2), който организира елементите посредством връзката "<”. Чтобы сравнить узлы дерева, подразумевают, что часть или все поле данных определено в качестве ключа и операция “<” сравнивает ключи при размещении элемента на дереве.
Binary търсене дърво е изработена от следното правило:
За всеки възел, стойностите на данни в ляво-дървото е по-малък, отколкото този възел, а в дясната-дървото - повече.
Дървото се нарича търсенето, тъй като търсенето на даден елемент (основен) може да отиде само на доста специфичен начин. Като се започне от корена, сканирани лявото поддърво, ако ключовата стойност е по-малка от текущия възел. В противен случай сканиране на дясното-дървото. Методът на създаване на дървото ви позволява да търсите най-краткия път от корена. Двоично дърво за търсене са предназначени за бърз достъп до данните. В идеалния случай, дървото е балансиран и е с височина и ефективността на поръчка търсене
Фигура 8.2 - двоично наредено дърво
За обработка на данните, съхранявани в дървото, се използват следните методи за предаване на дърво:
ляво поддърво, дясно поддърво възел. метод или симетричен;
ляво поддърво, дясно поддърво възел. или обратно метод;
прав под-Node- ляво поддърво. или от дясно на ляво;
възел на ляво-дървото, нали поддървото. или отгоре-надолу.
За изпълнение на рекурсивни алгоритми използват методи.
Целта на този клас е двоичен подредени дърво (например - на фигура 8.2).
// клас - двоично дърво
// премахване на всички възли на дървото
невалидни DeleteTree (TreeNode * т);
// получим указател - с възел с елемента и неговата майка
TreeNode * FindNode (Конст вътр т,
Алгоритъм за отстраняване дърво възли приложени елементи функция DeleteTree и използва-елемент функция ClearTree. призован като деструктор и претоварен операция задача.
Функционални елементи Намери и Insert започне от корена и се използва определението за двоично дърво за търсене. Алгоритъмът е на прав поддърво, ключ, или когато един нов елемент е по-голяма, отколкото на текущия възел. В противен случай, преминаването се простира от ляво-дървото. Функция Element Намери със затворен FindNode функция елемент. получаване като параметър ключа и осъществява преминаването от дървото. Функцията връща указател към съответстващата възел и неговата майка показалеца. Ако мачът се случва в зародиш, показалеца родител е NULL.
Функция-Delete изтрива елемент от дърво с дадена ключова възел. Първо, с помощта на функция-елемент е разположен FindNode място на възел в дървото и определената показалеца си майка. Ако целевият възел е на линия, операцията по изтриване свършва.
Изтриване на възел от дървото изисква поредица от тестове, за да се определи къде да се свържете на възел, за да бъде изтрита синове. Поддървета трябва да се поставя повторно по такъв начин, че да се запази структурата на двоично наредено дърво.
функция FindNode DNodePtr връща указател към възела Г. бъдат изтрити. Вторият показалеца, PNodePtr. P идентифицира възела - възел майка да бъдат изтрити. Изтриване функция се "опитва" да се намери замяна възел R., която е прикрепена към основната и следователно заема мястото на отдалечения възел. Смяната възел R Посочената указател RNodePtr.
Функция Delete алгоритъм за търсене изпълнява подмяна единица от четирите случая, в зависимост от броя и местоположението на синовете на изтрити възел. Имайте предвид, че ако показалеца родител е NULL. се заличава и се актуализира корен. Тази ситуация се взема под внимание от алгоритъма.
Целта на тази функция е да учи алгоритми и функции за работа с двоично наредено дърво по примера на дървото на числа.
Избор, разположенията и за настройка на компоненти свойства.
Кодекси за класове, функции и обработват събитие
Запазване на основния модул форма на име LR_8, и проекта - име PR_LR_8.
За да се настанят на класовете в проекта използва модулите, които не са свързани с формата. Клас за един възел на дървото е обявена и е определено в f_8_1 файл и клас за двоично дърво - в f_8_2 модул. По-долу са заглавните файлове и файлове с изпълнение на тези модули на.
f_8_1.h модул f_8_1 на заглавния файл (без форма)
#include
// BinSTree зависи TreeNode
// променлива newnode показва новия възел, който е създаден
// чрез Call GetTreeNode закрепен и впоследствие
// новия възел и предава като параметри в GetTreeNode
TreeNode * newlptr, * newrptr, * newnode;
// спре рекурсивни канала, като празен дърво
// ако е така, то създава копие от него. в противен случай тя връща
// и го затвори синове
анулира __fastcall RadioButton2Click (TObject * Sender);
анулира __fastcall RadioButton1Click (TObject * Sender);
анулира __fastcall ExitExecute (TObject * Sender);
анулира __fastcall OutMemoExecute (TObject * Sender);
анулира __fastcall InsertExecute (TObject * Sender);
анулира __fastcall BitBtn1Click (TObject * Sender);
анулира __fastcall ClearMemoExecute (TObject * Sender);
анулира __fastcall ClearTreeExecute (TObject * Sender);
анулира __fastcall CountLeafExecute (TObject * Sender);
анулира __fastcall DepthExecute (TObject * Sender);
анулира __fastcall FindExecute (TObject * Sender);
анулира __fastcall DeleteExecute (TObject * Sender);
частни: // декларации за потребителя
обществени: // декларации потребителя
__fastcall TForm1 (TComponent * собственика);
екстернант ПАКЕТ TForm1 * Form1;
Прехвърляме формата на компонентите и определете стойностите им собственост. В допълнение, от страницата - LabeledEdit1 (EditLabel-> Надпис - Key, Text - 10), ActionManager1 действие мениджър и съблича ActionMainMenuBar1 главното меню. По подразбиране банда главното меню ActionMainMenuBar1 намира в горната част, по цялата ширина на формата. Попитай я имот Align = alNone, за да му се даде желания размер и място на правилното място.
След това, с вложка Win32 страница под формата на ImageList1 от стандарта страница - Label1 (Надпис - ДЪРВО), Memo1, GroupBox1 (Надпис - Формиране на дърво). Панел GroupBox1 трансфер: от стандарта страница - два бутона за избор - RadioButton1 (с надписи - ръчно Проверени - вярно Enabled - вярно ..) И RadioButton2 (с надписи - автоматично Проверени - фалшива Enabled - вярно ..), LABEL2 (Надпис - броят на възли) Button1 (надпис - Добавяне възел), BUTTON2 (надпис - Премахване възел) от примерите страница - CSpinEdit1 (MAXVALUE - 100, MINVALUE - 1, стойност - 10) от страницата Advanced - BitBtn1 (надпис - START), LabeledEdit2 (EditLabel- > надпис - число, текст - 10).
Заредете компонент ImageList1 fldropen икони на файлове. filesave. флопи. намери. вмъкнете. ясен. изтриете. arrow2d. изтриете. dooropen. directry. В ActionManager1 компоненти изображения, собственост на равно ImageList1, като свързва действието контролер със списък от изображения.
Добави към формата с помощта на контролер действия лентата с инструменти ActionManager1 ActionTollBar1, определен за него Изравнете = alNone, Constraints-> MaxHeight = 230, Constraints-> MinHeight = 230 и го поставете върху по образец съгласно ris.8.3.
имот за действие Button1 Бутонът (Надпис - Добавяне на този уеб сайт) и BUTTON2 (Надпис - Изтриване на възел), съответно, се съхранява стойностите Поставете и Delete.
Действия по активиране и инициализация на компоненти и със събития, са изброени в изпълнение LR_8.cpp LR_8 модул файла.
файл изпълнение LR_8.cpp модул LR_8 на