Реализовать программу для работы с типом данных ”Дерево”

        {

                outputMemo->Lines->Add("Элемент " + FloatToStr(key) + " удален.");

                ClearPaintField();

                curTree->DrawTree(Form1);

        }

        else                                               //узел не найден

                outputMemo->Lines->Add("Элемент " + FloatToStr(key) + " не найден.");

}

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

 

void __fastcall TForm1::blncBtnClick(TObject *Sender)      //балансировка

{

        curTree->Balance(); //балансируем

        ClearPaintField();

        curTree->DrawTree(Form1);

}

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

 

 

void __fastcall TForm1::srchUpBinTreeMaxHghtBtnClick(TObject *Sender) //поиск максимального по высоте упорядоченного дерева

{

        cTree* tree = curTree->SearchUpTreeMaxHeight(); //получаем это дерево

        tree->SetDRAW_Y_START(250);

        ClearPaintField();

        curTree->DrawTree(Form1);

        tree->DrawTree(Form1);

}

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

 

void __fastcall TForm1::rootSQRBtnClick(TObject *Sender) //возведение ключа корня в квадрат и восставновление баланса

{

        curTree->SQRRoot();

        ClearPaintField();

        curTree->DrawTree(Form1);

}

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

 

Unit 2

 

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

 

 

#pragma hdrstop

 

#include "Unit2.h"

#include "math.h"

#include <vcl.h>

#include <memory.h>

 

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

 

#pragma package(smart_init)

 

#define DRAW_Y_STEP 30        //расстояние между узлами по вертикали

#define DRAW_X_START 660      //позиция корня узла по горизонтали

//#define DRAW_Y_START 20

#define DRAW_X_SHIFT_UNIT 13  //расстояние между листьями по горизонтали

 

class cNode //класс узла дерева

{

        public: float key;    //ключ узла

        public: cNode* left;  //левый дочерний узел

        public: cNode* right; //правый дочерний узел

        //public: cNode* parent; //родительский узел

        public: int height; //высота поддерева

 

        public: cNode(float key, cNode* left, cNode* right, cNode* parent, int height) //конструктор узла

        {

                this->key = key;

                this->left = left;

                this->right = right;

                this->height = height;

        }

 

        public: String ToString() //преобразование узла в строку

        {

                return "key: " + FloatToStr(this->key) + "; " + "Левый потомок: " + (this->left != NULL ? FloatToStr(this->left->key) : (String)"отсутствует") + "; " + "Правый потомок: " + (this->right != NULL ? FloatToStr(this->right->key) : (String)"отсутствует");

        }

};

 

class cTree //класс дерева

{

        cNode* root; //корень дерева;

        int count;   //количество узлов в дереве

 

        public: int DRAW_Y_START;

 

        public: cTree(cNode* root) //конструктор дерева

        {

                this->root = root;

                this->count = 1;

                DRAW_Y_START = 20;

        }

 

        public: cTree(float key) //конструктор дерева

        {

                this->root = new cNode(key, NULL, NULL, NULL, 0);

                this->count = 1;

                DRAW_Y_START = 20;

        }

 

        public: void SetDRAW_Y_START(int y) //изменение позиции корня по вертикали

        {

                DRAW_Y_START = y;

        }

 

        private: int max(int a, int b) //возвращает максимальное значение из 2-х

        {

                return a < b ? b : a;

        }

 

        private: cNode* singleLeftRotate(cNode* root) //одинарное левое вращение

        {

                cNode* left = root->left;

                root->left = left->right;

                left->right = root;

                root->height = max(root->left != NULL ? root->left->height : -1, root->right != NULL ? root->right->height : -1) + 1;

                left->height = max(left->left != NULL ? left->left->height : 0, root != NULL ? root->height : 0) + 1;

                return left;

        }

 

        private: cNode* singleRightRotate(cNode* root) //одинарное правое вращение

        {

                cNode* right = root->right;

                root->right = right->left;

                right->left = root;

                root->height = max(root->left != NULL ? root->left->height : -1, root->right != NULL ? root->right->height : -1) + 1;

                right->height = max(right->right != NULL ? right->right->height : 0, root != NULL ? root->height : 0) + 1;

                return right;

        }

 

        private: cNode* doubleLeftRotate(cNode* root) //право-левое вращение

        {

                root->left = singleRightRotate(root->left);

                return singleLeftRotate(root);

        }

 

        private: cNode* doubleRightRotate(cNode* root) //лево-правое вращение

        {

                root->right = singleLeftRotate(root->right);

                return singleRightRotate(root);

        }

 

        private: void InsertNode(cNode* &node, float key, bool AVLMode) //добавление узла

        {

                if (IsEmpty()) //проверка на наличие корня

                {

                        root = new cNode(key, NULL, NULL, node, 0); //добавляем корень

                        count = 1;

                        return;

                }

                if (key < node->key)  //идем в лево

                        if (node->left == NULL) //левый потомок отсутствует

                                node->left = new cNode(key, NULL, NULL, node, 0); //создаем новый узел

                        else                    //левый потомок присутствует

                        {

                                InsertNode(node->left, key, AVLMode); //опускаемся в левое поддерево

                                if (AVLMode)                          //необходимо проверить баланс узла

                                        if (node->left->height - (node->right != NULL ? node->right->height : -1) == 2) //нарушено условие: левое поддерево выше правого более чем на 1 узел

                                                if (key < node->left->key) //новый узел ушел влево

                                                        node = singleLeftRotate(node);

                                                else                       //новый узел ушел вправо

                                                        node = doubleLeftRotate(node);

                        }

                else                 //идем в право

                        if (node->right == NULL) //правый потомок отсутсвует

                                node->right = new cNode(key, NULL, NULL, node, 0); //создаем новый узел

                        else

                        {

                                InsertNode(node->right, key, AVLMode); //опускаемся в правое поддерево

                                if (AVLMode)                           //необходимо проверить баланс узла

                                        if (node->right->height - (node->left != NULL ? node->left->height : -1) == 2) //нарушено условие: правое поддерево выше левого более чем на 1 узел

                                                if (key >= node->right->key)

                                                        node = singleRightRotate(node);

                                                else

                                                        node = doubleRightRotate(node);

                        }

                node->height = max(node->left != NULL ? node->left->height : 0, node->right != NULL ? node->right->height : 0) + 1;

        }

 

        private: void draw(TForm *form, cNode* node, int level, int x, int y)  //отрисовка дерева

        {

                if (node == NULL)

                        return;

                form->Canvas->TextOutA(x, y, FloatToStr(node->key) + "::" + FloatToStr((node->left != NULL ? node->left->height : -1) - (node->right != NULL ? node->right->height : -1))); //рисуем узел

                //рекурсивный обход дерева в глубину

                if (node->left != NULL)

                {

                        form->Canvas->MoveTo(x + 6, y + 12);

                        int child_x = x - DRAW_X_SHIFT_UNIT * pow(2, root->height - level - 1);

                        int child_y = y + DRAW_Y_STEP;

                        form->Canvas->LineTo(child_x + 6, child_y);

                        draw(form, node->left, level + 1, child_x, child_y);

                }

                if (node->right != NULL)

                {

                        form->Canvas->MoveTo(x + 6, y + 12);

                        int child_x = x + DRAW_X_SHIFT_UNIT * pow(2, root->height - level - 1);

                        int child_y = y + DRAW_Y_STEP;

                        form->Canvas->LineTo(child_x + 6, child_y);

                        draw(form, node->right, level + 1, child_x, child_y);

                }

        }

 

        public: void DrawTree(TForm *form) //метод, вызывающий вывод дерева

        {

                draw(form, root, 0, DRAW_X_START, DRAW_Y_START);

        }

 

        public: void AddNode(float key, bool AVLMode) //метод, вызывающий добавление узла

        {

                InsertNode(root, key, AVLMode);

                count++;

        }

 

        private: void makeEmpty(cNode* node) //удаление дерева

        {

                if (node->left != NULL)

                        makeEmpty(node->left);

                if (node->right != NULL)

                        makeEmpty(node->right);

                free(node);

        }

 

        private: cNode* find(key, cNode* node) //поиск по заданому ключу

        {

                if (node == NULL)

                        return NULL;

                if (key == node->key) //узел найден

                        return node;

                else                  //продолжаем искать

                        if (key < node->key)  //искомый ключ находится в левом поддереве

                                if (node->left != NULL)

                                        return find(key, node->left);

                                else return NULL; //узла с искомым ключом нет

                        else                  //искомый ключ находится в правом поддереве

                                if (node->right != NULL)

                                        return find(key, node->right);

                                else return NULL; //узла с искомым ключом нет

        }

 

        private: cNode* findMin(cNode* node) //поиск узла с минимальным ключом

        {

                if (node == NULL)

                        return NULL;

                if (node->left != NULL)

                        return findMin(node->left);

                else

                        return node;

        }

 

        public: cNode* FindMin() //метод, вызывающий поиск минимального ключа

        {

                return findMin(root);

        }

 

        private: cNode* findMax(cNode* node) //поиск узла с максимальным ключом

        {

                if (node == NULL)

                        return NULL;