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;

void dodaj(BST **root, int element)
     BST *x=(*root);
     BST *y=NULL;
     BST *nowy = (BST*)malloc(sizeof(BST));
     {    y=x;
          if(x->klucz>element) x=x->lewy;
          else x=x->prawy;
     if(y==NULL) (*root)=nowy;
          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 (")");
     if(root->lewy!=NULL) rysuj(root->lewy);
     if(root->prawy!=NULL) rysuj(root->prawy);

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

void wyswietl(BST *root)
     if (root!=NULL)
     printf("%d ", root->klucz);
     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;
    return min(root->prawy);
         while(y!=NULL && root==y->prawy)
    return y;

BST *poprzednik(BST *root)
    BST *y=NULL;
    return max(root->lewy);
         while(y!=NULL && root==y->lewy)
         {  root=y;
    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)
     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)
     else y->ojciec->prawy=x;

     if (y!=usuwany)

     return y;

int main(int argc, char *argv[])
  BST *root=NULL;
  int opcja=0, k;
     scanf("%d", &opcja);
        case 1:printf("Podaj wartosc: "); scanf("%d", &k); dodaj(&root,k);
        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;
        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 września 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 września 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 marca 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 stycznia 2016 o 11:58 am

    Ensure that your coupons precisely check on see.

  5. 28 marca 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.

  6. 2 stycznia 2017 o 2:13 am

    A lot of thanks for your whole effort on this website.
    Debby enjoys participating in investigation and it’s
    simple to grasp why. All of us know all relating to the
    lively means you convey useful guides on this website and in addition invigorate participation from website
    visitors on that subject matter then our child is understanding a whole lot.
    Enjoy the rest of the new year. You are always
    conducting a glorious job.

  7. 17 grudnia 2017 o 9:11 pm

    Fantastic blog you have here but I was curious about if you knew of any message boards that cover the same topics discussed in this article?
    I’d really like to be a part of community where I can get comments from other experienced individuals that share the same interest.
    If you have any suggestions, please let me know. Thank you!

  1. No trackbacks yet.


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


Komentujesz korzystając z konta Wyloguj /  Zmień )

Zdjęcie na Google+

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

Zdjęcie z Twittera

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

Zdjęcie na Facebooku

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


Connecting to %s

%d blogerów lubi to: