Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <ctime>
- #include <fstream>
- namespace util {
- inline int generateRandomInteger(int min, int max) {
- return (std::rand() % (max - min)) + min;
- }
- inline unsigned int max(unsigned int a, unsigned int b) {
- if(a > b)
- return a;
- return b;
- }
- }
- struct Node {
- int key;
- char key_string[10];
- Node* leftChild;
- Node* rightChild;
- Node(int key) : key(key) {
- leftChild = nullptr;
- rightChild = nullptr;
- std::sprintf(key_string, "%d", key);
- }
- bool isLeaf() {
- return (leftChild == nullptr && rightChild == nullptr);
- }
- bool hasOnlyOneChild() {
- return hasOnlyLeftChild() || hasOnlyRightChild();
- }
- bool hasOnlyLeftChild() {
- return (rightChild == nullptr);
- }
- bool hasOnlyRightChild() {
- return (leftChild == nullptr);
- }
- bool hasTwoChildren() {
- return (leftChild != nullptr && rightChild != nullptr);
- }
- Node* getSmallestNodeInRightSubtree() {
- Node *tmp = this->rightChild;
- while(tmp != nullptr && tmp->leftChild != nullptr) {
- tmp = tmp->leftChild;
- }
- return tmp;
- }
- void assignValues(const Node* node) {
- this->key = node->key;
- std::strcpy(this->key_string, node->key_string);
- }
- friend std::ostream&operator<<(std::ostream& out, const Node* node) {
- std::cout << "Node={key=" << node->key << ", key_string=" << std::string(node->key_string) << "}";
- return out;
- }
- };
- class BinarySearchTree {
- private:
- Node* root;
- unsigned int size;
- public:
- BinarySearchTree() {
- std::srand(std::time(nullptr));
- root = nullptr;
- size = 0;
- }
- bool add(int key) {
- Node* node = new Node(key);
- if(root == nullptr) { // nie istnieje korzen
- root = node;
- size++;
- return true;
- } else { // korzen juz istnieje
- Node* tmp = root;
- while(true) {
- if(node->key < tmp->key) {
- if(tmp->leftChild == nullptr) { // znaleziono miejsce
- tmp->leftChild = node;
- size++;
- return true;
- }
- tmp = tmp->leftChild;
- } else if(node->key > tmp->key) {
- if(tmp->rightChild == nullptr) { // znaleziono miejsce
- tmp->rightChild = node;
- size++;
- return true;
- }
- tmp = tmp->rightChild;
- } else {
- std::cout << "ERROR: w drzewie JUZ znajduje sie wezel o kluczu " << node->key << std::endl;
- return false;
- }
- }
- }
- }
- void addManyRandom(unsigned int n) {
- for (int i = 0; i < n; ++i) {
- unsigned int key = util::generateRandomInteger(-1000, 1000);
- while(!this->add(key)) {
- key = util::generateRandomInteger(-1000, 1000);
- }
- }
- }
- Node* find(int key) {
- Node* tmp = root;
- while(tmp != nullptr) {
- if(key < tmp->key) {
- tmp = tmp->leftChild;
- } else if(key > tmp->key) {
- tmp = tmp->rightChild;
- } else { //znaleziono wezel
- return tmp;
- }
- }
- return nullptr;
- }
- void show(int key) {
- Node* result = this->find(key);
- if(result == nullptr)
- std::cout << "ERROR: nie znaleziono wezla o kluczu " << key << std::endl;
- else
- std::cout << result << std::endl;
- }
- Node *getParent(int key) {
- if(key == root->key) {
- return nullptr;
- }
- Node* tmp = root;
- while(tmp != nullptr) {
- if((tmp->leftChild != nullptr && tmp->leftChild->key == key)
- || (tmp->rightChild != nullptr && tmp->rightChild->key == key))
- return tmp;
- if(key < tmp->key) {
- tmp = tmp->leftChild;
- } else if(key > tmp->key) {
- tmp = tmp->rightChild;
- }
- }
- return nullptr;
- }
- bool remove(int key) {
- Node* found = this->find(key);
- if(found == nullptr) { // nie znaleziono wezla
- return false;
- }
- Node* parent = this->getParent(key);
- if(found->isLeaf()) {
- removeLeaf(found, parent);
- size--;
- return true;
- }
- else if(found->hasOnlyOneChild()) {
- removeNodeWithOnlyOneChild(found, parent);
- size--;
- return true;
- }
- else if (found->hasTwoChildren()){
- removeNodeWithBothChildren(found, parent);
- size--;
- return true;
- }
- return false;
- }
- void removeLeaf(Node* leaf, Node* parent) {
- if(parent->leftChild == leaf) { // leaf jest lewym dzieckiem
- parent->leftChild = nullptr;
- delete parent->leftChild;
- } else if(parent->rightChild == leaf) { // leaf jest prawym dzieckiem
- parent->rightChild = nullptr;
- delete parent->rightChild;
- }
- }
- void removeNodeWithOnlyOneChild(Node* node, Node* parent) {
- if(node == root) {
- if(root->leftChild != nullptr) {
- root = root->leftChild;
- }
- else if(root->rightChild != nullptr) {
- root = root->rightChild;
- }
- }
- else if(node->hasOnlyLeftChild()) {
- if(parent->leftChild == node) { // node jest lewym dzieckiem
- parent->leftChild = node->leftChild;
- delete node;
- } else if(parent->rightChild == node) {// node jest prawym dzieckiem
- parent->rightChild = node->leftChild;
- delete node;
- }
- } else if(node->hasOnlyRightChild()) {
- if (parent->leftChild == node) { // node jest lewym dzieckiem
- parent->leftChild = node->rightChild;
- delete node;
- } else if (parent->rightChild == node) {// node jest prawym dzieckiem
- parent->rightChild = node->rightChild;
- delete node;
- }
- }
- }
- void removeNodeWithBothChildren(Node* node, Node* parent) {
- Node* smallestNodeInRightSubtree = node->getSmallestNodeInRightSubtree();
- Node* smallestNodeInRightSubtree_parent = getParent(smallestNodeInRightSubtree->key);
- node->assignValues(smallestNodeInRightSubtree);
- if(smallestNodeInRightSubtree->isLeaf()) {
- removeLeaf(smallestNodeInRightSubtree, smallestNodeInRightSubtree_parent);
- }
- else if(smallestNodeInRightSubtree->hasOnlyOneChild()) {
- removeNodeWithOnlyOneChild(smallestNodeInRightSubtree, smallestNodeInRightSubtree_parent);
- }
- }
- enum class DfsType {
- PRE_ORDER,
- IN_ORDER,
- POST_ORDER,
- };
- void dfs(DfsType type) {
- switch (type) {
- case DfsType::PRE_ORDER:
- std::cout << "\n===: PreOrder Depth First Search :===" << std::endl;
- dfsPreOrder(root);
- break;
- case DfsType::IN_ORDER:
- std::cout << "\n===: InOrder Depth First Search :===" << std::endl;
- dfsInOrder(root);
- break;
- case DfsType::POST_ORDER:
- std::cout << "\n===: PostOrder Depth First Search :===" << std::endl;
- dfsPostOrder(root);
- break;
- default:
- std::cout << "NIEPOPRAWNY WYBOR DFS" << std::endl;
- break;
- }
- }
- void makeBackbone() {
- Node* parentTmp = root;
- Node* grandFather = nullptr;
- while(parentTmp != nullptr) {
- if(parentTmp->leftChild == nullptr) {
- Node* grandFather = parentTmp;
- parentTmp = parentTmp->rightChild;
- } else {
- Node * childTmp = parentTmp->leftChild;
- rotateRight(childTmp, parentTmp, grandFather);
- parentTmp = childTmp;
- }
- }
- }
- void performDsw() {
- Node* childTmp = nullptr;
- Node* parentTmp = root;
- Node* grandParentTmp = nullptr;
- unsigned int treeSize = getSize();
- unsigned int k = 1;
- while(k <= treeSize)
- k = 2*k+1;
- k = k / 2;
- for (int i = 0; i < (treeSize - k); ++i) {
- childTmp = parentTmp->rightChild;
- if(childTmp != nullptr) {
- rotateLeft(parentTmp->rightChild, parentTmp, grandParentTmp);
- grandParentTmp = childTmp;
- parentTmp = childTmp->rightChild;
- }
- }
- while (k > 1) {
- k = k / 2;
- grandParentTmp = nullptr;
- parentTmp = root;
- for (int i = 0; i < k; ++i) {
- if(parentTmp != nullptr && parentTmp->rightChild != nullptr) {
- childTmp = parentTmp->rightChild;
- rotateLeft(parentTmp->rightChild, parentTmp, grandParentTmp);
- }
- grandParentTmp = childTmp;
- parentTmp = childTmp->rightChild;
- }
- }
- }
- unsigned int getHeight(Node* current) {
- if(current == nullptr) { // root jest nullem
- return 0;
- }
- unsigned int leftHeight = getHeight(current->leftChild);
- unsigned int rightHeight = getHeight(current->rightChild);
- return (util::max(leftHeight, rightHeight) + 1);
- }
- unsigned int getHeight() {
- return getHeight(root);
- }
- unsigned int getSize() const {
- return size;
- }
- private:
- void dfsPreOrder(Node* start) {
- if(start == nullptr)
- return;
- std::cout << start << std::endl;
- dfsPreOrder(start->leftChild);
- dfsPreOrder(start->rightChild);
- }
- void dfsInOrder(Node* start) {
- if(start == nullptr)
- return;
- dfsInOrder(start->leftChild);
- std::cout << start << std::endl;
- dfsInOrder(start->rightChild);
- }
- void dfsPostOrder(Node* start) {
- if(start == nullptr)
- return;
- dfsPostOrder(start->leftChild);
- dfsPostOrder(start->rightChild);
- std::cout << start << std::endl;
- }
- void rotateLeft(Node* child, Node* parent, Node* grandParent) {
- if (grandParent == nullptr) {
- root = child;
- } else {
- if (grandParent->rightChild == parent)
- grandParent->rightChild = child;
- else if (grandParent->leftChild == parent)
- grandParent->leftChild = child;
- }
- if(child != nullptr) {
- Node *tmp = child->leftChild;
- child->leftChild = parent;
- parent->rightChild = tmp;
- }
- }
- void rotateRight(Node* child, Node* parent, Node* grandParent) {
- if (grandParent == nullptr) {
- root = child;
- } else {
- if (grandParent->rightChild == parent)
- grandParent->rightChild = child;
- else if (grandParent->leftChild == parent)
- grandParent->leftChild = child;
- }
- Node *tmp = child->rightChild;
- child->rightChild = parent;
- parent->leftChild = tmp;
- }
- };
- struct FileStructure {
- unsigned int X1;
- unsigned int X2;
- };
- FileStructure readFile(const std::string& path);
- int main() {
- FileStructure fileStructure = readFile("inlab05.txt");
- BinarySearchTree tree;
- tree.addManyRandom(fileStructure.X1);
- std::cout << tree.getHeight() << std::endl;
- tree.makeBackbone();
- tree.performDsw();
- std::cout << tree.getHeight() << std::endl;
- // tree.removeAll();
- }
- FileStructure readFile(const std::string& path) {
- FileStructure fileStructure;
- std::fstream file;
- file.open(path);
- if(file.good()) {
- file >> fileStructure.X1;
- file >> fileStructure.X2;
- }
- return fileStructure;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement