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

                if (node->right != NULL)

                        return findMax(node->right);

                else

                        return node;

        }

 

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

        {

                return findMax(root);

        }

 

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

        {

                return find(key, root);

        }

 

        private: void calcHeight(cNode* node) //подсчет высоты дерева

        {

                if (node == NULL)

                        return;

                if (node->left != NULL)

                        calcHeight(node->left);

                if (node->right != NULL)

                        calcHeight(node->right);

                if ((node->left == NULL) && (node->right == NULL))

                        node->height = 0;

                else

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

        }

 

        private: void balance(cNode* &node) //балансировка дерева

        {

                if (node != NULL)

                {

                        balance(node->left);  //балансировка левого поддерева

                        balance(node->right); //балансировка правого поддерева

                        if ((node->left != NULL ? node->left->height : -1) - (node->right != NULL ? node->right->height : -1) >= 2) //баланс нарушен в левую сторону

                        {

                                node = singleLeftRotate(node);

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

                        }

                        if ((node->left != NULL ? node->left->height : -1) - (node->right != NULL ? node->right->height : -1) <= -2) //баланс нарушен в правую сторону

                        {

                                node = singleRightRotate(node);

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

                        }

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

                }

        }

 

        private: bool delNode(float key, cNode* &node) //удаление узла

        {

                if (node != NULL)

                {

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

                        {

                                if ((node->left == NULL) && (node->right == NULL)) //удаляемый узел является листом

                                {

                                        free(node);

                                        node = NULL;

                                        return true;

                                }

                                cNode* oldNode = node;

                                if ((node->left == NULL) || (node->right == NULL)) //удаляемый узел имеет одного потомка

                                {

                                        if (node->left != NULL)

                                                node = node->left;

                                        else

                                                node = node->right;

 

                                        return true;

                                }

                                else                                               ////удаляемый узел имеет двух потомков

                                {

                                        cNode* rChild = node->right;

                                        cNode* prev = NULL;

                                        while (rChild->left != NULL)

                                        {

                                                prev = rChild;

                                                rChild = rChild->left;

                                        }

                                        if (node->right != rChild)

                                        {

                                                prev->left = rChild->right;

                                                rChild->right = node->right;

                                        }

                                        rChild->left = node->left;

                                        node = rChild;

                                        calcHeight(node);

                                }

                                free(oldNode);

                                return true;

                        }

                        bool res;

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

                                res = delNode(key, node->left);

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

                                res = delNode(key, node->right);

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

                        return res;

                }

                return false;

        }

 

        public: void Balance() //метод, вызывающий балансировку дерева

        {

                if (IsEmpty())

                        return;

                while (abs((root->left != NULL ? root->left->height : -1) - (root->right != NULL ? root->right->height : -1)) >= 2) //пока баланс в корне не восставновлен

                balance(root);

        }

 

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

        {

                bool res = delNode(key, root);

                if (res)

                        count--;

                if (AVLMode)

                        balance(root);

                return res;

        }

 

        public: void Destroy()  //метод, вызывающий удаление дерева

        {

                makeEmpty(root);

        }

 

        public: bool IsEmpty() //проверка на наличие дерева

        {

                return root == NULL ? true : false;

        }

 

        private: bool tryAddkey(float key, float* keys, int keysCount) //добавление в массив ключа дерева

        {

                bool res = true;

                for (int i = 0; i < keysCount; i++)

                        if (key == keys[i])

                        {

                                res = false;

                                break;

                        }

                if (res)

                        keys[keysCount] = key;

                return res;

        }

 

        private: cNode* getMaxHeightUpTree(cNode* node, float* keys, int &keysCount) //поиск максимального по высоте упорядоченного бинарного поддерва

        {

                if (node == NULL)

                        return NULL;

                cNode* left = NULL;

                cNode* right = NULL;

                left = getMaxHeightUpTree(node->left, keys, keysCount); //ищем в левом поддереве

                right = getMaxHeightUpTree(node->right, keys, keysCount); //ищем в правом поддереве

                if ((node->left == left) && (node->right == right)) //узел является листом

                        //пытаемся добавить ключ узла в массив ключей дерева

                        if (tryAddkey(node->key, keys, keysCount))  //ключ ранее в массиве не в встречался

                        {

                                keysCount++;

                                return node;                        //возвращаем узел как корень наибольшего по высоте поддерева

                        }

                return (left != NULL ? left->height : 0) > (right != NULL ? right->height : 0) ? left : right; //возвращаем узел поддерева-потомка с наибольшой высотой

        }

 

        public: cTree* SearchUpTreeMaxHeight() //метод, вызывающий поиск максимального по высоте упорядоченного бинарного поддерва

        {

                float* keys = new float[count];

                return new cTree(getMaxHeightUpTree(root, keys, 0));

        }

 

        public: void SQRRoot() //возведение клюяа корня в квадрат

        {

                if (!IsEmpty())

                {

                        root->key *= root->key;

                        cNode* rightMin = findMin(root); //поиск минимального узла в правом поддереве

                        if (root->key >rightMin->key)   //ключ корня больше ключа минимального узла в правом поддереве

                        {

                                float key = root->key; //запоминаем ключ корня

                                delNode(key, root);   //удаляем корень из дерева

                                balance(root);        //балансируем дерево

                                InsertNode(root, key, true); //добавляем в дерево ключ старого корня, с последующей балансировкой

                        }

                }

 

        }

};