[SDP/S08] Solved exercises from seminar

2 files changed, 400 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/08-Seminar-30.11.2022/exercises.cpp b/Year 2/Structures and data algorithms/08-Seminar-30.11.2022/exercises.cpp
new file mode 100644
index 0000000..390ae1b
--- /dev/null
+++ b/Year 2/Structures and data algorithms/08-Seminar-30.11.2022/exercises.cpp
@@ -0,0 +1,164 @@
+#include "tree-utils.h"
+
+// Exercise 1
+
+template <class T>
+void myInsertInBST(Tree<T>* tree, const T& elem) {
+	if (elem > tree->data) {
+		if (tree->right == nullptr)
+			tree->right = new Tree<T>(elem);
+		else
+			myInsertInBST(tree->right, elem);
+	}
+	else {
+		if (tree->left == nullptr)
+			tree->left = new Tree<T>(elem);
+		else
+			myInsertInBST(tree->left, elem);
+	}
+}
+
+void ex1() {
+	Tree<int>* t = new Tree<int>(8, new Tree<int>(3, new Tree<int>(1), new Tree<int>(6, nullptr, new Tree<int>(7))), new Tree<int>(10, nullptr, new Tree<int>(14, new Tree<int>(13))));
+	myInsertInBST(t, 4);
+	printTree(t);
+
+	freeTree(t);
+}
+
+// Exercise 2
+
+template <class T>
+bool myContains(Tree<T>* tree, const T& elem) {
+	if (tree == nullptr) return false;
+	if (tree->data == elem) return true;
+	return myContains(tree->left, elem) || myContains(tree->right, elem);
+}
+
+template <class T>
+bool myContainsBST(Tree<T>* tree, const T& elem) {
+	if (tree == nullptr) return false;
+	if (tree->data == elem)
+		return true;
+	else if (elem < tree->data)
+		return myContainsBST(tree->left, elem);
+	else
+		return myContainsBST(tree->right, elem);
+}
+
+void ex2() {
+	Tree<int>* t = 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))));
+	std::cout << myContains(t, 9) << " " << myContains(t, 4) << std::endl;
+	std::cout << myContainsBST(t, 9) << " " << myContainsBST(t, 4) << std::endl;
+
+	freeTree(t);
+}
+
+// Exercise 3
+
+template <class T>
+void maxRec(Tree<T>* tree, T& max) {
+	if (tree == nullptr) return;
+	if (tree->data > max) max = tree->data;
+	maxRec(tree->left, max);
+	maxRec(tree->right, max);
+}
+
+template <class T>
+T max(Tree<T>* tree) {
+	if (tree == nullptr) return T();
+	T max = tree->data;
+	maxRec(tree, max);
+	return max;
+}
+
+template <class T>
+T maxBST(Tree<T>* tree) {
+	if (tree == nullptr) return T();
+	while (tree->right != nullptr) tree = tree->right;
+	return tree->data;
+}
+
+template <class T>
+void minRec(Tree<T>* tree, T& max) {
+	if (tree == nullptr) return;
+	if (tree->data < max) max = tree->data;
+	minRec(tree->left, max);
+	minRec(tree->right, max);
+}
+
+template <class T>
+T min(Tree<T>* tree) {
+	if (tree == nullptr) return T();
+	T max = tree->data;
+	minRec(tree, max);
+	return max;
+}
+
+template <class T>
+T minBST(Tree<T>* tree) {
+	if (tree == nullptr) return T();
+	while (tree->left != nullptr) tree = tree->left;
+	return tree->data;
+}
+
+void ex3() {
+	Tree<int>* t = 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))));
+	std::cout << max(t) << " " << maxBST(t) << std::endl;
+	std::cout << min(t) << " " << minBST(t) << std::endl;
+
+	freeTree(t);
+}
+
+// Exercise 4
+
+template <class T>
+void heightRec(Tree<T>* tree, int& result, int current = 0) {
+	if (tree == nullptr) return;
+	if (current > result) result = current;
+	heightRec(tree->left, result, current + 1);
+	heightRec(tree->right, result, current + 1);
+}
+
+template <class T>
+int height(Tree<T>* tree) {
+	int result = 0;
+	heightRec(tree, result);
+	return result;
+}
+
+void ex4() {
+	Tree<int>* t = 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))));
+	std::cout << height(t) << std::endl;
+
+	freeTree(t);
+}
+
+// Exercise 5
+
+template <class T>
+void inorderTraversal(Tree<T>* tree, void (*todo)(T)) {
+	if (tree == nullptr) return;
+	inorderTraversal(tree->left, todo);
+	todo(tree->data);
+	inorderTraversal(tree->right, todo);
+}
+
+template <class T>
+void print(T elem) {
+	std::cout << elem << " ";
+}
+
+void ex5() {
+	Tree<int>* t = 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(t, print); // on a BST, it prints all elements, in ascending order
+	std::cout << std::endl;
+
+	freeTree(t);
+}
+
+// main
+
+int main() {
+	ex5();
+}
diff --git a/Year 2/Structures and data algorithms/08-Seminar-30.11.2022/tree-utils.h b/Year 2/Structures and data algorithms/08-Seminar-30.11.2022/tree-utils.h
new file mode 100644
index 0000000..c9faf2c
--- /dev/null
+++ b/Year 2/Structures and data algorithms/08-Seminar-30.11.2022/tree-utils.h
@@ -0,0 +1,236 @@
+/* Author  : StoychoX
+ * Source  : https://github.com/stoychoX/Data-structures-and-algorithms/raw/main/Seminar08/tree-utils.h
+ * License : <none>
+ * Date    : 25.12.2022
+ */
+
+#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