Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar08
diff options
context:
space:
mode:
Commit7eee5a78005a9a569186d2c8b4b645a818ab9bf1 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-06 07:04:44 -0400
Files84594e0af29cefa5aae76ace5f8eb81484400e31 /Seminar08
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.tar.gz
Data-structures-and-algorithms-7eee5a78005a9a569186d2c8b4b645a818ab9bf1.zip
Parent0841635826cb03c0e74cd75ec3c97c4c3b594d8b (diff)
Cleanup
11 files changed, 0 insertions, 560 deletions
-rw-r--r--Seminar08/README.md193
-rw-r--r--Seminar08/height.cpp14
-rw-r--r--Seminar08/inorder-traversal.cpp23
-rw-r--r--Seminar08/insert-in-bst.cpp36
-rw-r--r--Seminar08/media/left-child-right-sibling.pngbin22100 -> 0 bytes
-rw-r--r--Seminar08/media/stick.pngbin13709 -> 0 bytes
-rw-r--r--Seminar08/media/subtree.pngbin32004 -> 0 bytes
-rw-r--r--Seminar08/media/tree-first-example.pngbin16135 -> 0 bytes
-rw-r--r--Seminar08/media/tree-second-example.pngbin20847 -> 0 bytes
-rw-r--r--Seminar08/min-max-elem.cpp64
-rw-r--r--Seminar08/tree-utils.h230
diff --git a/Seminar08/README.md b/Seminar08/README.md
deleted file mode 100644
index a61b2bd..0000000
--- a/Seminar08/README.md
+++ /dev/null
@@ -1,193 +0,0 @@
-# Дървета - част 1
-Свързан граф, който не съдържа цикли наричаме дърво. Дървета се използват от далечната 1875 година когато английски математик на име Arthur Cayley ги използва за да брои видове химични съединения.
-
-## Примери за дървета
-Вероятно всеки вече в един или друг момент се е сблъсквал с дървета. Това е дърво:
-
-![](media/tree-first-example.png)
-
-Това също е дърво:
-
-![](media/tree-second-example.png)
-
-Дърветата са практически използваеми в компютърните науки, много алгоритми и системи ги използват за множество различни цели.
-
-## Малко дефиниции
-| Понятие | Дефиниция
-| :--- | :----:
-| Дърво | Свързан ацикличен граф.
-| Кореново дърво | Дърво, в което точно един връх е избран за корен. Най - често в курса когато пишем дърво разбираме кореново дърво.
-| Листо | Връх без наследници.
-| Вътрешен връх | Връх, който не е листо или корен.
-| Разклоненост | Максималния брой деца на кой да е връх.
-| Височина на връх *u* | Максималното разстояние между *u* и кое да е листо.
-| Дълбочина на връх *u* | Разстоянието между корена и *u*.
-| Височина на дърво | Височината на корена.
-| Ниво *k* | Множеството от всички върхове с дълбочина *к*.
-| Предшественик на връх *u* | За връх *v* казваме, че е предшественик на *u* ако *v* се съдържа в пътя между корена и *u*.
-| Наследник на връх *u* | За връх *v* казваме, че е наследник на *u* ако *u* е предшественик на *v*.
-
-В дефиницията ва предшественик, казваме "пътя между корена и *u*". Важно свойство на дърветата е, че между всеки два върха има **точно един път**. Това свойство е необходимо и достатъчно условие граф да е дърво, ако в един граф имаме точно един път между всеки два върха то той е дърво. Какво би се объркало ако съществуват два върха без път между тях? Какво би станало ако имаме два пътя между два върха?
-
-## Височина на дърво
-С височини на дървета ще се занимаваме много. Неформално, доста често е полезно да държим дървото ниско, това в някакъв смисъл минимизира възможните "слизания надолу".
-
-Колко е максималната височина на дърво с *n* върха? Най - много тя може да стане *n*. Това се случва когато дървото е изродено.
-Пример за изродено дърво с 4 върха:
-
-![](media/stick.png)
-
-Има ли долна граница за височината на дърво? Ако нищо не знаем за дървото, то височината му най - малко може да е 1. Това се случва когато всички възли, различни от корена, са негови наследници (т.е. когато нямаме вътрешни върхове).
-Доста често обаче, когато работим с дървета, знаем тяхната разклоненост.
-Нека имаме дърво с *n* върха и разклоненост *k*. Тогава то не може да стане по - ниско от $\lfloor \log_k n \rfloor$.
-
-Опитайте се да начертаете дърво с разклоненост 2 и 8 върха. Възможно ли е височината му да е по - малка от 3?
-
-## Поддървета
-Неформално, поддърво вкоренено във връх *u* е върхът *u* и всичко под него. Формалната дефиниция ще оставим за друг курс, но това е пример за поддърво, вкоренено във връх 2:
-
-![](media/subtree.png)
-
-## Двоични дървета.
-Двоичното дърво е дърво с максимална разклоненост 2. Това означава, че всеки възел има най - много две деца. В общия случай различаваме децата като ляво и дясно дете (или ляв и десен наследник).
-За двоичните дървета можем също да си мислим като рекурсивно дефинирана структура от данни:
-* Празното дърво е двоично дърво
-* Дърво с един връх и без ребра е двоично дърво
-* Възел с ляв наследник двоично дърво и десен наследник двоично дърво е двоично дърво.
-
-Голяма част от алгоритмите върху двоичните дървета са рекурсивни точно поради този удобен начин да дефинираме двоично дърво.
-
-Дървото в пример 1 е двоично дърво. Дървото в пример 2 не е двоично дърво, понеже има възел от степен 4.
-
-Двоичните дървета поддържат операции по добавяне на елемент и премахване на елемент. Проблемът е, че нищо не знаем за елементите. Нищо не знаем за височината. Единственото което знаем е, че това е дърво с разклоненост 2.
-
-## Двоични наредени дървета
-Двоичното наредено дърво е двоично дърво за което е вярно следното **свойство:**
-
-- Нека *u* е възел в двоично наредено дърво. Стойността на всеки възел от лявото поддърво на *u* е по - малка от стойността на *u*. Стойността на всеки възел от дясното поддърво на *u* е по - голяма от стойността на *u*.
-
-Можем да имаме повтарящи се елементи, това не е проблем. Можем да ги слагаме само отляво или само отдясно, важното е да се поддържа една конвенция.
-
-Едно важно нещо, без което не можем да имаме двоично наредено дърво, е свойството на стойностите на възлите да са сравними. не можем да строим двоично наредено дърво от несравними стойности. Двоичните наредени дървета са сравнително лесни за разбиране и ползване и притежават интересни свойства, с който ще се занимаваме тепърва!
-
-## Представяне на дървета
-
-### Свързано представяне - Двоични дървета
-Свързаното представяне е ужасно удобно когато поддържаме операции като добавяне или изтриване. То ще се ползва най - често в курса, представяме двоично дърво като:
-
-```cpp
-template<class T>
-struct Tree {
- T data;
- Tree* left;
- Tree* right;
-
- Tree(T data, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data {data}, left {l}, right {r} {}
-}
-```
-
-От тук всеки указател от типа *Tree\<T>\** е валидно дърво. Ако то е празно стойността му би била nullptr. Ако е непразно, данните записани във възела му достъпваме чрез data полето, а лявото и дясното поддърво достъпваме съответно чрез left и right.
-
-Дървото от пример 1, представено по този начин, би изглеждало така:
-
-```cpp
-Tree<int>* createExampleOne() {
- return new Tree<int>(
- 0, // Корена
- new Tree<int>(1), // Лявото поддърво
- new Tree<int>( // Дясното поддърво
- 2,
- new Tree<int>(3, new Tree<int>(5), new Tree<int>(6)),
- new Tree<int>(4, nullptr, new Tree<int>(7))
- )
- );
-}
-```
-
-Или пък примерно, как можем да проверим дали възел е листо? Спомняме си дефиницията на листо и пишем:
-```cpp
-template<class T>
-bool isLeaf(const Tree<T>* t) {
- return t != nullptr && t->left == nullptr && t->right == nullptr;
-}
-```
-
-### Списък на бащите
-Очевидно, чрез свързаното представяне в някакъв смисъл слизаме от корена към листата. Какво правим обаче ако искаме да се качваме от листата към корена?
-
-Нека имаме дърво с *n* върха. Върховете са номерирани с числа от 0 до *n-1*. Едно валидно номериране можем да видим в пример едно. Корена е 0 левия наследник 1, десния 2 и така, по нива, от ляво надясно им даваме индекси от 0 до *n* - 1. Разбира се, това номериране не е единствено, но някак е най - удобно.
-
-Разглеждаме масив tArray с *n* елемента за който е вярно: **В tArray[i] е записан номера на бащата на връх с номер i. Ако върхът с номер i е корен (а корена няма баща) просто пишем -1**.
-Дървото от пример 1 може да се представи чрез списък на бащите по следния начин:
-
-* [-1, 0, 0, 2, 2, 3, 3, 4]
-
-Едно от предимствата на това представяне е, че можем да представим дърво с произволна разклоненост. Все пак няма значение разклонеността, ако можем да номерираме възлите с числа от 0 до *n-1* можем да го представим по този начин.
-
-Но с какво ни помага това? Тук движението става от листата към корена. Вярно е, че за всеки връх, за константно време знаейки номера му, мога да намеря баща му. Е баща му също е възел, тоест мога да намеря и неговия баща.
-
-Така движението в някакъв смисъл не става (корен -> листа) а става (връх -> корен). Това представяне се използва в задачи за намиране на предшественици (и не само).
-
-Недостатъците на това представяне са, че добавянето, проверката дали възел е листо, премахването и други операции върху дървета стават сложни.
-
-Представянето на дървета с масиви е използвано в някои алгоритми и може много скоро нещо подобно да се появи.
-
-### Ляв син десен брат
-Представянето чрез масив на бащите ни позволи да представим дърво с произволна разклоненост. Има поне още два начина да се представи такова дърво. За всеки възел пазим указател към най - левия му син и най - десния му брат:
-
-```cpp
-template<class T>
-struct Tree{
- T data;
- Tree<T>* leftChild;
- Tree<T>* rightSibling;
-};
-```
-
-Така от корена можем да достъпим кой да е връх на произволно разклоненото дърво.
-![](media/left-child-right-sibling.png)
-
-Тук в leftChild указателя на 2 ще е записан адреса на 4. В rightSibling указателя на 2 ще е записан 3. Ако някой възел няма ляво дете или десен брат, то указателя просто е nullptr.
-Предимството е, че за същата памет, с която представихме двоично дърво, можем да представим дърво с произволна разклоненост. Недостатъка е, че имаме последователен достъп до децата. Тоест ако искам да взема третото дете на връх *u* първо ще трябва да сляза до най - лявото му дете и да се предвижа две позиции надясно. Ако често имаме нужда да четем дете на позиция k това може би не би било най - подходящото представяне.
-
-### Чрез вектор от децата
-Тук идеята е супер интуитивна:
-```cpp
-template<class T>
-struct Tree {
- T data;
- std::vector<Tree<T>*> children;
-};
-```
-Ако искаме да вземем третото дете на връх *u* просто правим u->children[2]. Предимството е очевидно - нямаме последователен достъп до децата. Недостатъкът е, че възлите започват да заемат повече памет. Размера на вектора (в x64) е 32 байта. Ако възлите ни са от тип int то размера на структурата би бил 40 байта.
-Вектора ще направи алокации, което също в някакъв смисъл забавя програмата. Но пък веднъж като построим дървото имаме бърз достъп до децата.
-
-### Чрез допълнителен parent указател
-Представянето чрез масив на бащите беше хубаво, но проблемът е, че трудно добавяме и изваждаме елемент от колекцията. Ако искаме да имаме дърво което поддържа добавяне и изтриване и също така може да намира родителя си, то просто добавяме още един указател.
-```cpp
-template<class T>
-struct Tree {
- T data;
- Tree* parent;
- Tree* left;
- Tree* right;
-
- Tree(T data, Tree<T>* p = nullptr, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data {data}, parent {p}, left {l}, right {r} {}
-}
-```
-Тук проблемът е, че отново плащаме цената от 4 (или 8) байта за допълнителен указател. Но пък ако ни трябва добавяне, премахване и движение както от корен към листа така и листа корен плащаме малко памет и имаме всичко това!
-
-## Задача първа
-Да се реализира функция, която добавя елемент в двоично наредено дърво.
-
-## Задача втора
-Да се напише функция *contains(Tree\<T>\* tree, const T& elem)* която връща дали елемента се съдържа в двоично дърво. Да се реализира същата функция за двоично наредено дърво.
-
-## Задача трета
-Да се напише функция *max((Tree\<T>\* tree)* която връща най - големия елемент в двоично дърво. Да се реализира същата функция за двоично наредено дърво. Да се реализира функция намираща най - малкия елемент.
-
-## Задача четвърта
-Да се реализира функция, която връща височината на двоично дърво.
-
-## Задача пета
-Да се напише функция, която обхожда елементите на двоично дърво по схемата ляво-корен-дясно. (още позната като inorder traversal). Извикайте функцията върху двоично наредено дърво. Какво забелязвате?
diff --git a/Seminar08/height.cpp b/Seminar08/height.cpp
deleted file mode 100644
index c115228..0000000
--- a/Seminar08/height.cpp
+++ /dev/null
@@ -1,14 +0,0 @@
-#include"tree-utils.h"
-#include<iostream>
-
-template<typename T>
-size_t height(const Tree<T>* tree) {
- if (!tree)
- return 0;
-
- return 1 + std::max(height(tree->left), height(tree->right));
-}
-
-int main(){
-
-}
diff --git a/Seminar08/inorder-traversal.cpp b/Seminar08/inorder-traversal.cpp
deleted file mode 100644
index c9a9bd6..0000000
--- a/Seminar08/inorder-traversal.cpp
+++ /dev/null
@@ -1,23 +0,0 @@
-#include "tree-utils.h"
-
-template <typename T>
-void inorderTraversal(const Tree<T> *tree) {
- if (tree == nullptr) {
- return;
- }
-
- inorderTraversal(tree->left);
- std::cout << tree->data << ' ';
- inorderTraversal(tree->right);
-}
-
-int main() {
- Tree<int> *root = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
-
- inorderTraversal(root); //изпечатва елементите на дървото сортирано
- std::cout << '\n';
- printTree(root);
-
- freeTree(root);
- return 0;
-} \ No newline at end of file
diff --git a/Seminar08/insert-in-bst.cpp b/Seminar08/insert-in-bst.cpp
deleted file mode 100644
index ac4c9f4..0000000
--- a/Seminar08/insert-in-bst.cpp
+++ /dev/null
@@ -1,36 +0,0 @@
-#include<iostream>
-#include"tree-utils.h"
-
-// Тук допускаме да има повторения. Ако искаме да няма повторения втория else ще стане else if(t->data > elem)
-template<class T>
-void insertInBST(Tree<T>*& t, const T& elem) {
- if(t == nullptr) {
- t = new Tree<T>(elem);
- return;
- }
- else if(t->data < elem) {
- insertInBST(t->right, elem);
- }
- else {
- insertInBST(t->left, elem);
- }
-}
-
-int main() {
- Tree<int>* example = new Tree<int>(4, new Tree<int>(2), new Tree<int>(6));
-
- insertInBST(example, 1);
- printTree(example);
-
- // За любопитните: колко ли ще е височината на дърво от 50 случайни числа?
- Tree<int>* secondExample = nullptr;
- srand(time(NULL));
- for (int i = 0; i < 50; i++)
- insertInBST<int>(secondExample, rand() % 100);
-
- exportToTex(secondExample, "file.txt");
- //-------------------------------------------------
-
- freeTree(example);
- freeTree(secondExample);
-} \ No newline at end of file
diff --git a/Seminar08/media/left-child-right-sibling.png b/Seminar08/media/left-child-right-sibling.png
deleted file mode 100644
index 180f782..0000000
--- a/Seminar08/media/left-child-right-sibling.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/media/stick.png b/Seminar08/media/stick.png
deleted file mode 100644
index 9fcc5ad..0000000
--- a/Seminar08/media/stick.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/media/subtree.png b/Seminar08/media/subtree.png
deleted file mode 100644
index 5875be2..0000000
--- a/Seminar08/media/subtree.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/media/tree-first-example.png b/Seminar08/media/tree-first-example.png
deleted file mode 100644
index 4fe94bf..0000000
--- a/Seminar08/media/tree-first-example.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/media/tree-second-example.png b/Seminar08/media/tree-second-example.png
deleted file mode 100644
index bf57c99..0000000
--- a/Seminar08/media/tree-second-example.png
+++ /dev/null
Binary files differ
diff --git a/Seminar08/min-max-elem.cpp b/Seminar08/min-max-elem.cpp
deleted file mode 100644
index cbd8560..0000000
--- a/Seminar08/min-max-elem.cpp
+++ /dev/null
@@ -1,64 +0,0 @@
-#include "tree-utils.h"
-#include <cmath>
-
-// for regular binary trees
-template <typename T>
-T max_elem(Tree<T> *tree) {
- T res = tree->data;
-
- if (tree->left != nullptr) {
- res = std::max(res, max_elem(tree->left));
- }
- if (tree->right != nullptr) {
- res = std::max(res, max_elem(tree->right));
- }
-
- return res;
-}
-
-template <typename T>
-T min_elem(Tree<T> *tree) {
- T res = tree->data;
-
- if (tree->left != nullptr) {
- res = std::min(res, min_elem(tree->left));
- }
- if (tree->right != nullptr) {
- res = std::min(res, min_elem(tree->right));
- }
-
- return res;
-}
-
-// for binary search trees
-template <typename T>
-T max_elem_bst(Tree<T> *tree) {
- while (tree->right != nullptr)
- tree = tree->right;
-
- return tree->data;
-}
-
-template <typename T>
-T min_elem_bst(Tree<T> *tree) {
- while (tree->left != nullptr)
- tree = tree->left;
-
- return tree->data;
-}
-
-int main() {
- Tree<int> *regularTree = new Tree<int>(2, new Tree<int>(3, new Tree<int>(4), new Tree<int>(5)), new Tree<int>(13, new Tree<int>(7), new Tree<int>(8)));
- printTree(regularTree);
- std::cout << "Maximum element in regular binary tree: " << max_elem(regularTree) << '\n';
- std::cout << "Minimum element in regular binary tree: " << min_elem(regularTree) << '\n';
-
- Tree<int> *binarySearchTree = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, new Tree<int>(4), new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
- printTree(binarySearchTree);
- std::cout << "Maximum element in bs tree: " << max_elem_bst(binarySearchTree) << '\n';
- std::cout << "Minimum element in bs tree: " << min_elem_bst(binarySearchTree) << '\n';
-
- freeTree(regularTree);
- freeTree(binarySearchTree);
- return 0;
-} \ No newline at end of file
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<iostream>
-#include<string>
-#include<fstream>
-#include<assert.h>
-
-// Важни неща:
-template<class T>
-struct Tree {
- T data;
- Tree* left;
- Tree* right;
-
- Tree(T data, Tree<T>* l = nullptr, Tree<T>* r = nullptr) : data{ data }, left{ l }, right{ r } {}
-};
-
-template<class T>
-void freeTree(Tree<T>* t) {
- if (t == nullptr)
- return;
- freeTree(t->left);
- freeTree(t->right);
- delete t;
-}
-
-template<class T>
-void insertInBST(Tree<T>*& t, const T& elem, bool hasDuplicates = true) {
- if (t == nullptr) {
- t = new Tree<T>(elem);
- return;
- }
- else if (t->data < elem) {
- insertInBST(t->right, elem, hasDuplicates);
- }
- else if ((t->data > elem) || hasDuplicates) {
- insertInBST(t->left, elem, hasDuplicates);
- }
-}
-
-template<class T>
-const Tree<T>* getMinNode(const Tree<T>* t) {
- assert(t != nullptr);
-
- const Tree<T>* iter = t;
-
- while (iter->left) {
- iter = iter->left;
- }
- return iter;
-}
-
-template<class T>
-bool removeElement(Tree<T>*& 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<T>* toDelete = t;
- t = t->right;
- delete toDelete;
- }
- else if (t->left && !t->right) { // Има само ляво поддърво
- Tree<T>* toDelete = t;
- t = t->left;
- delete toDelete;
- }
- else { // Вътрешен връх.
- T newData = getMinNode(t->right)->data;
- t->data = newData;
- removeElement(t->right, newData);
- }
- return true;
-}
-
-template<class T>
-bool containsBST(const Tree<T>* 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<class T>
-void innerVertexRemoveCase(Tree<T>*& inVertex) {
- assert(inVertex && inVertex->left && inVertex->right);
-
- Tree<T>** minNode = &inVertex->right;
- Tree<T>** minNodeParent = &inVertex;
-
- bool firstGoingDown = true;
-
- while ((*minNode)->left) {
- minNode = &(*minNode)->left;
-
- minNodeParent = firstGoingDown ? &(*minNodeParent)->right : &(*minNodeParent)->left;
-
- firstGoingDown = false;
- }
-
- Tree<T>* originalRight = (*minNode)->right;
-
- (*minNode)->left = inVertex->left;
-
- if (!firstGoingDown)
- (*minNode)->right = inVertex->right;
-
- Tree<T>* toDelete = inVertex;
-
- inVertex = (*minNode);
-
- if (!firstGoingDown)
- (*minNodeParent)->left = originalRight;
-
- delete toDelete;
-}
-
-template<class T>
-bool removeElementPointerSwap(Tree<T>*& 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<T>* toDelete = t;
- t = t->right;
- delete toDelete;
- }
- else if (t->left && !t->right) { // Има само ляво поддърво
- Tree<T>* 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<class T>
-void printBT(const std::string& prefix, const Tree<T>* 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<class T>
-void printTree(const Tree<T>* node) {
- printBT("", node, false);
-}
-
-// Следващите две функции са малко по - красив начин да изпринтим дърво, но го конвертира къмм LaTeX документ
-// Когато извикате exportToTex("file.txt") ще ви създаде фейл с код.
-// Пейстнете кода в overleaf.com и ще ви излезе дървото.
-
-// Не е перфектно но пък е по - удобно от конзолата. Това е за демонстрации, не е нужно да го учите или разбирате.
-template<class T>
-void recFillFileStream(std::ofstream& outFile, const Tree<T>* r) {
- if (r == nullptr)
- return;
-
- outFile << "[" << r->data << " ";
- recFillFileStream(outFile, r->left);
- recFillFileStream(outFile, r->right);
-
- outFile << "]";
-}
-
-template<class T>
-void exportToTex(const Tree<T>* 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