API tools faq
paste
Advertisement
Gilgamesh858

file.cpp

Gilgamesh858
Jun 22nd, 2015
242
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 15.24 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. template <class H> class MultiBST{
  6.     public:
  7.         virtual MultiBST<H>* ins(H x) = 0;
  8.         virtual int search(H x) = 0;
  9.         virtual void inorder() = 0;
  10.         virtual MultiBST<H>* del(H x) = 0;
  11. };
  12.  
  13. template <typename H> class Node{
  14.     private:
  15.         H key;
  16.         int mul;
  17.         Node<H> *parent, *left, *right;
  18.     public:
  19.         Node(H x){
  20.             key = x;
  21.             mul = 1;
  22.             parent = left = right = NULL;
  23.         }
  24.         Node(const Node<H>& copy){
  25.             key = copy.key;
  26.             mul = copy.mul;
  27.             parent = copy.parent;
  28.             left = copy.left;
  29.             right = copy.right;
  30.         }
  31.         H getKey() { return key; }
  32.         int getMul() { return mul; }
  33.         Node<H>* getParent() { return parent; }
  34.         Node<H>* getLeft() { return left; }
  35.         Node<H>* getRight() { return right; }
  36.         void setKey(H x){ key = x; }
  37.         void setParent(Node<H> *par){ parent = par; }
  38.         void setLeft(Node<H> *lef){ left = lef; }
  39.         void setRight(Node<H> *rig){ right = rig; }
  40.         void setMul(int mul) { this->mul = mul; }
  41.         void incMul(){ mul++; }
  42.         void decMul(){ mul--; }
  43.         int isLeaf() {
  44.             if( left == NULL && right == NULL)
  45.                 return 1;
  46.             return 0;
  47.         }
  48.         int onlyOneSon(){
  49.             if(left!=NULL && right==NULL)
  50.                 return 1;
  51.             else if(left==NULL && right!=NULL)
  52.                 return 2;
  53.             return 0;
  54.         }
  55. };
  56.  
  57. template <typename H> class MyMultiBST: public MultiBST<H>{
  58.     private:
  59.         Node<H> *root;
  60.     public:
  61.         MyMultiBST(){ root = NULL; }
  62.         int isEmpty(){
  63.             if(root==NULL)
  64.                 return 1;
  65.             return 0;
  66.         }
  67.         void _ins(Node<H> *aux, Node<H> *par, H x){
  68.             if(aux!=NULL && aux->getKey() == x){
  69.                 aux->incMul();
  70.                 return;
  71.             }
  72.             if(aux==NULL){
  73.                 Node<H> *temp = new Node<H>(x);
  74.                 if(par==NULL){
  75.                     root = temp;
  76.                     //return;
  77.                 }
  78.                 if( x < par->getKey() ){
  79.                     par->setLeft(temp);
  80.                     temp->setParent(par);
  81.                     return;
  82.                 }
  83.                 else{
  84.                     par->setRight(temp);
  85.                     temp->setParent(par);
  86.                     return;
  87.                 }
  88.             }
  89.             par = aux;
  90.             if( x < aux->getKey() )
  91.                 aux = aux->getLeft();
  92.             else
  93.                 aux = aux->getRight();
  94.             _ins(aux, par, x);
  95.         }
  96.         MultiBST<H>* ins(H x){
  97.             _ins(root, NULL, x);
  98.             return this;
  99.         }
  100.         int multiplicity(H x){
  101.             if(search(x))
  102.                 return _search(root, x)->getMul();
  103.             return 0;
  104.         }
  105.         void getMin(){
  106.             if(isEmpty())
  107.                 return;
  108.             cout << _getMin(root)->getKey() << endl;
  109.         }
  110.         Node<H> *_getMin(Node<H> *aux){
  111.             if(aux->getLeft()==NULL)
  112.                 return aux;
  113.             return _getMin(aux->getLeft());
  114.         }
  115.         Node<H> *getNext(Node<H> *aux){
  116.             if(aux->getRight()!=NULL)
  117.                 return _getMin(aux->getRight());
  118.             while(aux->getParent()->getKey() <= aux->getKey())
  119.                 aux = aux->getParent();
  120.             return aux->getParent();
  121.         }
  122.         void _del(Node<H> *temp){
  123.             if(temp->isLeaf()){
  124.                 if(temp==root){
  125.                     root=NULL;
  126.                     return;
  127.                 }
  128.                 if(temp->getParent()->getLeft()==temp){
  129.                     temp->getParent()->setLeft(NULL);
  130.                     delete(temp);
  131.                     return;
  132.                 }
  133.                 temp->getParent()->setRight(NULL);
  134.                 delete(temp);
  135.                 return;
  136.             }
  137.             if(temp->onlyOneSon()==1){
  138.                 if(temp==root){
  139.                     root = temp->getLeft();
  140.                     root->setParent(NULL);
  141.                     delete(temp);
  142.                     return;
  143.                 }
  144.                 temp->getParent()->setLeft(temp->getLeft());
  145.                 temp->getLeft()->setParent(temp->getParent());
  146.                 delete(temp);
  147.                 return;
  148.             }
  149.             if(temp->onlyOneSon()==2){
  150.                 if(temp==root){
  151.                     root = temp->getRight();
  152.                     root->setParent(NULL);
  153.                     delete(temp);
  154.                     return;
  155.                 }
  156.                 temp->getParent()->setRight(temp->getRight());
  157.                 temp->getRight()->setParent(temp->getParent());
  158.                 delete(temp);
  159.                 return;
  160.             }
  161.             Node<H> *next = getNext(temp);
  162.  
  163.             Node<H> dest = *temp;
  164.             temp->setKey(next->getKey());
  165.             temp->setMul(next->getMul());
  166.             next->setKey(dest.getKey());
  167.             next->setMul(dest.getMul());
  168.             _del(next);
  169.         }
  170.         MultiBST<H>* del(H x){
  171.             if(!search(x))
  172.                 return this;
  173.             Node<H> *node = _search(root, x);
  174.             if(node->getMul() > 1){
  175.                 node->decMul();
  176.                 return this;
  177.             }
  178.             _del(node);
  179.             return this;
  180.         }
  181.         Node<H>* _search(Node<H> *aux, H x){
  182.             if(aux==NULL)
  183.                 return NULL;
  184.             if(aux->getKey() == x)
  185.                 return aux;
  186.             if(aux->getKey() > x)
  187.                 return _search(aux->getLeft(), x);
  188.             return _search(aux->getRight(), x);
  189.         }
  190.         int search(H x){
  191.             if(_search(root, x) != NULL)
  192.                 return 1;
  193.             return 0;
  194.         }
  195.         void _inorder(Node<H> *aux){
  196.             if(aux==NULL)
  197.                 return;
  198.             _inorder(aux->getLeft());
  199.             for(int i=0; i < aux->getMul(); i++) cout << aux->getKey() << " ";
  200.             _inorder(aux->getRight());
  201.         }
  202.         void _postorder(Node<H> *aux){
  203.             if(aux==NULL)
  204.                 return;
  205.             _postorder(aux->getLeft());
  206.             _postorder(aux->getRight());
  207.             for(int i=0; i < aux->getMul(); i++) cout << aux->getKey() << " ";
  208.         }
  209.         void _preorder(Node<H> *aux){
  210.             if(aux==NULL)
  211.                 return;
  212.             _preorder(aux->getLeft());
  213.             _preorder(aux->getRight());
  214.             for(int i=0; i < aux->getMul(); i++) cout << aux->getKey() << " ";
  215.         }
  216.         void inorder(){
  217.             _inorder(root);
  218.             cout << endl;
  219.         }
  220.         void postorder(){
  221.             _postorder(root);
  222.             cout << endl;
  223.         }
  224.         void preorder(){
  225.             _preorder(root);
  226.             cout << endl;
  227.         }
  228. };
  229. int main()
  230. {
  231.     MyMultiBST<int> *T = new MyMultiBST<int>();
  232.     //T->ins(10)->ins(5)->ins(2)->ins(7)->ins(17)->ins(12)->ins(3)->ins(15);
  233.     T->ins(10)->ins(7)->ins(7)->ins(23)->ins(30)->ins(4)->ins(1)->ins(5)->ins(9)->ins(5)->ins(1)->ins(7)->ins(1)->ins(9);
  234.     T->inorder();
  235.     T->getMin();
  236.     T->del(7)->del(4)->del(23)->del(7);
  237.     T->inorder();
  238.     return 0;
  239. }
  240.  
  241. #include <iostream>
  242.  
  243. using namespace std;
  244.  
  245. template <typename H> class Node{
  246.     private:
  247.         H key;
  248.         Node<H> *parent, *left, *right;
  249.     public:
  250.         Node(H key){
  251.         this->key = key;
  252.         parent = left = right = NULL;
  253.         }
  254.         H getKey(){ return key; }
  255.         Node<H>* getParent(){ return parent; }
  256.         Node<H>* getLeft(){ return left; }
  257.         Node<H>* getRight(){ return right; }
  258.         void setParent(Node<H>* parent){ this->parent = parent; }
  259.         void setLeft(Node<H>* left){ this->left = left; }
  260.         void setRight(Node<H>* right){ this->right = right; }
  261.         void setKey(H key) { this->key = key; }
  262.         bool isLeaf(){
  263.             if(left==NULL && right==NULL)
  264.                 return 1;
  265.             return 0;
  266.         }
  267. };
  268.  
  269. template <typename H> class Tree{
  270.     private:
  271.         Node<H>* root;
  272.     public:
  273.         Tree(){ root = NULL; }
  274.         Node<H>* getRoot() { return root; }
  275.         bool isEmpty(){
  276.             if(root==NULL)
  277.                 return 1;
  278.             return 0;
  279.         }
  280.         Tree<H>* ins(H x){
  281.             Node<H>* temp = new Node<H>(x);
  282.             if(root==NULL){
  283.                 root = temp;
  284.                 return this;
  285.             }
  286.  
  287.             Node<H>* t = root;
  288.             Node<H>* p = NULL;
  289.             while(t){
  290.                 p = t;
  291.                 if( t->getKey() > x ) t = t->getLeft();
  292.                 else t = t->getRight();
  293.             }
  294.             if( p->getKey() > x ){
  295.               p->setLeft(temp);
  296.               temp->setParent(p);
  297.               return this;
  298.             }
  299.             p->setRight(temp);
  300.             temp->setParent(p);
  301.             return this;
  302.         /*METODO NOSTRO
  303.             Node<H>* temp = new Node<H>(x);
  304.             if(isEmpty()){
  305.                 root = temp;
  306.                 return this;
  307.             }
  308.             Node<H>* n = root;
  309.             while(1){
  310.                 if(n->isLeaf()){
  311.                     if(temp->getKey() < n->getKey()){
  312.                         n->setLeft(temp);
  313.                         temp->setParent(n);
  314.                         return this;
  315.                     }
  316.                     n->setRight(temp);
  317.                     temp->setParent(n);
  318.                     return this;
  319.                 }
  320.                 if(temp->getKey() < n->getKey()){
  321.                     if(!n->getLeft()){
  322.                         n->setLeft(temp);
  323.                         temp->setParent(n);
  324.                         return this;
  325.                     }
  326.                     n = n->getLeft();
  327.                 }
  328.                 else{
  329.                     if(!n->getRight()){
  330.                         n->setRight(temp);
  331.                         temp->setParent(n);
  332.                         return this;
  333.                     }
  334.                     n = n->getRight();
  335.                 }
  336.             }*/
  337.         }
  338.         Node<H>* getNext(Node<H> *x){
  339.             if(getMax(root)->getKey() == x->getKey()) return NULL;
  340.             if(x->getRight()) return getMin(x->getRight());
  341.             while(x->getParent()->getKey() <= x->getKey()) x=x->getParent();
  342.             return x->getParent();
  343.         }
  344.         void del(H x){
  345.             if(!search(x)){
  346.                 cout << "Elemento inesistente" << endl;
  347.                 return;
  348.             }
  349.             Node<H> *temp = _search(x);
  350.             if(temp->isLeaf()){
  351.                 Node<H> *par = temp->getParent();
  352.                 if(!par){
  353.                     root = NULL;
  354.                     delete(temp);
  355.                     return;
  356.                 }
  357.                 if(par->getLeft() == temp){
  358.                     par->setLeft(NULL);
  359.                     delete(temp);
  360.                     return;
  361.                 }
  362.                 par->setRight(NULL);
  363.                 delete(temp);
  364.                 return;
  365.             }
  366.             if(!(temp->getLeft() && temp->getRight())){         //#1
  367.                 if(temp->getLeft()){                            //#2
  368.                     if(temp->getParent()->getLeft() == temp){   //#3
  369.                         temp->getParent()->setLeft(temp->getLeft());
  370.                         temp->getLeft()->setParent(temp->getParent());
  371.                         delete(temp);
  372.                         return;
  373.                     }                                           //!#3
  374.                     if(temp->getParent()->getRight() == temp){  //#3
  375.                         temp->getParent()->setRight(temp->getLeft());
  376.                         temp->getLeft()->setParent(temp->getParent());
  377.                         delete(temp);
  378.                         return;
  379.                     }                                           //!#3
  380.                 }                                               //!#2
  381.                 if(temp->getParent()->getLeft() == temp){       //#2
  382.                         temp->getParent()->setLeft(temp->getRight());
  383.                         temp->getRight()->setParent(temp->getParent());
  384.                         delete(temp);
  385.                         return;
  386.                 }                                               //!#2
  387.                 temp->getParent()->setRight(temp->getRight());
  388.                 temp->getRight()->setParent(temp->getParent());
  389.                 delete(temp);
  390.                 return;
  391.             }                                                   //!#1
  392.             Node<H> *sup = getNext(temp);
  393.             H p = sup->getKey();
  394.             sup->setKey(temp->getKey());
  395.             temp->setKey(p);
  396.             del(sup->getKey());
  397.             return;
  398.         }
  399.         int search(H x){
  400.             if(_search(x)) return 1;
  401.             return 0;
  402.         }
  403.         Node<H>* _search(H x){
  404.             if(isEmpty())
  405.                 return NULL;
  406.             Node<H> *temp = root;
  407.             while(temp!=NULL){
  408.                 if(temp->getKey() == x) return temp;
  409.                 if(temp->getKey()>x)
  410.                     temp = temp->getLeft();
  411.                 else temp = temp->getRight();
  412.             }
  413.             return NULL;
  414.         }
  415.         Node<H>* getMin(Node<H>* r){
  416.             if( r == NULL ) return NULL;
  417.             while(r->getLeft()) r = r->getLeft();
  418.             cout << r->getKey();
  419.             return r;
  420.         }
  421.         Node<H>* getMax(Node<H>* r){
  422.             if( r == NULL ) return NULL;
  423.             while(r->getRight()) r = r->getRight();
  424.             cout << r->getKey();
  425.             return r;
  426.         }
  427.         void rec_inorder(Node<H>* r){
  428.             if(!r) return;
  429.             rec_inorder(r->getLeft());
  430.             cout << r->getKey() << " ";
  431.             rec_inorder(r->getRight());
  432.         }
  433.         void rec_postorder(Node<H>* r){
  434.             if(!r) return;
  435.             rec_inorder(r->getLeft());
  436.             rec_inorder(r->getRight());
  437.             cout << r->getKey() << " ";
  438.         }
  439.         void rec_preorder(Node<H>* r){
  440.             if(!r) return;
  441.             cout << r->getKey() << " ";
  442.             rec_inorder(r->getLeft());
  443.             rec_inorder(r->getRight());
  444.         }
  445. };
  446.  
  447. int main(){
  448.     Tree<int> *T = new Tree<int>();
  449.     T->ins(5)->ins(56)->ins(67);//->ins(2)->ins(20)->ins(1)->ins(4)->ins(6)->ins(7)->ins(8)->ins(9)->ins(10);
  450.     T->rec_inorder(T->getRoot()); cout << endl ;
  451.     T->rec_postorder(T->getRoot()); cout << endl ;
  452.     T->rec_preorder(T->getRoot()); cout << endl ;
  453.     cout << endl << "Massimo " ;
  454.     T->getMax(T->getRoot());
  455.     cout << endl << "Minimo " ;
  456.     T->getMin(T->getRoot());
  457.     cout << endl ;
  458.     T->del(5);
  459.     T->rec_inorder(T->getRoot()); cout << endl ;
  460.     /*T->del(4);
  461.     T->rec_inorder(T->getRoot()); cout << endl ;
  462.     T->del(6);
  463.     T->rec_inorder(T->getRoot()); cout << endl ;
  464.     T->del(5);
  465.     T->rec_inorder(T->getRoot()); cout << endl ;
  466.     /*T->del(1);
  467.     T->rec_inorder(T->getRoot()); cout << endl ;
  468.     T->del(10);
  469.     T->rec_inorder(T->getRoot()); cout << endl ;
  470.     T->del(5);
  471.     T->rec_inorder(T->getRoot()); cout << endl ;*/
  472.  return 0;
  473. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!