From 5e595c4055876c4169e6eb7a9bcbbe67787e69ce Mon Sep 17 00:00:00 2001 From: Syndamia Date: Thu, 5 Jan 2023 18:28:02 +0200 Subject: [SDP/E2] Added work from exam --- .../Structures and data algorithms/Exam 2/ex1.cpp | 119 +++++++++++++++++++++ 1 file changed, 119 insertions(+) create mode 100644 Year 2/Structures and data algorithms/Exam 2/ex1.cpp (limited to 'Year 2/Structures and data algorithms/Exam 2/ex1.cpp') diff --git a/Year 2/Structures and data algorithms/Exam 2/ex1.cpp b/Year 2/Structures and data algorithms/Exam 2/ex1.cpp new file mode 100644 index 0000000..822d316 --- /dev/null +++ b/Year 2/Structures and data algorithms/Exam 2/ex1.cpp @@ -0,0 +1,119 @@ +#include +#include +#include // Б подточка + +template +struct Node { + T data; + Node *left, *right; + Node(const T& data, Node* left = nullptr, Node* right = nullptr) : data(data), left(left), right(right) {} +}; + +void freeTree(const Node* tree) { + if (tree == nullptr) return; + freeTree(tree->left); + freeTree(tree->right); + delete tree; +} + +/* Подточка А */ + +bool checkWord(const Node* tree, const char* start, const char* end) { + if (start == end) + return true; + if (start == nullptr || tree == nullptr) + return false; + if (*start != tree->data) + return false; + + return checkWord(tree->left, start + 1, end) || checkWord(tree->right, start + 1, end); +} + +bool readWord(const Node* tree, const char* word) { + if (strlen(word) < 4) + throw std::runtime_error("Word length cannot be less than 4!"); + + const char* endWord = word; + while (*endWord != '\0') endWord++; + + const char* separator = word + 1; + while (separator != endWord) { + if (checkWord(tree->right, word, separator) && checkWord(tree->left, separator, endWord)) + return true; + separator++; + } + return false; +} + +void A() { + const Node* t = + new Node('F', + new Node('B', + new Node('A'), + new Node('D', + new Node('C'), + new Node('E'))), + new Node('G', + nullptr, + new Node('I', + new Node('H'), + nullptr))); + + std::cout << readWord(t, "GIBDC") << readWord(t, "GIBD") << readWord(t, "GIBCD") << readWord(t, "GHBD") << std::endl; + freeTree(t); +} + +/* Подточка Б */ + +bool risingOrder(std::vector& v) { + for (size_t i = 0; i < v.size() - 1; i++) { + if (v[i] > v[i+1]) return false; + } + return true; +} + +void getLevel(const Node* tree, size_t level, std::vector& out) { + if (level == 0) return; + if (tree->left != nullptr) getLevel(tree->left, level - 1, out); + if (level == 1) { + out.push_back(tree->data); + return; + } + if (tree->right != nullptr) getLevel(tree->right, level - 1, out); +} + +size_t minLevel(const Node* tree) { + std::vector temp; + size_t i = 1; + getLevel(tree, i, temp); + while (!temp.empty()) { + i++; + temp.clear(); + getLevel(tree, i, temp); + if (risingOrder(temp)) break; + } + return (temp.empty()) ? 0 : i; +} + +void B() { + const Node* t = + new Node('F', + new Node('Z', + new Node('Z'), + new Node('D', + new Node('C'), + new Node('E'))), + new Node('G', + nullptr, + new Node('I', + new Node('H'), + nullptr))); + + std::cout << minLevel(t) << std::endl; + freeTree(t); +} + +int main() { + //A(); + B(); +} -- cgit v1.3.1-26-gb76a