daily pastebin goal
23%
SHARE
TWEET

Untitled

a guest Dec 13th, 2018 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<math.h>
  4.  
  5. struct drvo{
  6.     int broj;
  7.     int balans;
  8.     struct drvo *levi, *desni;
  9. };
  10.  
  11. #define novi(x) x=(struct drvo*) malloc(sizeof(struct drvo))
  12.  
  13. int dodaj(struct drvo**,int);
  14. struct drvo* form();
  15. void ispis(struct drvo*);
  16. void lrotacija(struct drvo**);
  17. void drotacija(struct drvo**);
  18. int dubina(struct drvo*);
  19.  
  20. int dodaj(struct drvo **p, int vrednost){
  21.     int inkrement, rezultat;
  22.     struct drvo *t=*p;
  23.     rezultat=0;
  24.     if(t==NULL){
  25.         novi(t);
  26.         t->broj=vrednost;
  27.         t->levi=t->desni=NULL;
  28.         t->balans=0;
  29.         rezultat=1;
  30.     }
  31.     else{
  32.         if(vrednost>t->broj)
  33.             inkrement=dodaj(&(t->desni),vrednost);
  34.         else
  35.             inkrement=-dodaj(&(t->levi),vrednost);
  36.         t->balans+=inkrement;
  37.         if(inkrement!=0 && t->balans!=0){
  38.             if(t->balans<-1){
  39.                 if(t->levi->balans<0)
  40.                     drotacija(&t);
  41.                 else{
  42.                     lrotacija(&(t->levi));
  43.                     drotacija(&t);
  44.                 }
  45.             }
  46.             else if(t->balans>1){
  47.                 if(t->desni->balans>0)
  48.                     lrotacija(&t);
  49.                 else{
  50.                     drotacija(&(t->desni));
  51.                     lrotacija(&t);
  52.                 }
  53.             }
  54.             else
  55.                 rezultat=1;
  56.         }
  57.     }
  58.     *p=t;
  59.     return rezultat;
  60. }
  61.  
  62. struct drvo* form(){
  63.     struct drvo *koren;
  64.     int k;
  65.     koren=NULL;
  66.     scanf("%d",&k);
  67.     while(k) {
  68.         dodaj(&koren,k);
  69.         scanf("%d",&k);
  70.     }
  71.     return koren;
  72. }
  73.  
  74. void ispis(struct drvo *p){
  75.     if (p) {
  76.         ispis(p->levi);
  77.         printf("%5d",p->broj);
  78.         ispis(p->desni);
  79.     }
  80. }
  81.  
  82. int dubina(struct drvo *p){
  83.     int dl=0,dd=0;
  84.     if(p){
  85.         if (p->levi) dl=dubina(p->levi);
  86.         if (p->desni) dd=dubina(p->desni);
  87.         if (dl>dd) return ++dl;
  88.         else return ++dd;
  89.     }
  90.     else return 0;
  91. }
  92.  
  93. void lrotacija(struct drvo **t){
  94.     struct drvo *poml,*pomd;
  95.     int stari_balans;
  96.     poml=*t;
  97.     pomd=poml->desni;
  98.     poml->desni=pomd->levi;
  99.     pomd->levi=poml;
  100.     *t=pomd;
  101.     poml->balans=dubina(poml->desni)-dubina(poml->levi);
  102.     pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
  103. }
  104.  
  105. void drotacija(struct drvo **t){
  106.     struct drvo *poml,*pomd;
  107.     int stari_balans;
  108.     pomd=*t;
  109.     poml=pomd->levi;
  110.     pomd->levi=poml->desni;
  111.     poml->desni=pomd;
  112.     *t=poml;
  113.     poml->balans=dubina(poml->desni)-dubina(poml->levi);
  114.     pomd->balans=dubina(pomd->desni)-dubina(pomd->levi);
  115. }
  116.  
  117. void sredi(struct drvo **p){
  118.     struct drvo *t;
  119.     if(*p){
  120.         t=*p;
  121.         if(t->balans<-1){
  122.             if(t->levi->balans<0)
  123.                 drotacija(&t);
  124.             else{
  125.                 lrotacija(&(t->levi));
  126.                 drotacija(&t);
  127.             }
  128.         }
  129.         else if(t->balans>1){
  130.             if(t->desni->balans>0)
  131.                 lrotacija(&t);
  132.             else{
  133.                 drotacija(&(t->desni));
  134.                 lrotacija(&t);
  135.             }
  136.         }
  137.         *p=t;
  138.     }
  139. }
  140.  
  141. int nadji(struct drvo **p){
  142.     struct drvo *pom,*pom1;
  143.     int rez;
  144.     pom=*p;
  145.     if(!pom->levi){
  146.         rez=pom->broj;
  147.         pom=pom->desni;
  148.     }
  149.     else
  150.         rez=nadji(&(pom->levi));
  151.     if(pom){
  152.         pom->balans=dubina(pom->desni)-dubina(pom->levi);
  153.         sredi(&pom);
  154.     }
  155.     *p=pom;
  156.     return rez;
  157. }
  158.  
  159. struct drvo* obrisi_b(struct drvo *p, int k){
  160.     struct drvo *pom;
  161.     if(!p) return NULL;
  162.     if(p->broj==k){
  163.         if((!p->levi) && (!p->desni)){
  164.             free(p);
  165.             return NULL;
  166.         }
  167.         if((!p->levi) && (p->desni)){
  168.             pom=p->desni;
  169.             free(p);
  170.             return pom;
  171.         }
  172.         if((p->levi) && (!p->desni)){
  173.             pom=p->levi;
  174.             free(p);
  175.             return pom;
  176.         }
  177.         if((p->levi) && (p->desni)){
  178.             p->broj=nadji(&(p->desni));
  179.             p->balans=dubina(p->desni)-dubina(p->levi);
  180.             sredi(&p);
  181.             return p;
  182.         }
  183.     }
  184.     if(k<p->broj){
  185.         p->levi=obrisi_b(p->levi,k);
  186.         p->balans=dubina(p->desni)-dubina(p->levi);
  187.         sredi(&p);
  188.         return p;
  189.     }
  190.     else{
  191.         p->desni=obrisi_p(p->desni,k);
  192.         p->balans=dubina(p->desni)-dubina(p->levi);
  193.         sredi(&p);
  194.         return p;
  195.     }
  196. }
  197.  
  198. int main(){
  199.     struct drvo *p,*q;
  200.     p=form();
  201.     ispis(p);
  202.     printf("\n");
  203.     printf("Dubina je %d\n",dubina(p));
  204.    
  205.     return 0;
  206. }
RAW Paste Data
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
 
Top