Merge branch 'main' of https://github.com/stoychoX/Data-structures-and-algorithms

8 files changed, 251 insertions, 0 deletions

diff --git a/Practicum/pract07/ExampleFunctions.cpp b/Practicum/pract07/ExampleFunctions.cpp
new file mode 100644
index 0000000..9e81f98
--- /dev/null
+++ b/Practicum/pract07/ExampleFunctions.cpp
@@ -0,0 +1,85 @@
+#include <iostream>
+#include <queue>
+#include <algorithm>
+
+template <typename T>
+struct TreeNode {
+    T data;
+    TreeNode* left;
+    TreeNode* right;
+
+    TreeNode(const T& val) : data(val), left(nullptr), right(nullptr) {}
+};
+
+// Проверка дали даден възел е листо
+// Листо е възел, който няма деца
+template <typename T>
+bool isLeaf(TreeNode<T>* node) {
+    return node && !node->left && !node->right;
+}
+
+// Проверка дали даден елемент се съдържа в дърво
+template <typename T>
+bool contains(TreeNode<T>* root, T value) {
+    if (root == nullptr) return false;
+
+    if (root->data == value) return true;
+
+    return contains(root->left, value) || contains(root->right, value);
+}
+
+// Намиране на височина на дърво
+// Височината на дърво е дължината на най-дългия път от корена до някое листо
+template <typename T>
+int getHeight(TreeNode<T>* root) {
+    if (!root) return -1;
+
+    int leftHeight = getHeight(root->left);
+    int rightHeight = getHeight(root->right);
+
+    return 1 + std::max(leftHeight, rightHeight);
+}
+
+// Преброяване на възлите в дърво
+template <typename T>
+int countNodes(TreeNode<T>* root) {
+    if (!root) return 0;
+
+    if (!root->left && !root->right) return 1;
+
+    return 1 + countNodes(root->left) + countNodes(root->right);
+}
+
+int main() {
+    // Създаване на двоично дърво от цели числа
+    TreeNode<int>* root = new TreeNode<int>(1);
+    root->left = new TreeNode<int>(2);
+    root->right = new TreeNode<int>(3);
+    root->left->left = new TreeNode<int>(4);
+    root->left->right = new TreeNode<int>(5);
+    root->right->left = new TreeNode<int>(6);
+    root->right->right = new TreeNode<int>(7);
+
+    // Как изглежда дървото:
+    //       1
+    //      / \
+    //     2   3
+    //    / \ / \
+    //   4  5 6  7
+
+    // Проверка дали даден възел е листо
+    std::cout << "Is 4 a leaf: " << std::boolalpha << isLeaf(root->left->left) << std::endl; // true
+    std::cout << "Is 3 a leaf: " << std::boolalpha << isLeaf(root->right) << std::endl; // false
+
+    // Проверка дали даден елемент се съдържа в дървото
+    std::cout << "Does the tree contain 5: " << std::boolalpha << contains(root, 5) << std::endl; // true
+    std::cout << "Does the tree contain 8: " << std::boolalpha << contains(root, 8) << std::endl; // false
+
+    // Намиране на височината на дървото
+    std::cout << "Height of the tree: " << getHeight(root) << std::endl; // 2
+
+    // Преброяване на възлите в дървото
+    std::cout << "Total nodes in the tree: " << countNodes(root) << std::endl; // 7
+
+    return 0;
+}
diff --git a/Practicum/pract07/Traversals.cpp b/Practicum/pract07/Traversals.cpp
new file mode 100644
index 0000000..61f8bb1
--- /dev/null
+++ b/Practicum/pract07/Traversals.cpp
@@ -0,0 +1,98 @@
+#include <iostream>
+#include <queue>
+#include <algorithm>
+
+template <typename T>
+struct TreeNode {
+    T data;
+    TreeNode* left;
+    TreeNode* right;
+
+    TreeNode(const T& val) : data(val), left(nullptr), right(nullptr) {}
+};
+
+// Preorder обхождане (корен, ляво, дясно)
+template <typename T>
+void preorderTraversal(TreeNode<T>* root) {
+    if (!root) return;
+    std::cout << root->data << " ";
+    preorderTraversal(root->left);
+    preorderTraversal(root->right);
+}
+
+// Inorder обхождане (ляво, корен, дясно)
+template <typename T>
+void inorderTraversal(TreeNode<T>* root) {
+    if (!root) return;
+    inorderTraversal(root->left);
+    std::cout << root->data << " ";
+    inorderTraversal(root->right);
+}
+
+// Postorder обхождане (ляво, дясно, корен)
+template <typename T>
+void postorderTraversal(TreeNode<T>* root) {
+    if (!root) return;
+    postorderTraversal(root->left);
+    postorderTraversal(root->right);
+    std::cout << root->data << " ";
+}
+
+// Обхождане в широчина
+template <typename T>
+void bfs(TreeNode<T>* root) {
+    if (!root) return;
+
+    std::queue<TreeNode<T>*> q;
+    q.push(root);
+
+    while (!q.empty()) {
+        TreeNode<T>* current = q.front();
+        q.pop();
+
+        std::cout << current->data << " ";
+
+        if (current->left) q.push(current->left);
+        if (current->right) q.push(current->right);
+    }
+}
+
+int main() {
+    // Създаване на двоично дърво от цели числа
+    TreeNode<int>* root = new TreeNode<int>(1);
+    root->left = new TreeNode<int>(2);
+    root->right = new TreeNode<int>(3);
+    root->left->left = new TreeNode<int>(4);
+    root->left->right = new TreeNode<int>(5);
+    root->right->left = new TreeNode<int>(6);
+    root->right->right = new TreeNode<int>(7);
+
+    // Как изглежда дървото:
+    //       1
+    //      / \
+    //     2   3
+    //    / \ / \
+    //   4  5 6  7
+
+    // Preorder обхождане
+    std::cout << "Preorder traversal: ";
+    preorderTraversal(root); // 1 2 4 5 3 6 7
+    std::cout << std::endl;
+
+    // Inorder обхождане
+    std::cout << "Inorder traversal: ";
+    inorderTraversal(root); // 4 2 5 1 6 3 7
+    std::cout << std::endl;
+
+    // Postorder обхождане
+    std::cout << "Postorder traversal: ";
+    postorderTraversal(root); // 4 5 2 6 7 3 1
+    std::cout << std::endl;
+
+    // Обхождане в широчина
+    std::cout << "BFS traversal: ";
+    bfs(root); // 1 2 3 4 5 6 7
+    std::cout << std::endl;
+
+    return 0;
+}
diff --git a/Practicum/pract07/binaryTree.png b/Practicum/pract07/binaryTree.png
new file mode 100644
index 0000000..01a9e2a
--- /dev/null
+++ b/Practicum/pract07/binaryTree.png
diff --git a/Practicum/pract07/inorder.gif b/Practicum/pract07/inorder.gif
new file mode 100644
index 0000000..d807a10
--- /dev/null
+++ b/Practicum/pract07/inorder.gif
diff --git a/Practicum/pract07/postorder.gif b/Practicum/pract07/postorder.gif
new file mode 100644
index 0000000..023f302
--- /dev/null
+++ b/Practicum/pract07/postorder.gif
diff --git a/Practicum/pract07/preorder.gif b/Practicum/pract07/preorder.gif
new file mode 100644
index 0000000..17ae1b0
--- /dev/null
+++ b/Practicum/pract07/preorder.gif
diff --git a/Practicum/pract07/readme.md b/Practicum/pract07/readme.md
new file mode 100644
index 0000000..d23f234
--- /dev/null
+++ b/Practicum/pract07/readme.md
@@ -0,0 +1,68 @@
+# Практикум №7 по Структури от данни, спец. ИС
+
+## Какво е дърво?
+
+***Дървото*** е йерархична структура от данни, съставена от **върхове** и **ръбове**. То започва с един основен връх, наречен **корен** (root), от който се разклоняват други върхове (наричани **деца**), образувайки по-малки поддървета.
+
+### Основни термини и характеристики:
+- **корен** (root): началният връх на дървото, който няма родител
+- **връх** (node): всеки елемент в дървото
+- **деца**: върховете, които са непосредствено свързани към даден връх
+- **родител**: връх, който има деца
+- **листо** (leaf): връх, който няма деца
+- **вътрешен връх**: връх, който има поне едно дете и не е листо
+- **поддърво**: множеството от върхове, което включва даден връх и всичките му наследници
+- **височина на връх**: максималното разстояние от този връх до някое листо в неговото поддърво
+- **дълбочина на връх**: разстоянието от този връх до корена на дървото
+- **разклоненост**: максималният брой деца, които има който и да е връх в дървото
+
+> **Note:** Нека `T` е дърво с корен `r`, и `v` е връх в `T`:
+> - **Поддървото, вкоренено** във `v`, включва `v` и всички негови наследници <br>
+> - **Височината** на `v` е максималното разстояние от `v` до някое листо в поддървото му <br>
+> - **Дълбочината** на v е разстоянието от `v` до корена `r` на `T`
+
+![binaryTree.png](binaryTree.png)
+
+## Основни алгоритми за обхождане на двоично дърво  
+**Обхождането** на дърво е процесът на посещаване на всеки връх в определен ред.
+Съществуват два основни начина за обхождане на дървета:
+
+### 1. Обхождане в дълбочина (DFS)
+При **DFS** преминаваме на максимална дълбочина в поддървото, преди да се върнем към съседни възли на по-горно ниво.
+
+**Сложност:** O(n), където n е броя на върховете в дървото.
+
+Съществуват три основни типа обхождане в дълбочина:
+
+#### 1.1 Префиксно обхождане (Preorder)
+При префиксното обхождане винаги посещаваме текущия връх преди неговите деца. Коренът на дървото е първият връх, който се посещава. Започваме, като следваме пътя наляво, посещавайки всеки връх по реда на срещането му. Когато достигнем листо, се връщаме назад и продължаваме с дясната част на дървото, като отново посещаваме върховете в реда на срещането им.
+
+Първо се обработва коренът, след това лявото поддърво и накрая дясното поддърво. <br>
+**_Корен → Ляво поддърво → Дясно поддърво_** <br>
+
+
+![preorder.gif](preorder.gif)
+
+#### 1.2 Инфиксно обхождане (Inorder)
+Първо се обработва лявото поддърво, след това коренът и накрая дясното поддърво. <br>
+**_Ляво поддърво → Корен → Дясно поддърво_**
+
+> **Забележка:** При двоичните дървета за търсене (**BST**) този тип обхождане извежда елементите в сортиран ред.
+
+![inorder.gif](inorder.gif)
+
+#### 1.3 Постфиксно обхождане (Postorder)
+При постфиксното обхождане първо посещаваме децата на възела, преди да посетим самия него. Първо се обработва лявото поддърво, след това дясното поддърво и накрая коренът. <br>
+**_Ляво поддърво → Дясно поддърво → Корен_**
+
+![postorder.gif](postorder.gif)
+
+### 2. Обхождане в ширoчина (BFS)
+При **BFS** се преминава през възлите ниво по ниво, започвайки от корена и преминавайки към всяко следващо ниво. Изследват се всички възли на дадено ниво, преди да се премине към следващото ниво. Най-често се използва **опашка** (queue), за да се следи реда на върховете, които трябва да се посетят. Започваме от корена, добавяме го в опашката и след това последователно добавяме неговите деца, докато обработваме всеки връх.
+
+**Сложност:** O(n), където n е броя на върховете в дървото.
+
+![tree-dfs-vs-bfs.gif](tree-dfs-vs-bfs.gif)
+
+## Задачи
+[Линк към задачите](https://leetcode.com/problem-list/aw76m7ld/)
diff --git a/Practicum/pract07/tree-dfs-vs-bfs.gif b/Practicum/pract07/tree-dfs-vs-bfs.gif
new file mode 100644
index 0000000..4fdbc4a
--- /dev/null
+++ b/Practicum/pract07/tree-dfs-vs-bfs.gif