From a636f8b6bf4202c9cc78262ab9f42bdc842372a7 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Mon, 26 Dec 2022 09:09:33 +0200 Subject: [SDP/S09] Added solutions to all but the last two exericses --- .../09-Seminar-07.12.2022/exercises.cpp | 168 +++++++++++++++ .../09-Seminar-07.12.2022/tree-utils.h | 236 +++++++++++++++++++++ 2 files changed, 404 insertions(+) create mode 100644 Year 2/Structures and data algorithms/09-Seminar-07.12.2022/exercises.cpp create mode 100644 Year 2/Structures and data algorithms/09-Seminar-07.12.2022/tree-utils.h diff --git a/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/exercises.cpp b/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/exercises.cpp new file mode 100644 index 0000000..4e72328 --- /dev/null +++ b/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/exercises.cpp @@ -0,0 +1,168 @@ +#include "./tree-utils.h" +#include + +// Exercise 1 + +template +bool isBST(Tree* tree) { + if (tree == nullptr) return true; + return (tree->left == nullptr || tree->left->data < tree->data) + && (tree->right == nullptr || tree->data < tree->right->data) + && isBST(tree->left) && isBST(tree->right); +} + +void ex1() { + Tree* t = new Tree(8, new Tree(3, new Tree(1), new Tree(6, new Tree(4), new Tree(7))), new Tree(10, nullptr, new Tree(14, new Tree(13)))); + std::cout << isBST(t) << std::endl; + + freeTree(t); +} + +// Exercise 2 + +template +void recBuildBST(std::vector& vec, int start, int end, Tree*& parent) { + int mid = start + (end - start) / 2; + Tree* current = new Tree(vec[mid]); + + if (parent == nullptr) + parent = current; + + if (current->data < parent->data) + parent->left = current; + else if (parent->data < current->data) + parent->right = current; + + if (mid - start > 0) + recBuildBST(vec, start, mid - 1, current); + if (end - mid > 0) + recBuildBST(vec, mid + 1, end, current); +} + +template +Tree* vecToBST(std::vector& vec) { + Tree* result = nullptr; + recBuildBST(vec, 0, vec.size() - 1, result); + return result; +} + +void ex2() { + std::vector v = { 1, 3, 4, 6, 7, 8, 10, 13, 14 }; + Tree* t = vecToBST(v); + printTree(t); + + freeTree(t); +} + +// Exercise 3 + +template +void insertNodeInBST(Tree*& tree, Tree* node) { + if (tree == nullptr) { + tree = node; + return; + } + + insertNodeInBST((tree->data < node->data) ? tree->right : tree->left, node); +} + +template +void removeInBST(Tree*& tree, const T& elem) { + Tree** current = &tree; + while (*current != nullptr && (*current)->data != elem) { + current = ((*current)->data < elem) ? &((*current)->right) : &((*current)->left); + } + if (current == nullptr) return; + + Tree* oldCurrent = *current; + *current = (*current)->right; + insertNodeInBST(*current, oldCurrent->left); + delete oldCurrent; +} + +void ex3() { + Tree* t = new Tree(8, new Tree(3, new Tree(1), new Tree(6, new Tree(4), new Tree(7))), new Tree(10, nullptr, new Tree(14, new Tree(13)))); + removeInBST(t, 8); + printTree(t); + + freeTree(t); +} + +// Exercise 4 + +template +bool equal(Tree* a, Tree* b) { + if ((a == nullptr) != (b == nullptr)) return false; + else if (a == nullptr) return true; + + return a->data == b->data && equal(a->left, b->left) && equal(a->right, b->right); +} + +void ex4() { + Tree* t1 = new Tree(8, new Tree(3, new Tree(1), new Tree(6, new Tree(4), new Tree(7))), new Tree(10, nullptr, new Tree(14, new Tree(13)))); + Tree* t2 = new Tree(8, new Tree(3, new Tree(1), new Tree(6, new Tree(4), new Tree(7))), new Tree(10, nullptr, new Tree(14, new Tree(13)))); + std::cout << equal(t1, t2) << std::endl; + + freeTree(t1); + freeTree(t2); +} + +// Exercise 5 + +template +void rightRotation(Tree*& tree) { + Tree* root = tree; + Tree* pivot = tree->left; + + tree = pivot; + root->left = pivot->right; + tree->right = root; +} + +template +void leftRotation(Tree*& tree) { + Tree* root = tree; + Tree* pivot = tree->right; + + tree = pivot; + root->right = pivot->left; + tree->left = root; +} + +void ex5() { + Tree* t = new Tree('Q', new Tree('P', new Tree('A'), new Tree('B')), new Tree('C')); + printTree(t); + rightRotation(t); + printTree(t); + leftRotation(t); + leftRotation(t); + printTree(t); + rightRotation(t); + printTree(t); + + freeTree(t); +} + +// Exercise 6 + +template +T pred(Tree* tree, const T& x) { + if (tree->value > x) { + if (tree->left == nullptr) return tree->value; + pred(tree->left, x); + } + else { + if (tree->right == nullptr) return tree->value; + pred(tree->right, x); + } +} + +void ex6() { + +} + +// main + +int main() { + ex5(); +} diff --git a/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/tree-utils.h b/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/tree-utils.h new file mode 100644 index 0000000..c9faf2c --- /dev/null +++ b/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/tree-utils.h @@ -0,0 +1,236 @@ +/* Author : StoychoX + * Source : https://github.com/stoychoX/Data-structures-and-algorithms/raw/main/Seminar08/tree-utils.h + * License : + * Date : 25.12.2022 + */ + +#ifndef TREE_UTIL_IMPL +#define TREE_UTIL_IMPL + +#include +#include +#include +#include + +// Важни неща: +template +struct Tree { + T data; + Tree* left; + Tree* right; + + Tree(T data, Tree* l = nullptr, Tree* r = nullptr) : data{ data }, left{ l }, right{ r } {} +}; + +template +void freeTree(Tree* t) { + if (t == nullptr) + return; + freeTree(t->left); + freeTree(t->right); + delete t; +} + +template +void insertInBST(Tree*& t, const T& elem, bool hasDuplicates = true) { + if (t == nullptr) { + t = new Tree(elem); + return; + } + else if (t->data < elem) { + insertInBST(t->right, elem, hasDuplicates); + } + else if ((t->data > elem) || hasDuplicates) { + insertInBST(t->left, elem, hasDuplicates); + } +} + +template +const Tree* getMinNode(const Tree* t) { + assert(t != nullptr); + + const Tree* iter = t; + + while (iter->left) { + iter = iter->left; + } + return iter; +} + +template +bool removeElement(Tree*& t, const T& elem) { + if (t == nullptr) + return false; + + if (t->data > elem) { + return removeElement(t->left, elem); + } + else if (t->data < elem) { + return removeElement(t->right, elem); + } + + // Намерили сме елемента + if (!t->left && !t->right) { // Листо + delete t; + t = nullptr; // !! + } + else if (!t->left && t->right) { // Има само дясно поддърво + Tree* toDelete = t; + t = t->right; + delete toDelete; + } + else if (t->left && !t->right) { // Има само ляво поддърво + Tree* toDelete = t; + t = t->left; + delete toDelete; + } + else { // Вътрешен връх. + T newData = getMinNode(t->right)->data; + t->data = newData; + removeElement(t->right, newData); + } + return true; +} + +template +bool containsBST(const Tree* t, const T& elem) { + if (t == nullptr) + return false; + + if (t->data == elem) + return true; + + if (t->data < elem) + return containsBST(t->right, elem); + + return containsBST(t->left, elem); +} + + +// За по - любопитните премахване на възел +// само с пренасочване на указатели и без копие на T +template +void innerVertexRemoveCase(Tree*& inVertex) { + assert(inVertex && inVertex->left && inVertex->right); + + Tree** minNode = &inVertex->right; + Tree** minNodeParent = &inVertex; + + bool firstGoingDown = true; + + while ((*minNode)->left) { + minNode = &(*minNode)->left; + + minNodeParent = firstGoingDown ? &(*minNodeParent)->right : &(*minNodeParent)->left; + + firstGoingDown = false; + } + + Tree* originalRight = (*minNode)->right; + + (*minNode)->left = inVertex->left; + + if (!firstGoingDown) + (*minNode)->right = inVertex->right; + + Tree* toDelete = inVertex; + + inVertex = (*minNode); + + if (!firstGoingDown) + (*minNodeParent)->left = originalRight; + + delete toDelete; +} + +template +bool removeElementPointerSwap(Tree*& t, const T& elem) { + if (t == nullptr) + return false; + + if (t->data > elem) { + return removeElementPointerSwap(t->left, elem); + } + else if (t->data < elem) { + return removeElementPointerSwap(t->right, elem); + } + + // Намерили сме елемента + if (!t->left && !t->right) { // Листо + delete t; + t = nullptr; + } + else if (!t->left && t->right) { // Има само дясно поддърво + Tree* toDelete = t; + t = t->right; + delete toDelete; + } + else if (t->left && !t->right) { // Има само ляво поддърво + Tree* toDelete = t; + t = t->left; + delete toDelete; + } + else { // Вътрешен връх. + innerVertexRemoveCase(t); + } + return true; +} + +// Неща за мое удобство, не е нужно да ги четете: + +// Взето от: +// https://stackoverflow.com/questions/36802354/print-binary-tree-in-a-pretty-way-using-c +template +void printBT(const std::string& prefix, const Tree* node, bool isLeft) { + if (node != nullptr) { + std::cout << prefix; + + std::cout << (isLeft ? "|--" : "`--"); + + std::cout << node->data << std::endl; + + printBT(prefix + (isLeft ? "| " : " "), node->left, true); + printBT(prefix + (isLeft ? "| " : " "), node->right, false); + } +} + +template +void printTree(const Tree* node) { + printBT("", node, false); +} + +// Следващите две функции са малко по - красив начин да изпринтим дърво, но го конвертира къмм LaTeX документ +// Когато извикате exportToTex("file.txt") ще ви създаде фейл с код. +// Пейстнете кода в overleaf.com и ще ви излезе дървото. + +// Не е перфектно но пък е по - удобно от конзолата. Това е за демонстрации, не е нужно да го учите или разбирате. +template +void recFillFileStream(std::ofstream& outFile, const Tree* r) { + if (r == nullptr) + return; + + outFile << "[" << r->data << " "; + recFillFileStream(outFile, r->left); + recFillFileStream(outFile, r->right); + + outFile << "]"; +} + +template +void exportToTex(const Tree* root, const char* filePath) { + std::ofstream outFile(filePath, std::ios::trunc); + + outFile << "\\documentclass[tikz,border=10pt]{standalone}" << std::endl; + outFile << "\\usepackage[linguistics]{forest}" << std::endl; + outFile << "\\begin{document}" << std::endl; + outFile << "\\begin{forest}" << std::endl; + + recFillFileStream(outFile, root); + + outFile << "\\end{forest}"; + outFile << "\\end{document}"; + + outFile.close(); +} + +#endif -- cgit v1.3.1-26-gb76a