[SDP/E2] Added work from exam

1 files changed, 119 insertions, 0 deletions

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 <iostream>
+#include <cstring>
+#include <vector> // Б подточка
+
+template <typename T>
+struct Node {
+	T data;
+	Node<T> *left, *right;
+	Node(const T& data, Node<T>* left = nullptr, Node<T>* right = nullptr) : data(data), left(left), right(right) {}
+};
+
+void freeTree(const Node<char>* tree) {
+	if (tree == nullptr) return;
+	freeTree(tree->left);
+	freeTree(tree->right);
+	delete tree;
+}
+
+/* Подточка А */
+
+bool checkWord(const Node<char>* 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<char>* 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<char>* t =
+		new Node<char>('F',
+				new Node<char>('B',
+					new Node<char>('A'),
+					new Node<char>('D',
+						new Node<char>('C'),
+						new Node<char>('E'))),
+				new Node<char>('G',
+					nullptr,
+					new Node<char>('I',
+						new Node<char>('H'),
+						nullptr)));
+
+	std::cout << readWord(t, "GIBDC") << readWord(t, "GIBD") << readWord(t, "GIBCD") << readWord(t, "GHBD") << std::endl;
+	freeTree(t);
+}
+
+/* Подточка Б */
+
+bool risingOrder(std::vector<char>& 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<char>* tree, size_t level, std::vector<char>& 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<char>* tree) {
+	std::vector<char> 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<char>* t =
+		new Node<char>('F',
+				new Node<char>('Z',
+					new Node<char>('Z'),
+					new Node<char>('D',
+						new Node<char>('C'),
+						new Node<char>('E'))),
+				new Node<char>('G',
+					nullptr,
+					new Node<char>('I',
+						new Node<char>('H'),
+						nullptr)));
+
+	std::cout << minLevel(t) << std::endl;
+	freeTree(t);
+}
+
+int main() {
+	//A();
+	B();
+}