Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct drzewoBST
- {
- drzewoBST * up;
- drzewoBST * left;
- drzewoBST * right;
- int val;
- };
- void addBstNode(drzewoBST *&root, int x,drzewoBST * wezel2)
- {
- if(root== nullptr)
- {
- auto *w=new drzewoBST();
- w->left= nullptr;
- w->right= nullptr;
- w->up=wezel2;
- w->val=x;
- root=w;
- } else
- {
- if(x>=root->val)
- {
- addBstNode(root->right,x,root);
- }else
- addBstNode(root->left,x,root);
- }
- }
- void addBstNode(drzewoBST *&root, int x)
- {
- if(root== nullptr)
- {
- auto *w=new drzewoBST();
- w->left= nullptr;
- w->right= nullptr;
- w->val=x;
- root=w;
- } else
- {
- if(x>=root->val)
- {
- addBstNode(root->right,x,root);
- }else
- addBstNode(root->left,x,root);
- }
- }
- void addBstNodeWithRememberUp(drzewoBST *&root, int x)
- {
- if(root== nullptr)
- {
- auto *w=new drzewoBST();
- w->left= nullptr;
- w->right= nullptr;
- w->val=x;
- root=w;
- } else
- if(x>=root->val&&root->right== nullptr)
- {
- auto *w=new drzewoBST();
- w->left= nullptr;
- w->right= nullptr;
- w->up=root;
- w->val=x;
- root->right=w;
- }
- else
- if(x<root->val&&root->left== nullptr)
- {
- auto *w=new drzewoBST();
- w->left= nullptr;
- w->right= nullptr;
- w->up=root;
- w->val=x;
- root->left=w;
- }
- else{
- if(x>=root->val)
- {
- addBstNodeWithRememberUp(root->right,x);
- }else
- addBstNodeWithRememberUp(root->left,x);
- }
- }
- drzewoBST* znajdzMin(drzewoBST *root)
- {
- if(root!= nullptr)
- {
- if(root->left!= nullptr)
- znajdzMin(root->left);
- else return root;
- }
- }
- drzewoBST* znajdzMax(drzewoBST *root)
- {
- if(root!= nullptr)
- {
- if(root->right!= nullptr)
- znajdzMax(root->right);
- else return root;
- }
- }
- //drzewoBST* zdnajdzMaxWPodGalezi(drzewoBST *root,int aktualneMaksimum)
- //{
- // if(root!= nullptr)
- // {
- // if(root->val>aktualneMaksimum){
- // aktualneMaksimum=root->val;
- //
- // }
- // }
- //}
- drzewoBST * nastepnik (drzewoBST *wezel)
- {
- drzewoBST * r;
- if(wezel)
- {
- if(wezel->right) return znajdzMin(wezel->right);
- else {
- r= wezel->up;
- while(r && (wezel==r->right))
- {
- wezel=r;
- r=r->up;
- }
- return r;
- }
- }
- return nullptr;
- }
- drzewoBST * poprzednik (drzewoBST *wezel)
- {
- drzewoBST *r;
- if(wezel)
- {
- if(wezel->left) return znajdzMin(wezel->left);
- else
- {
- r=wezel->up;
- while(r&&(wezel==r->left))
- {
- wezel=r;
- r=r->up;
- }
- return r;
- }
- }return nullptr;
- }
- drzewoBST* szukaj(drzewoBST *root,int wartoscSzukana)
- {
- if(root!= nullptr)
- {
- if(root->val==wartoscSzukana)
- {
- return root;
- }
- if(wartoscSzukana>root->val)
- {
- szukaj(root->right,wartoscSzukana);
- }else szukaj(root->left,wartoscSzukana);
- return nullptr;
- }
- }
- //funkcja usuwająca liście tego drzewa
- void usunTo(drzewoBST *&root)
- {
- delete root;
- root= nullptr;
- }
- void usunLiscie (drzewoBST *&root) // gdzieś się wykrzacza funkcja przy wypisywaniu
- {
- if(root!= nullptr)
- {
- if(root->left== nullptr&&root->right== nullptr)//gdy nie ma możliwości zejścia w dół
- {
- usunTo(root);
- }else
- {
- if(root->left!= nullptr)
- {
- usunLiscie(root->left);
- }
- if(root->right!= nullptr)
- {
- usunLiscie(root->right);
- }
- }
- }
- }
- //inorder ( wyświetlanie )
- void inorder(drzewoBST *&root)
- {
- if(root!= nullptr)
- {
- inorder(root->left);
- cout<<root->val<<" ";
- inorder(root->right);
- }else
- return;
- }
- void usunElement(drzewoBST *&wierzcholek)// nie dokończona
- {
- if(wierzcholek->left== nullptr&&wierzcholek->right == nullptr) // To jest wtedy liść
- {
- delete wierzcholek;
- }else if(wierzcholek->left&&wierzcholek->right)
- {
- drzewoBST * minimumZPrawejGalezi= znajdzMin(wierzcholek->right);
- if(minimumZPrawejGalezi->right)
- {
- drzewoBST * gora=minimumZPrawejGalezi->up;
- }
- } else
- if(wierzcholek->left!= nullptr || wierzcholek -> right== nullptr)
- {
- drzewoBST *gora=wierzcholek->up;
- if(gora->left==wierzcholek)
- {
- gora->left=wierzcholek->left;
- wierzcholek->up=gora;
- delete wierzcholek;
- } else
- if(gora->right==wierzcholek)
- {
- gora->right=wierzcholek->right;
- wierzcholek->up=gora;
- delete wierzcholek;
- }
- }
- }
- void rotacjaWLewo(drzewoBST *&root,drzewoBST *&zamieniany)
- {
- drzewoBST * b,* parent;
- b=zamieniany->left;
- if(b== nullptr)
- {
- return;
- }
- parent=zamieniany->up;
- zamieniany->left=b->right;
- if(zamieniany!= nullptr)
- {
- zamieniany->left->up=zamieniany;
- }
- b->right=zamieniany;
- b->up=parent;
- zamieniany->up=b;
- if(parent== nullptr)
- {
- root=b;
- return;
- }
- if(parent->left==zamieniany)
- {
- parent->left=b;
- }else parent->right=b;
- }
- int main() {
- drzewoBST * drzewo=nullptr;
- addBstNode(drzewo,12);
- addBstNode(drzewo,16);
- addBstNode(drzewo,25);
- addBstNode(drzewo,14);
- addBstNode(drzewo,3);
- addBstNode(drzewo,8);
- addBstNode(drzewo,22);
- addBstNode(drzewo,16);
- addBstNode(drzewo,10);
- addBstNode(drzewo,27);
- drzewoBST * drzewo2=nullptr;
- addBstNode(drzewo2,12);
- addBstNode(drzewo2,6);
- addBstNode(drzewo2,-5);
- addBstNode(drzewo2,11);
- addBstNode(drzewo2,3);
- addBstNode(drzewo2,8);
- addBstNode(drzewo2,22);
- addBstNode(drzewo2,16);
- addBstNode(drzewo2,10);
- addBstNode(drzewo2,27);
- inorder(drzewo);
- cout<<endl;
- usunLiscie(drzewo);
- inorder(drzewo);
- cout<<endl;
- usunLiscie(drzewo2);
- inorder(drzewo2);
- cout<<endl;
- drzewoBST * nowe=nullptr;
- addBstNodeWithRememberUp(nowe,12);
- addBstNodeWithRememberUp(nowe,16);
- addBstNodeWithRememberUp(nowe,25);
- addBstNodeWithRememberUp(nowe,14);
- addBstNodeWithRememberUp(nowe,3);
- addBstNodeWithRememberUp(nowe,8);
- addBstNodeWithRememberUp(nowe,22);
- addBstNodeWithRememberUp(nowe,16);
- addBstNodeWithRememberUp(nowe,10);
- addBstNodeWithRememberUp(nowe,27);
- inorder(nowe);
- cout<<endl<<znajdzMin(nowe)->val<<endl<<znajdzMax(nowe)->val<<endl;
- /// TESTOWANIE POPRZEDNIKA I NASTĘPNIKA
- drzewoBST *drzewoBst= nullptr;
- addBstNodeWithRememberUp(drzewoBst,15);
- addBstNodeWithRememberUp(drzewoBst,6);
- addBstNodeWithRememberUp(drzewoBst,22);
- addBstNodeWithRememberUp(drzewoBst,-5);
- addBstNodeWithRememberUp(drzewoBst,14);
- addBstNodeWithRememberUp(drzewoBst,8);
- addBstNodeWithRememberUp(drzewoBst,12);
- addBstNodeWithRememberUp(drzewoBst,13);
- addBstNodeWithRememberUp(drzewoBst,18);
- addBstNodeWithRememberUp(drzewoBst,27);
- addBstNodeWithRememberUp(drzewoBst,17);
- inorder(drzewoBst);
- cout<<endl;
- cout<<drzewoBst->left->right->left->right->right->val<<endl;
- cout<<poprzednik(drzewoBst->left->right->left->right->right)->val<<endl;//ok
- cout<<drzewoBst->right->left->left->val<<endl;
- cout<<poprzednik(drzewoBst->right->left->left)->val<<endl;//ok
- cout<<poprzednik(drzewoBst)->val<<endl;
- cout<<nastepnik(drzewoBst)->val<<endl;
- cout<<nastepnik(drzewoBst->right->right);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement