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

Автор: Пользователь скрыл имя, 22 Июня 2013 в 14:01, курсовая работа

Описание работы

Написать программу, реализующую структуру данных АВЛ-деревья. Программа должна выполнять следующие функции:
Создание дерева.
Добавление узла в дерево.
Удаление узла из дерева.
Поиск узла по значению.
Поиск минимального по значению узла.
Поиск максимального по значению узла.
Восстановление баланса дерева.
Поиск упорядоченного бинарного дерева поиска максимальной высоты.
Вывод дерева на экран в виде рисунка.

Работа содержит 1 файл

ПЗ.docx

— 460.77 Кб (Скачать)

                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); //добавляем в дерево ключ старого корня, с последующей балансировкой

                        }

                }

 

        }

};


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