From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- Seminar08/tree-utils.h | 230 ------------------------------------------------- 1 file changed, 230 deletions(-) delete mode 100644 Seminar08/tree-utils.h (limited to 'Seminar08/tree-utils.h') diff --git a/Seminar08/tree-utils.h b/Seminar08/tree-utils.h deleted file mode 100644 index 3ce0d93..0000000 --- a/Seminar08/tree-utils.h +++ /dev/null @@ -1,230 +0,0 @@ -#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 \ No newline at end of file -- cgit v1.3.1-26-gb76a