Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //SDIZO I1 222A LAB04
- //Paweł Patyk
- //pp41473@zut.edu.pl
- #include "pch.h"
- #include <iostream>
- #include <sstream>
- #include <string>
- #include <cstdlib>
- #include <ctime>
- #include <fstream>
- #include <math.h>
- using namespace std;
- class Element {
- private:
- int key;
- int balance;
- Element *ptrLeft;
- Element *ptrRight;
- char tab[10];
- public:
- Element();
- Element(int keyVal);
- ~Element();
- int getKey();
- int getBalance();
- Element * getPtrLeft();
- Element * getPtrRight();
- char * getTab();
- void setPtrLeft(int liczba);
- void setPtrLeft(Element *ptr);
- void setPtrRight(int liczba);
- void setPtrRight(Element *ptr);
- void increaseBalance();
- void reduceBalance();
- };
- Element::Element() {
- }
- Element::Element(int keyVal) {
- key = keyVal;
- sprintf_s(tab, "%d", keyVal);
- balance = 0;
- }
- Element ::~Element() {
- }
- int Element::getKey() {
- return this->key;
- }
- int Element::getBalance() {
- return this->balance;
- }
- Element * Element::getPtrLeft() {
- return this->ptrLeft;
- }
- Element * Element::getPtrRight() {
- return this->ptrRight;
- }
- char * Element::getTab() {
- return tab;
- }
- void Element::setPtrLeft(int liczba) {
- ptrLeft = new Element(liczba);
- }
- void Element::setPtrRight(int liczba) {
- ptrRight = new Element(liczba);
- }
- void Element::setPtrLeft(Element * ptr) {
- ptrLeft = ptr;
- }
- void Element::setPtrRight(Element * ptr) {
- ptrRight = ptr;
- }
- void Element::increaseBalance() {
- balance++;
- }
- void Element::reduceBalance() {
- balance--;
- }
- class Tree {
- private:
- Element * root = nullptr;
- int numberElements;
- public:
- Tree();
- Tree(int i);
- void setRoot(Element * ptr);
- void add(int keyVal);
- void addMany(int num);
- bool find(int key_val, bool kom = true);
- void remove(int key_val);
- void rotateRight(Element * ptrGrand,Element * ptrPar,Element * ptrChild);
- void rotateLeft(Element * ptrGrand, Element * ptrPar, Element * ptrChild);
- void showPreorder();
- void showPreorder(Element * ptr, int &i);
- void showInorder();
- void showInorder(Element * ptr, int &i);
- void showPostorder();
- void showPostorder(Element * ptr, int &i);
- void showNumberElements();
- };
- Tree::Tree() {
- }
- void Tree::setRoot(Element * ptr) {
- root = ptr;
- }
- void Tree::showPreorder(Element * ptr, int &i) {
- if (ptr == nullptr) {
- return;
- }
- else {
- i++;
- cout << ptr->getKey() << endl;
- showPreorder(ptr->getPtrLeft(), i);
- showPreorder(ptr->getPtrRight(), i);
- }
- }
- void Tree::showPreorder() {
- int i = 0;
- if (root == nullptr) {
- cout << "nie mozna wyswietlic korzen jest pusty" << endl;
- }
- else {
- showPreorder(root, i);
- cout << "liczba odwiedzanych wezlow : " << i << endl;
- }
- }
- void Tree::showInorder(Element * ptr, int &i) {
- if (ptr == nullptr) {
- return;
- }
- else {
- i++;
- showInorder(ptr->getPtrLeft(), i);
- cout << ptr->getKey() << endl;
- showInorder(ptr->getPtrRight(), i);
- }
- }
- void Tree::showInorder() {
- int i = 0;
- if (root == nullptr) {
- cout << "nie mozna wyswietlic korzen jest pusty" << endl;
- }
- else {
- showInorder(root, i);
- cout << "liczba odwiedzanych wezlow : " << i << endl;
- }
- }
- void Tree::showPostorder(Element * ptr, int &i) {
- if (ptr == nullptr) {
- return;
- }
- else {
- i++;
- showPostorder(ptr->getPtrLeft(), i);
- showPostorder(ptr->getPtrRight(), i);
- cout << ptr->getKey() << endl;
- }
- }
- void Tree::showPostorder() {
- int i = 0;
- if (root == nullptr) {
- cout << "nie mozna wyswietlic korzen jest pusty" << endl;
- }
- else {
- showPostorder(root, i);
- cout << "liczba odwiedzanych wezlow : " << i << endl;
- }
- }
- void Tree::showNumberElements() {
- cout << "Liczba elementow : " << numberElements << endl;
- }
- bool Tree::find(int key_val, bool kom) {
- Element * supPtr = root;
- if (root == nullptr) {
- if (kom == true) {
- cout << "korzen jest pusty" << endl;
- }
- return false;
- }
- if (supPtr->getKey() == key_val) {
- if (kom == true) {
- cout << "istnieje element z podanym kluczem " << endl;
- }
- return true;
- }
- else if (supPtr->getKey() > key_val) {
- supPtr = supPtr->getPtrLeft();
- }
- else if (supPtr->getKey() < key_val) {
- supPtr = supPtr->getPtrRight();
- }
- while (supPtr != nullptr) {
- if (supPtr->getKey() == key_val) {
- if (kom == true) {
- cout << "istnieje element z podanym kluczem " << endl;
- }
- return true;
- }
- else if (supPtr->getKey() > key_val) {
- supPtr = supPtr->getPtrLeft();
- }
- else if (supPtr->getKey() < key_val) {
- supPtr = supPtr->getPtrRight();
- }
- }
- if (supPtr == nullptr) {
- if (kom == true) {
- cout << "nie ma elementu o podanym kluczu " << endl;
- }
- return false;
- }
- }
- void Tree::rotateRight(Element * ptrGrand, Element * ptrPar, Element * ptrChild) {
- if (ptrGrand != nullptr) {
- if (ptrGrand->getPtrRight() == ptrPar) {
- ptrGrand->setPtrRight(ptrChild);
- }
- else{
- ptrGrand->setPtrLeft(ptrChild);
- }
- }
- else {
- root = ptrChild;
- }
- Element *ptrSup = ptrChild->getPtrRight();
- ptrChild->setPtrLeft(ptrPar);
- ptrPar->setPtrRight(ptrSup);
- }
- void Tree::rotateLeft(Element * ptrGrand, Element * ptrPar, Element * ptrChild) {
- if (ptrGrand != nullptr) {
- if (ptrGrand->getPtrRight() == ptrPar) {
- ptrGrand->setPtrRight(ptrChild);
- }
- else {
- ptrGrand->setPtrLeft(ptrChild);
- }
- }
- else {
- root = ptrChild;
- }
- Element *ptrSup = ptrChild->getPtrLeft();
- ptrChild->setPtrRight(ptrPar);
- ptrPar->setPtrLeft(ptrSup);
- }
- void Tree::add(int keyVal) {
- bool czy_sie_powtarza = find(keyVal, false);
- if (czy_sie_powtarza == true) {
- cout << "nie mozna dodac obikektu poniewaz istnieje juz jeden z takim kluczem" << endl;
- return;
- }
- if (root == nullptr) {
- root = new Element(keyVal);
- numberElements++;
- return;
- }
- Element * supPtr = root;
- int sizeArray = log2(numberElements) + 1;
- Element **tabPtr = new Element *[sizeArray];
- for (int i = 0; i < sizeArray; i++) {
- tabPtr[i] = nullptr;
- }
- for (int i = 0; i < sizeArray; i++) {
- tabPtr[i] = supPtr;
- if (supPtr->getKey() > keyVal && supPtr->getPtrLeft() != nullptr) {
- supPtr->reduceBalance();
- supPtr = supPtr->getPtrLeft();
- }
- else if (supPtr->getKey() < keyVal && supPtr->getPtrRight() != nullptr) {
- supPtr->increaseBalance();
- supPtr = supPtr->getPtrRight();
- }
- else if (supPtr->getKey() > keyVal && supPtr->getPtrLeft() == nullptr) {
- supPtr->reduceBalance();
- supPtr->setPtrLeft(keyVal);
- break;
- }
- else if (supPtr->getKey() < keyVal && supPtr->getPtrRight() == nullptr) {
- supPtr->increaseBalance();
- supPtr->setPtrRight(keyVal);
- break;
- }
- }
- numberElements++;
- for (int i = 0; i < sizeArray; i++) {
- if (tabPtr[i] == nullptr) {
- break;
- }
- cout << tabPtr[i]->getBalance() << " " << tabPtr[i]->getKey() << endl;
- }
- cout << endl;
- }
- int main()
- {
- Tree tree;
- //tree.showNumberElements();
- tree.add(10);
- tree.add(5);
- tree.add(15);
- tree.add(6);
- tree.add(11);
- //tree.add(13);
- //tree.add(18);
- //srand(time(NULL));
- //int k1, k2, k3, k4, number;
- //fstream infile;
- //infile.open("inlab03.txt");
- //if (infile.good() == false) {
- // cout << "blad" << endl;
- //}
- //infile >> number;
- //infile >> k1;
- //infile >> k2;
- //infile >> k3;
- //infile >> k4;
- //infile.close();
- }
- //class Element {
- //
- //private:
- // int key;
- // Element * ptr_left = nullptr;
- // Element * ptr_right = nullptr;
- // char tab[10];
- // int balance;
- //public:
- // Element();
- // Element(int key_val);
- // int get_key();
- // Element * get_ptr_left();
- // Element * get_ptr_right();
- // void set_ptr_left(int liczba);
- // void set_ptr_right(int liczba);
- // void set_ptr_left(Element * ptr);
- // void set_ptr_right(Element * ptr);
- // char * show_tab();
- //
- //};
- //Element::Element() {
- //
- //}
- //
- //Element::Element(int key_val) {
- // key = key_val;
- // sprintf_s(tab, "%d", key_val);
- //}
- //
- //
- //
- //int Element::get_key() {
- // return key;
- //}
- //
- //Element * Element::get_ptr_left() {
- // return ptr_left;
- //}
- //
- //Element * Element::get_ptr_right() {
- // return ptr_right;
- //}
- //
- //void Element::set_ptr_left(int liczba) {
- // ptr_left = new Element(liczba);
- //}
- //
- //void Element::set_ptr_right(int liczba) {
- // ptr_right = new Element(liczba);
- //}
- //
- //
- //void Element::set_ptr_left(Element * ptr) {
- // ptr_left = ptr;
- //}
- //
- //void Element::set_ptr_right(Element * ptr) {
- // ptr_right = ptr;
- //}
- //
- //
- //char * Element::show_tab() {
- // return tab;
- //}
- //
- //class Tree {
- //private:
- // Element * root = nullptr;
- //
- //public:
- // Tree();
- // Tree(int i);
- // void set_root(Element * ptr);
- // void add(int key_val);
- // void add_many(int num);
- // bool find(int key_val, bool kom = true);
- // void remove(int key_val);
- // void show_pre_order();
- // void show_pre_order(Element * ptr, int &i);
- // void show_in_order();
- // void show_in_order(Element * ptr, int &i);
- // void show_post_order();
- // void show_post_order(Element * ptr, int &i);
- //};
- //
- //
- //
- //
- //
- //
- //
- //Tree::Tree() {
- //
- //}
- //
- //void Tree::set_root(Element * ptr) {
- // root = ptr;
- //}
- //
- //bool Tree::find(int key_val, bool kom) {
- // Element * sup_ptr = root;
- // if (root == nullptr) {
- // if (kom == true) {
- // cout << "korzen jest pusty" << endl;
- //
- // }
- // return false;
- // }
- // if (sup_ptr->get_key() == key_val) {
- // if (kom == true) {
- // cout << "istnieje element z podanym kluczem " << endl;
- //
- // }
- // return true;
- // }
- // else if (sup_ptr->get_key() > key_val) {
- // sup_ptr = sup_ptr->get_ptr_left();
- // }
- // else if (sup_ptr->get_key() < key_val) {
- // sup_ptr = sup_ptr->get_ptr_right();
- // }
- //
- // while (sup_ptr != nullptr) {
- // if (sup_ptr->get_key() == key_val) {
- // if (kom == true) {
- // cout << "istnieje element z podanym kluczem " << endl;
- // }
- // return true;
- // }
- // else if (sup_ptr->get_key() > key_val) {
- // sup_ptr = sup_ptr->get_ptr_left();
- // }
- // else if (sup_ptr->get_key() < key_val) {
- // sup_ptr = sup_ptr->get_ptr_right();
- // }
- // }
- // if (sup_ptr == nullptr) {
- // if (kom == true) {
- // cout << "nie ma elementu o podanym kluczu " << endl;
- //
- // }
- // return false;
- // }
- //}
- //
- //
- //void Tree::add(int key_val) {
- //
- // if (root == nullptr) {
- // root = new Element(key_val);
- // return;
- //
- // }
- //
- // bool czy_sie_powtarza = find(key_val, false);
- // if (czy_sie_powtarza == true) {
- // cout << "nie mozna dodac obikektu poniewaz istnieje juz jeden z takim kluczem" << endl;
- // return;
- // }
- //
- // Element * sup_ptr = root;
- //
- //
- // while ((sup_ptr->get_key() > key_val && sup_ptr->get_ptr_left() != nullptr) || (sup_ptr->get_key() < key_val && sup_ptr->get_ptr_right() != nullptr)) {
- // if (sup_ptr->get_key() > key_val) {
- // sup_ptr = sup_ptr->get_ptr_left();
- // }
- // else if (sup_ptr->get_key() < key_val) {
- // sup_ptr = sup_ptr->get_ptr_right();
- // }
- //
- // }
- // if (sup_ptr->get_key() > key_val) {
- // sup_ptr->set_ptr_left(key_val);
- // }
- // else if (sup_ptr->get_key() < key_val) {
- // sup_ptr->set_ptr_right(key_val);
- // }
- //
- //}
- //
- //void Tree::add_many(int num) {
- // for (int i = 0; i < num; i++) {
- // int key_val = (rand() % 20000) - 10000;
- // while (find(key_val, false) == true) {
- // key_val = (rand() % 20000) - 10000;
- // }
- // add(key_val);
- // }
- //
- //}
- //
- //
- //
- //void Tree::show_pre_order(Element * ptr, int &i) {
- // if (ptr == nullptr) {
- // return;
- // }
- // else {
- // i++;
- // cout << ptr->get_key() << endl;
- // show_pre_order(ptr->get_ptr_left(), i);
- // show_pre_order(ptr->get_ptr_right(), i);
- // }
- //}
- //
- //void Tree::show_pre_order() {
- // int i = 0;
- // if (root == nullptr) {
- // cout << "nie mozna wyswietlic korzen jest pusty" << endl;
- // }
- // else {
- // show_pre_order(root, i);
- // cout << "liczba odwiedzanych wezlow : " << i << endl;
- // }
- //}
- //
- //void Tree::show_in_order(Element * ptr, int &i) {
- // if (ptr == nullptr) {
- // return;
- // }
- // else {
- // i++;
- // show_in_order(ptr->get_ptr_left(), i);
- // cout << ptr->get_key() << endl;
- // show_in_order(ptr->get_ptr_right(), i);
- // }
- //}
- //
- //void Tree::show_in_order() {
- // int i = 0;
- //
- // if (root == nullptr) {
- // cout << "nie mozna wyswietlic korzen jest pusty" << endl;
- // }
- // else {
- // show_in_order(root, i);
- // cout << "liczba odwiedzanych wezlow : " << i << endl;
- // }
- //}
- //
- //
- //
- //void Tree::show_post_order(Element * ptr, int &i) {
- // if (ptr == nullptr) {
- // return;
- // }
- // else {
- // i++;
- // show_post_order(ptr->get_ptr_left(), i);
- // show_post_order(ptr->get_ptr_right(), i);
- // cout << ptr->get_key() << endl;
- // }
- //}
- //
- //
- //void Tree::show_post_order() {
- // int i = 0;
- // if (root == nullptr) {
- // cout << "nie mozna wyswietlic korzen jest pusty" << endl;
- // }
- // else {
- // show_post_order(root, i);
- // cout << "liczba odwiedzanych wezlow : " << i << endl;
- // }
- //}
- //
- //
- //void Tree::remove(int key_val) {
- // Element * ptr = root;
- // Element * par_ptr = nullptr;
- // if (root == nullptr) {
- // cout << " nie mozna usunac wezla ,korzen jest pusty" << endl;
- // return;
- // }
- // while (ptr != nullptr) {
- //
- // if (ptr->get_key() == key_val) {
- //
- // if (ptr->get_ptr_left() == nullptr && ptr->get_ptr_right() == nullptr) {
- // if (par_ptr->get_ptr_left() == ptr) {
- // if (root == ptr) {
- // delete ptr;
- // root = nullptr;
- // }
- // delete ptr;
- // par_ptr->set_ptr_left(nullptr);
- // return;
- // }
- // else {
- // if (root == ptr) {
- // delete ptr;
- // root = nullptr;
- // }
- // delete ptr;
- // par_ptr->set_ptr_right(nullptr);
- // return;
- // }
- // }
- //
- // else if (ptr->get_ptr_left() == nullptr && ptr->get_ptr_right() != nullptr) {
- // if (par_ptr->get_ptr_left() == ptr) {
- //
- // par_ptr->set_ptr_left(ptr->get_ptr_right());
- // delete ptr;
- // return;
- // }
- // else {
- //
- // par_ptr->set_ptr_right(ptr->get_ptr_right());
- // delete ptr;
- // return;
- // }
- // }
- // else if ((ptr->get_ptr_left() != nullptr && ptr->get_ptr_right() == nullptr)) {
- // if (ptr == root) {
- // Element * sup_ptr = ptr->get_ptr_left();
- // delete root;
- // root = sup_ptr;
- // return;
- // }
- // if (par_ptr->get_ptr_left() == ptr) {
- //
- // par_ptr->set_ptr_left(ptr->get_ptr_left());
- // delete ptr;
- // return;
- // }
- // else {
- //
- // par_ptr->set_ptr_right(ptr->get_ptr_left());
- // delete ptr;
- // return;
- // }
- // }
- // else if ((ptr->get_ptr_left() != nullptr && ptr->get_ptr_right() != nullptr)) {
- //
- //
- //
- // Element *succes_ptr = ptr->get_ptr_right();
- // Element * par_succes_ptr = nullptr;
- // while (succes_ptr->get_ptr_left() != nullptr) {
- // par_succes_ptr = succes_ptr;
- // succes_ptr = succes_ptr->get_ptr_left();
- // }
- // if (succes_ptr->get_ptr_right() == nullptr) {
- // if (root == ptr && (ptr->get_ptr_right() == succes_ptr)) {
- //
- // }
- // else {
- // if (par_succes_ptr == nullptr) {
- // succes_ptr->set_ptr_left(ptr->get_ptr_left());
- // }
- // else
- // {
- // par_succes_ptr->set_ptr_left(nullptr);
- // }
- //
- // }
- //
- // }
- // else {
- // if (root == ptr && (ptr->get_ptr_right() == succes_ptr)) {
- //
- // }
- // else
- // {
- // if (par_succes_ptr == nullptr) {
- // succes_ptr->set_ptr_left(ptr->get_ptr_left());
- // }
- // else
- // {
- // par_succes_ptr->set_ptr_left(succes_ptr->get_ptr_right());
- // }
- //
- // }
- //
- // }
- //
- // succes_ptr->set_ptr_left(ptr->get_ptr_left());
- // if (ptr == root && (ptr->get_ptr_right() == succes_ptr)) {
- //
- // }
- // else {
- // if (par_succes_ptr == nullptr)
- // {
- // }
- // else
- // {
- // succes_ptr->set_ptr_right(ptr->get_ptr_right());
- // }
- //
- // }
- // if (ptr == root) {
- // delete root;
- // root = succes_ptr;
- // return;
- // }
- //
- // if (par_ptr->get_ptr_left() == ptr) {
- // par_ptr->set_ptr_left(succes_ptr);
- // delete ptr;
- // return;
- // }
- // else {
- // par_ptr->set_ptr_right(succes_ptr);
- // delete ptr;
- // return;
- // }
- //
- //
- // }
- //
- //
- // }
- // else if (ptr->get_key() > key_val) {
- // par_ptr = ptr;
- // ptr = ptr->get_ptr_left();
- // }
- // else {
- // par_ptr = ptr;
- // ptr = ptr->get_ptr_right();
- // }
- // }
- // cout << "nie mozna usunac wezla poniewaz nie istnieje " << endl;
- // return;
- //}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement