[SDP/S09] Added solutions to all but the last two exericses

2 files changed, 404 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/exercises.cpp b/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/exercises.cpp
new file mode 100644
index 0000000..4e72328
--- /dev/null
+++ b/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/exercises.cpp
@@ -0,0 +1,168 @@
+#include "./tree-utils.h"
+#include <vector>
+
+// Exercise 1
+
+template <class T>
+bool isBST(Tree<T>* tree) {
+	if (tree == nullptr) return true;
+	return    (tree->left  == nullptr || tree->left->data < tree->data)
+	       && (tree->right == nullptr || tree->data       < tree->right->data)
+	       && isBST(tree->left) && isBST(tree->right);
+}
+
+void ex1() {
+	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 << isBST(t) << std::endl;
+
+	freeTree(t);
+}
+
+// Exercise 2
+
+template <class T>
+void recBuildBST(std::vector<T>& vec, int start, int end, Tree<T>*& parent) {
+	int mid = start + (end - start) / 2;
+	Tree<T>* current = new Tree<T>(vec[mid]);
+
+	if (parent == nullptr)
+		parent = current;
+
+	if (current->data < parent->data)
+		parent->left = current;
+	else if (parent->data < current->data)
+		parent->right = current;
+
+	if (mid - start > 0)
+		recBuildBST(vec, start, mid - 1, current);
+	if (end - mid > 0)
+		recBuildBST(vec, mid + 1, end, current);
+}
+
+template <class T>
+Tree<T>* vecToBST(std::vector<T>& vec) {
+	Tree<T>* result = nullptr;
+	recBuildBST(vec, 0, vec.size() - 1, result);
+	return result;
+}
+
+void ex2() {
+	std::vector<int> v = { 1, 3, 4, 6, 7, 8, 10, 13, 14 };
+	Tree<int>* t = vecToBST(v);
+	printTree(t);
+
+	freeTree(t);
+}
+
+// Exercise 3
+
+template <class T>
+void insertNodeInBST(Tree<T>*& tree, Tree<T>* node) {
+	if (tree == nullptr) {
+		tree = node;
+		return;
+	}
+	
+	insertNodeInBST((tree->data < node->data) ? tree->right : tree->left, node);
+}
+
+template <class T>
+void removeInBST(Tree<T>*& tree, const T& elem) {
+	Tree<T>** current = &tree;
+	while (*current != nullptr && (*current)->data != elem) {
+		current = ((*current)->data < elem) ? &((*current)->right) : &((*current)->left);
+	}
+	if (current == nullptr) return;
+
+	Tree<T>* oldCurrent = *current;
+	*current = (*current)->right;
+	insertNodeInBST(*current, oldCurrent->left);
+	delete oldCurrent;
+}
+
+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))));
+	removeInBST(t, 8);
+	printTree(t);
+
+	freeTree(t);
+}
+
+// Exercise 4
+
+template <class T>
+bool equal(Tree<T>* a, Tree<T>* b) {
+	if ((a == nullptr) != (b == nullptr)) return false;
+	else if (a == nullptr) return true;
+
+	return a->data == b->data && equal(a->left, b->left) && equal(a->right, b->right);
+}
+
+void ex4() {
+	Tree<int>* t1 = 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))));
+	Tree<int>* t2 = 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 << equal(t1, t2) << std::endl;
+
+	freeTree(t1);
+	freeTree(t2);
+}
+
+// Exercise 5
+
+template <class T>
+void rightRotation(Tree<T>*& tree) {
+	Tree<T>* root = tree;
+	Tree<T>* pivot = tree->left;
+
+	tree = pivot;
+	root->left = pivot->right;
+	tree->right = root;
+}
+
+template <class T>
+void leftRotation(Tree<T>*& tree) {
+	Tree<T>* root = tree;
+	Tree<T>* pivot = tree->right;
+
+	tree = pivot;
+	root->right = pivot->left;
+	tree->left = root;
+}
+
+void ex5() {
+	Tree<char>* t = new Tree<char>('Q', new Tree<char>('P', new Tree<char>('A'), new Tree<char>('B')), new Tree<char>('C'));
+	printTree(t);
+	rightRotation(t);
+	printTree(t);
+	leftRotation(t);
+	leftRotation(t);
+	printTree(t);
+	rightRotation(t);
+	printTree(t);
+
+	freeTree(t);
+}
+
+// Exercise 6
+
+template <class T>
+T pred(Tree<T>* tree, const T& x) {
+	if (tree->value > x) {
+		if (tree->left == nullptr) return tree->value;
+		pred(tree->left, x);
+	}
+	else {
+		if (tree->right == nullptr) return tree->value;
+		pred(tree->right, x);
+	}
+}
+
+void ex6() {
+
+}
+
+// main
+
+int main() {
+	ex5();
+}
diff --git a/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/tree-utils.h b/Year 2/Structures and data algorithms/09-Seminar-07.12.2022/tree-utils.h
new file mode 100644
index 0000000..c9faf2c
--- /dev/null
+++ b/Year 2/Structures and data algorithms/09-Seminar-07.12.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