From f03828c4005104130f5e6e5680d0a54843316fef Mon Sep 17 00:00:00 2001 From: Desislava Shunina <115353472+desiish@users.noreply.github.com> Date: Tue, 19 Nov 2024 17:39:09 +0200 Subject: add pract07 readme --- Practicum/pract07/readme.md | 68 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+) create mode 100644 Practicum/pract07/readme.md (limited to 'Practicum/pract07') 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` и всички негови наследници
+> - **Височината** на `v` е максималното разстояние от `v` до някое листо в поддървото му
+> - **Дълбочината** на v е разстоянието от `v` до корена `r` на `T` + +![binaryTree.png](binaryTree.png) + +## Основни алгоритми за обхождане на двоично дърво +**Обхождането** на дърво е процесът на посещаване на всеки връх в определен ред. +Съществуват два основни начина за обхождане на дървета: + +### 1. Обхождане в дълбочина (DFS) +При **DFS** преминаваме на максимална дълбочина в поддървото, преди да се върнем към съседни възли на по-горно ниво. + +**Сложност:** O(n), където n е броя на върховете в дървото. + +Съществуват три основни типа обхождане в дълбочина: + +#### 1.1 Префиксно обхождане (Preorder) +При префиксното обхождане винаги посещаваме текущия връх преди неговите деца. Коренът на дървото е първият връх, който се посещава. Започваме, като следваме пътя наляво, посещавайки всеки връх по реда на срещането му. Когато достигнем листо, се връщаме назад и продължаваме с дясната част на дървото, като отново посещаваме върховете в реда на срещането им. + +Първо се обработва коренът, след това лявото поддърво и накрая дясното поддърво.
+**_Корен → Ляво поддърво → Дясно поддърво_**
+ + +![preorder.gif](preorder.gif) + +#### 1.2 Инфиксно обхождане (Inorder) +Първо се обработва лявото поддърво, след това коренът и накрая дясното поддърво.
+**_Ляво поддърво → Корен → Дясно поддърво_** + +> **Забележка:** При двоичните дървета за търсене (**BST**) този тип обхождане извежда елементите в сортиран ред. + +![inorder.gif](inorder.gif) + +#### 1.3 Постфиксно обхождане (Postorder) +При постфиксното обхождане първо посещаваме децата на възела, преди да посетим самия него. Първо се обработва лявото поддърво, след това дясното поддърво и накрая коренът.
+**_Ляво поддърво → Дясно поддърво → Корен_** + +![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/) -- cgit v1.3.1-23-gd82d From c516610609be1e62628badbe4fc25f5775275be2 Mon Sep 17 00:00:00 2001 From: Desislava Shunina <115353472+desiish@users.noreply.github.com> Date: Tue, 19 Nov 2024 17:40:15 +0200 Subject: add gifs and example function --- Practicum/pract07/ExampleFunctions.cpp | 85 ++++++++++++++++++++++++++++ Practicum/pract07/Traversals.cpp | 98 +++++++++++++++++++++++++++++++++ Practicum/pract07/binaryTree.png | Bin 0 -> 22798 bytes Practicum/pract07/inorder.gif | Bin 0 -> 186492 bytes Practicum/pract07/postorder.gif | Bin 0 -> 176498 bytes Practicum/pract07/preorder.gif | Bin 0 -> 157163 bytes Practicum/pract07/tree-dfs-vs-bfs.gif | Bin 0 -> 90580 bytes 7 files changed, 183 insertions(+) create mode 100644 Practicum/pract07/ExampleFunctions.cpp create mode 100644 Practicum/pract07/Traversals.cpp create mode 100644 Practicum/pract07/binaryTree.png create mode 100644 Practicum/pract07/inorder.gif create mode 100644 Practicum/pract07/postorder.gif create mode 100644 Practicum/pract07/preorder.gif create mode 100644 Practicum/pract07/tree-dfs-vs-bfs.gif (limited to 'Practicum/pract07') 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 +#include +#include + +template +struct TreeNode { + T data; + TreeNode* left; + TreeNode* right; + + TreeNode(const T& val) : data(val), left(nullptr), right(nullptr) {} +}; + +// Проверка дали даден възел е листо +// Листо е възел, който няма деца +template +bool isLeaf(TreeNode* node) { + return node && !node->left && !node->right; +} + +// Проверка дали даден елемент се съдържа в дърво +template +bool contains(TreeNode* root, T value) { + if (root == nullptr) return false; + + if (root->data == value) return true; + + return contains(root->left, value) || contains(root->right, value); +} + +// Намиране на височина на дърво +// Височината на дърво е дължината на най-дългия път от корена до някое листо +template +int getHeight(TreeNode* root) { + if (!root) return -1; + + int leftHeight = getHeight(root->left); + int rightHeight = getHeight(root->right); + + return 1 + std::max(leftHeight, rightHeight); +} + +// Преброяване на възлите в дърво +template +int countNodes(TreeNode* root) { + if (!root) return 0; + + if (!root->left && !root->right) return 1; + + return 1 + countNodes(root->left) + countNodes(root->right); +} + +int main() { + // Създаване на двоично дърво от цели числа + TreeNode* root = new TreeNode(1); + root->left = new TreeNode(2); + root->right = new TreeNode(3); + root->left->left = new TreeNode(4); + root->left->right = new TreeNode(5); + root->right->left = new TreeNode(6); + root->right->right = new TreeNode(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 +#include +#include + +template +struct TreeNode { + T data; + TreeNode* left; + TreeNode* right; + + TreeNode(const T& val) : data(val), left(nullptr), right(nullptr) {} +}; + +// Preorder обхождане (корен, ляво, дясно) +template +void preorderTraversal(TreeNode* root) { + if (!root) return; + std::cout << root->data << " "; + preorderTraversal(root->left); + preorderTraversal(root->right); +} + +// Inorder обхождане (ляво, корен, дясно) +template +void inorderTraversal(TreeNode* root) { + if (!root) return; + inorderTraversal(root->left); + std::cout << root->data << " "; + inorderTraversal(root->right); +} + +// Postorder обхождане (ляво, дясно, корен) +template +void postorderTraversal(TreeNode* root) { + if (!root) return; + postorderTraversal(root->left); + postorderTraversal(root->right); + std::cout << root->data << " "; +} + +// Обхождане в широчина +template +void bfs(TreeNode* root) { + if (!root) return; + + std::queue*> q; + q.push(root); + + while (!q.empty()) { + TreeNode* 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* root = new TreeNode(1); + root->left = new TreeNode(2); + root->right = new TreeNode(3); + root->left->left = new TreeNode(4); + root->left->right = new TreeNode(5); + root->right->left = new TreeNode(6); + root->right->right = new TreeNode(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 Binary files /dev/null and b/Practicum/pract07/binaryTree.png differ diff --git a/Practicum/pract07/inorder.gif b/Practicum/pract07/inorder.gif new file mode 100644 index 0000000..d807a10 Binary files /dev/null and b/Practicum/pract07/inorder.gif differ diff --git a/Practicum/pract07/postorder.gif b/Practicum/pract07/postorder.gif new file mode 100644 index 0000000..023f302 Binary files /dev/null and b/Practicum/pract07/postorder.gif differ diff --git a/Practicum/pract07/preorder.gif b/Practicum/pract07/preorder.gif new file mode 100644 index 0000000..17ae1b0 Binary files /dev/null and b/Practicum/pract07/preorder.gif differ 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 Binary files /dev/null and b/Practicum/pract07/tree-dfs-vs-bfs.gif differ -- cgit v1.3.1-23-gd82d