Strona główna > Drzewa > Drzewo poszukiwań binarnych BST

Drzewo poszukiwań binarnych BST

//BST implementacja w C
#include <stdio.h>
#include <stdlib.h>

typedef struct BST
{    
    int klucz;
    struct BST *ojciec;
    struct BST *prawy;
    struct BST *lewy;
}BST;

void dodaj(BST **root, int element)
{
     BST *x=(*root);
     BST *y=NULL;
     BST *nowy = (BST*)malloc(sizeof(BST));
     nowy->klucz=element;
     nowy->lewy=nowy->prawy=nowy->ojciec=NULL;
     while(x!=NULL)
     {    y=x;
          if(x->klucz>element) x=x->lewy;
          else x=x->prawy;
     }
     nowy->ojciec=y;    
     if(y==NULL) (*root)=nowy;
     else{
          if (y->klucz>nowy->klucz) y->lewy=nowy;
          else y->prawy=nowy;
          }
}

BST *min(BST *root)
{
    while(root->lewy!=NULL)  root=root->lewy;
    return root;
}

BST *max(BST *root)
{
    while(root->prawy!=NULL)  root=root->prawy;
    return root;
}

void rysuj(BST *root)
{
     if (root!= NULL) {
     printf ("%-7d" , root ->klucz);
     if (root->lewy==NULL&&root->prawy == NULL );
     else {
     printf ("(" );
     if(root->lewy!= NULL) printf("%d  ,", root->lewy->klucz); else
     printf(" _ ");
     if(root->prawy!= NULL) printf("% d", root->prawy->klucz); else printf
     (" _ ");
     printf (")");
     }
     printf("\n");
     }
     if(root->lewy!=NULL) rysuj(root->lewy);
     if(root->prawy!=NULL) rysuj(root->prawy);
}

void inorder(BST *root)
{ //(lewy syn, ojciec, prawy syn)
     if(root!=NULL){
     inorder(root->lewy);
     printf("%d ", root->klucz);
     inorder(root->prawy);
     }
}

void wyswietl(BST *root)
{
     if (root!=NULL)
     printf("%d ", root->klucz);
     else
     printf("Brak elem!");
}

BST *szukaj(BST *root, int wartosc)
{
     while(root!=NULL && root->klucz!=wartosc)
     {
          if (wartosc<root->klucz) root=root->lewy;
          else root=root->prawy;
     }
     return root;
}

BST *nastepnik(BST *root)
{
    BST *y=NULL;
    if(root->prawy!=NULL)
    return min(root->prawy);
    else{
         y=root->ojciec;
         while(y!=NULL && root==y->prawy)
         {
            root=y;
            y=y->ojciec;
         }
    return y;
    }   
}

BST *poprzednik(BST *root)
{
    BST *y=NULL;
    if(root->lewy!=NULL)
    return max(root->lewy);
    else{
         y=root->ojciec;
         while(y!=NULL && root==y->lewy)
         {  root=y;
            y=y->ojciec;
         }
    return y;
    }
}

BST *usun(BST *root, int element)
{
     BST *x=root;
     BST *y;
     BST *usuwany=szukaj(root,element);

     if(usuwany==NULL) return y;

     if(usuwany->lewy==NULL || usuwany->prawy==NULL)
     y=usuwany;
     else y=nastepnik(usuwany);

     if (y->lewy!=NULL) x=y->lewy;
     else x=y->prawy;

     if(x!=NULL) x->ojciec=y->ojciec;

     if(y->ojciec==NULL) root=x;
     else if(y==y->ojciec->lewy)
     y->ojciec->lewy=x;
     else y->ojciec->prawy=x;

     if (y!=usuwany)
     usuwany->klucz=y->klucz;

     return y;
}

int main(int argc, char *argv[])
{
  BST *root=NULL;
  int opcja=0, k;
  while(opcja!=9)
  {
     printf("\n1Dodaj\t2Wyswietl\t3Min\t4Max\t5Nast\t6Poprz\t7Rysuj\t8Usun\t9Koniec\n");
     scanf("%d", &opcja);
     switch(opcja)
     {
        case 1:printf("Podaj wartosc: "); scanf("%d", &k); dodaj(&root,k);
        break;
        case 2:printf("Metoda inorder:\n");inorder(root); break;
        case 3:printf("Min:  ");wyswietl(min(root)); break;
        case 4:printf("Max:  ");wyswietl(max(root)); break;
        case 5:printf("Podaj wartosc: ");scanf("%d", &k);
        printf("Nastepnik: ");wyswietl(nastepnik(szukaj(root,k))); break;
        case 6:printf("Podaj wartosc: ");scanf("%d", &k);
        printf("Poprzednik: ");wyswietl(poprzednik(szukaj(root,k))); break;
        break;
        case 7:printf("Ojciec|Lewy|Prawy\n"); rysuj(root); break;
        case 8:printf("Podaj wartosc do usuniecia:");scanf("%d",
        &k);usun(root,k); break;
        case 9:opcja=9; break;
     }
  }
  return 0;
}
  1. 17 Wrzesień 2013 o 7:33 am

    This is a very good tip particularly to those new to the blogosphere.
    Short but very accurate information… Thank you for sharing this one.
    A must read post!

  2. 17 Wrzesień 2013 o 6:27 pm

    Great site. Plenty of useful info here. I’m sending it
    to some buddies ans additionally sharing in delicious.
    And of course, thank you to your effort!

  3. 1 Marzec 2014 o 1:35 am

    I really like what you guys are up too. This type of clever work and
    exposure! Keep up the great works guys I’ve included you guys to blogroll.

  4. 31 Styczeń 2016 o 11:58 am

    Ensure that your coupons precisely check on see.

  5. 28 Marzec 2016 o 4:55 am

    After looking at a number of the articles on your site, I honestly appreciate your way of blogging.
    I saved it to my bookmark website list and will
    be checking back in the near future. Take a look at my web site too and tell me your opinion.

  1. No trackbacks yet.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d bloggers like this: