Drzewo BST

Odpowiedz Nowy wątek
2012-12-11 20:07
mba
0

Hej, piszę program drzewa przeszukiwań binarnych i mam mały problem. Wydaje mi się, że w funkcji dodawania jest coś nie tak. Mam dodawać, wypisywać i usuwać rekurencyjnie. Na razie za usuwanie się nie zabieram, póki reszta nie będzie poprawnie działać. Mój kod:

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

struct node
{
 unsigned int value;
 struct node *left, *right;
};

int add(struct node *current, int tValue);
void dopisz(struct node *current);
void usun(struct node *current);
void wyswietl(struct node *current);

int main()
{
    struct node *root = 0;

    int isEnd = FALSE;
    char answer[100];
    while(!isEnd)
    {
        printf("\n\t\tMENU\n");
        printf("[0] - zakonczenie programu\n");
                printf("[1] - dopisanie\n");
                printf("[2] - usuniecie\n");
                printf("[3] - wyswietlenie zawartosci drzewa\n");
        scanf("%s", answer);

                switch(answer[0])
                {
                        case '0':
                                printf("Zakonczenie!\n");
                                isEnd=TRUE;
                                break;
                        case '1':
                                dopisz(root);
                                break;
                        case '2':
                                //usun(root);
                                break;
                        case '3':
                                wyswietl(root);
                                break;
                        default:
                                printf("Bledny wybor...\n");
                }
    }
    return 0;
}

void wyswietl(struct node *current)
{
    if(current)
    {
        wyswietl(current->left);
        printf("%d\n", current->value);
        wyswietl(current->right);
    }

}

void dopisz(struct node *current)
{
    int tValue;
    printf("Wartosc: ");
    scanf("%d", &tValue);
    if(add(current, tValue))
    {
        printf("Dodano!\n");
    }
    else printf("Blad, podany klucz juz istnieje!");
}

int add(struct node *current, int tValue)
{
        if(!current)
        {
            current = (struct node*)malloc(sizeof(struct node));
            current->value = tValue;
            current->left = NULL;
            current->right = NULL;
            return TRUE;
        }
        else if(tValue == current->value)
            return FALSE;
        else if(tValue > current->value)
        {
            add(current->right, tValue);
        }
        else if(tValue < current->value)
        {
            add(current->left, tValue);
        }
}

Pozostało 580 znaków

2012-12-11 20:11
0

o_O a co ta funkcja dodawania niby robi? Gdzie niby podpinasz ten nowy węzeł drzewa? Bo ja tu nic takiego nie widzę. Chyba ze tobie się wydaje że jak masz
current -> right == NULL to jak zrobisz na kopii tego wskaźnik malloc to jakimś cudem nagle zrobi ci się current -> right = nowy obiekt.
Tak nie jest.
Bo wewnątrz funkcji pracujesz na KOPII wskaźnika a nie na jego oryginale. Zmiana tego wskaźnika (current) wewnątrz funkcji NIE WPŁYWA na jego zmianę "wyżej".


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2012-12-11 20:18
mba
0

Czyli muszę przekazywać przez wartość... Jak takie coś miałoby wyglądać? Definicja byłaby wtedy

int add(struct node *&current, int tValue)

?

edytowany 1x, ostatnio: mba, 2012-12-11 20:19

Pozostało 580 znaków

2012-12-11 21:01
0

To zależy od ciebie. Możesz przekazać **, możesz przekazać referencje do wskaźnika tak jak pokazałes, a mozesz też zmienic funkcję tak żeby od razu przypinać jak widzisz że masz iść w prawo/lewo a tam jest null.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2012-12-12 00:17
mba
0

Eh, nie wiem jak to zrobić. Nie używałem nigdy podwójnych , a moja metoda, którą napisałem wcześniej, jest odrzucana przez kompilator. Twojej trzeciej metody nie jestem sobie w stanie wyobrazić.
Jak chcę użyć
, to mam zmieniać jakoś definicje funkcji? Czy wystarczy dopisać gdzieś *? Mam potem problem ze zmodyfikowaniem tych wywołań

add(current->right, tValue);

Nie wiem co tam zmienić, gdzie dać gwiazdkę, co otoczyć nawiasem.

Kompilator ci odrzuci referencje jeśli używasz C a nie C++ ;) - Shalom 2012-12-12 00:43

Pozostało 580 znaków

2012-12-12 00:23
0

add((*current)->right, tValue);


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2012-12-12 00:46
mba
0

Przerobiłem w ten sposób, ale nadal warningi i program się sypie. Jestem przekonany, że źle obsługuję te wskaźniki. Dodałem przy okazji funkcję, która tworzy mi nowy węzeł.

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

struct node
{
 unsigned int value;
 struct node *left, *right;
};

int add(struct node **current, int tValue);
void dopisz(struct node **current);
void usun(struct node *current);
void wyswietl(struct node *current);
struct node* newNode(int tValue);

int main()
{
    struct node *root = 0;

    int isEnd = FALSE;
    char answer[100];
    while(!isEnd)
    {
        printf("\n\t\tMENU\n");
        printf("[0] - zakonczenie programu\n");
                printf("[1] - dopisanie\n");
                printf("[2] - usuniecie\n");
                printf("[3] - wyswietlenie zawartosci drzewa\n");
        scanf("%s", answer);

                switch(answer[0])
                {
                        case '0':
                                printf("Zakonczenie!\n");
                                isEnd=TRUE;
                                break;
                        case '1':
                                dopisz(&root);
                                break;
                        case '2':
                                //usun(root);
                                break;
                        case '3':
                                wyswietl(root);
                                break;
                        default:
                                printf("Bledny wybor...\n");
                }
    }
    return 0;
}

void wyswietl(struct node *current)
{
    if(current)
    {
        wyswietl(current->left);
        printf("%d\n", current->value);
        wyswietl(current->right);
    }

}

void dopisz(struct node **current)
{
    int tValue;
    printf("Wartosc: ");
    scanf("%d", &tValue);
    if(add((*current), tValue))
    {
        printf("Dodano!\n");
    }
    else printf("Blad, podany klucz juz istnieje!");
}

int add(struct node **current, int tValue)
{
        if(!current)
        {
            (*current) = newNode(tValue);
            return TRUE;
        }
        else if(tValue == (*current)->value)
            return FALSE;
        else if(tValue > (*current)->value)
        {
            add((*current)->right, tValue);
        }
        else if(tValue < (*current)->value)
        {
            add((*current)->left, tValue);
        }
        return FALSE;
}

struct node* newNode(int tValue)
{
        struct node *newNode = (struct node*)malloc(sizeof(struct node));
        newNode->value = tValue;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
}

Pozostało 580 znaków

2012-12-12 01:03
0

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

struct node
{
 unsigned int value;
 struct node *left, *right;
};

int add(struct node **current, int tValue);
void dopisz(struct node **current);
void usun(struct node *current);
void wyswietl(struct node *current);
struct node* newNode(int tValue);

int main()
{
    struct node *root = 0;

    int isEnd = FALSE;
        char answer[100];
        while(!isEnd)
        {
                printf("\n\t\tMENU\n");
                printf("[0] - zakonczenie programu\n");
                printf("[1] - dopisanie\n");
                printf("[2] - usuniecie\n");
                printf("[3] - wyswietlenie zawartosci drzewa\n");
                scanf("%s", answer);

                switch(answer[0])
                {
                        case '0':
                                printf("Zakonczenie!\n");
                                isEnd=TRUE;
                                break;
                        case '1':
                                dopisz(&root);
                                break;
                        case '2':
                                //usun(root);
                                break;
                        case '3':
                                wyswietl(root);
                                break;
                        default:
                                printf("Bledny wybor...\n");
                }
        }
        return 0;
}

void wyswietl(struct node *current)
{
    if(current)
    {
        wyswietl(current->left);
        printf("%d\n", current->value);
        wyswietl(current->right);
    }

}

void dopisz(struct node **current)
{
    int tValue;
    printf("Wartosc: ");
    scanf("%d", &tValue);
    if(add(current, tValue))
    {
        printf("Dodano!\n");
    }
    else printf("Blad, podany klucz juz istnieje!");
}

int add(struct node **current, int tValue)
{
        if(!(*current))
        {
            (*current) = newNode(tValue);
            return TRUE;
        }
        else if(tValue == (*current)->value)
            return FALSE;
        else if(tValue > (*current)->value)
        {
            return add(&((*current)->right), tValue);
        }
        else
        {
            return add(&((*current)->left), tValue);
        }
}

struct node* newNode(int tValue)
{
        struct node *newNode = (struct node*)malloc(sizeof(struct node));
        newNode->value = tValue;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
}

a to:
http://cdn.pophangover.com/wp[...]im-doing-dog-construction.jpg
ustaw sobie jako tapetę ;]


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 2x, ostatnio: Shalom, 2012-12-12 09:33

Pozostało 580 znaków

2012-12-12 09:19
mba
0

Zaskoczę Cię, ale tym razem Ty powinieneś to ustawić, link nie działa. :P
Pierwszy raz spotkałem się z takim użyciem wskaźników, więc się pogubiłem, ale dzięki za wyjaśnienie, już zaczynam to łapać. Dokończyłem ten program, wydaje się działać w miarę stabilnie. Teraz mam pytanie, czy napisanie jakiejś funkcji drukującej ładnie to drzewo jest do wykonania? Albo może istnieją już jakieś gotowce w sieci, które polecacie. Bo w sumie nie wiem jak ja miałem ten program napisać, czy ma drukować po prostu te liczby w kolejności inorder, czy ma to być jakaś graficzna reprezentacja. W każdym razie średnio widzę siebie wymyślającego printfy z liczonymi spacjami itp. Kod wygląda teraz tak:

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

struct node
{
 unsigned int value;
 struct node *left, *right;
};

int add(struct node **current, int tValue);
void dopisz(struct node **current);
void usun(struct node **current);
void wyswietl(struct node *current);
struct node* newNode(int tValue);
void Delete(struct node **tree, int  item);
void DeleteNode(struct node **tree);
void GetPredecessor(struct node **tree, int *data);

int main()
{
    struct node *root = 0;

    int isEnd = FALSE;
    char answer[100];
    while(!isEnd)
    {
        printf("\n\t\tMENU\n");
        printf("[0] - zakonczenie programu\n");
                printf("[1] - dopisanie\n");
                printf("[2] - usuniecie\n");
                printf("[3] - wyswietlenie zawartosci drzewa\n");
        scanf("%s", answer);

                switch(answer[0])
                {
                        case '0':
                                printf("Zakonczenie!\n");
                                isEnd=TRUE;
                                break;
                        case '1':
                                dopisz(&root);
                                break;
                        case '2':
                                usun(&root);
                                break;
                        case '3':
                                wyswietl(root);
                                break;
                        default:
                                printf("Bledny wybor...\n");
                }
    }
    return 0;
}

void usun(struct node **current)
{
    int tValue;
    printf("Wartosc: ");
    scanf("%d", &tValue);
    Delete(current, tValue);
}

void wyswietl(struct node *current)
{
    if(current)
    {
        wyswietl(current->left);
        printf("%d\n", current->value);
        wyswietl(current->right);
    }

}

void dopisz(struct node **current)
{
    int tValue;
    printf("Wartosc: ");
    scanf("%d", &tValue);
    if(add(current, tValue))
    {
        printf("Dodano!\n");
    }
    else printf("Blad, podany klucz juz istnieje!");
}

int add(struct node **current, int tValue)
{
    if(!(*current))
    {
        (*current) = newNode(tValue);
        return TRUE;
    }
    else if(tValue == (*current)->value)
        return FALSE;
    else if(tValue > (*current)->value)
    {
        add(&(*current)->right, tValue);
    }
    else if(tValue < (*current)->value)
    {
        add(&(*current)->left, tValue);
    }
}

struct node* newNode(int tValue)
{
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->value = tValue;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void Delete(struct node **tree, int tValue)
{
    if(tValue < (*tree)->value)
        Delete(&(*tree)->left, tValue);
    else if(tValue > (*tree)->value)
        Delete(&(*tree)->right, tValue);
    else
        DeleteNode(&(*tree));
}

void DeleteNode(struct node **tree)
{
    int tValue;
    struct node *tempPtr = (*tree);

    if((*tree)->left == NULL)
    {
        (*tree) = (*tree)->right;
        free(tempPtr);
    }
    else if((*tree)->right == NULL)
    {
        (*tree) = (*tree)->left;
        free(tempPtr);
    }
    else
    {
        GetPredecessor(&(*tree)->left, &tValue);
        (*tree)->value = tValue;
        Delete(&(*tree)->left, tValue);
    }
}

void GetPredecessor(struct node **tree, int *tValue)
{
    while((*tree)->right != NULL)
   (*tree) = (*tree)->right;
    *tValue = (*tree)->value;
}

Pozostało 580 znaków

2012-12-12 09:34
0

Poprawiłem obrazek, żebyś nie płakał :P
Da się wypisać drzewko graficznie, ale wypisanie go inorder/preorder/postorder też powinno wystarczyć ;]


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2012-12-19 00:55
mba
0

Witam. Moje drzewo należało z biegiem czasu rozszerzyć i wziąłem się za to dzisiaj. Po 3 godzinach ma to jakieś ręce i nogi, póki co chyba krzywe. Raz jak testowałem dodając i usuwając dane pojawił mi się wskaźnik do śmiecia. Nie wiem tylko gdzie jest problem, bo sam kod wydaje się dobrze napisany. Nie do końca rozumiem usuwanie.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE 1
#define FALSE 0

struct node
{
 char *word;
 unsigned int arity;
 struct node *left, *right, *parent;
};

// Opakowanie:
void dopisz(struct node *root);
void wyswietl(struct node *current);
void usun(struct node *current);
// Konkrety:
void treeInsert(struct node *current, char *tValue);
void treeDelete(struct node *current);
// Pomoc:
struct node* naj_lewo(struct node *start);
struct node* szukaj(struct node *start, char *tValue);

struct node *root = NULL;

int main()
{

    int isEnd = FALSE;
    char answer[100];
    while(!isEnd)
    {
        printf("\n\t\tMENU\n");
        printf("[0] - zakonczenie programu\n");
                printf("[1] - dopisanie\n");
                printf("[2] - usuniecie\n");
                printf("[3] - wyswietlenie zawartosci drzewa\n");
        scanf("%s", answer);

                switch(answer[0])
                {
                        case '0':
                                printf("Zakonczenie!\n");
                                isEnd=TRUE;
                                break;
                        case '1':
                                dopisz(root);
                                break;
                        case '2':
                                usun(root);
                                break;
                        case '3':
                                wyswietl(root);
                                break;
                        default:
                                printf("Bledny wybor...\n");
                }
    }
    return 0;
}

void usun(struct node *current)
{
    char tValue[20];
    printf("Wyraz: ");
    scanf("%s", tValue);
    treeDelete(szukaj(current,tValue));

}

void wyswietl(struct node *root)
{
    if(root)
    {
        wyswietl(root->left);
        printf("%s\t%d\n", root->word, root->arity);
        wyswietl(root->right);
    }
}

void dopisz(struct node *current)
{
    char tValue[20];
    printf("Wyraz: ");
    scanf("%s", tValue);
    treeInsert(current, tValue);
}

void treeInsert(struct node *current, char *tValue)
{
    //jezeli drzewo jest puste to dodaj korzen
    if (root == NULL)
    {
        root = (struct node*)malloc(sizeof (struct node));
        root->word = strdup(tValue);
        root->arity=1;
        root->left = NULL;
        root->right = NULL;
        root->parent = NULL;
    }
    //jezeli zadana wartosc jest mniejsza od korzenia idz do lewego poddrzewa
    else if(strcmp(tValue, current->word) < 0)
    {
    //jezeli lewe poddrzewo istnieje wywolaj dla niego ta funkcje rekurencyjnie
        if(current->left != NULL)
        {
            treeInsert(current->left, tValue);
        }
        //jezeli lewe poddrzewo nie istnieje dodaj nowy wezel o zadanej wartosci
        else
        {
            struct node *newItem;
            newItem = (struct node*)malloc(sizeof (struct node));
            newItem->word = strdup(tValue);
            newItem->arity=1;
            newItem->left = NULL;
            newItem->right = NULL;
            newItem->parent = current;
            current->left=newItem;
        }
    }
    //jezeli zadana wartosc jest wieksza lub rowna korzeniowi idz do prawego poddrzewa
    else if(strcmp(tValue, current->word) > 0)
    {
        //jezeli prawe poddrzewo istnieje wywolaj dla niego ta funkcje rekurencyjnie
        if(current->right!=NULL)
        {
            treeInsert(current->right, tValue);
        }
        //jezeli prawe poddrzewo nie istnieje dodaj nowy wezel o zadanej wartosci
        else
        {
            struct node *newItem;
            newItem = (struct node*)malloc(sizeof (struct node));
            newItem->word = strdup(tValue);
            newItem->arity=1;
            newItem->left = NULL;
            newItem->right = NULL;
            newItem->parent = current;
            current->right=newItem;
        }
    }
    else
    {
        current->arity++;
    }
}

void treeDelete(struct node *current)
{
    if(current->arity > 1)
    {
        current->arity--;
        return;
    }

    //jezeli wezel nie ma dzieci
    if(current->left==NULL && current->right==NULL)
    {
        //jezeli wezel jest korzeniem
        if(current->parent==NULL)
        {
            root=NULL;
        }
        //jezeli wezel jest po lewej stronie parenta,
        else if(current->parent->left==current)
        {
            //usun wezel z lewej strony wezla parenta
            current->parent->left=NULL;
        }
        else
        {
            //usun wezel z prawej strony wezla parenta
            current->parent->right=NULL;
        }
        free(current);
    }
    //jezeli wezel ma tylko jedno dziecko
    else if(current->left==NULL || current->right==NULL)
    {
        //jezeli po lewej stronie nie ma dziecka
        if(current->left==NULL)
        {
            //jezeli wezel jest korzeniem
            if(current->parent==NULL)
            {
                root=current->right;
            }
            //jezeli wezel jest po lewej stronie parenta
            else if(current->parent->left==current)
            {
                //przyczep z lewej strony parenta wezel bedacy po prawej stronie usuwanego wezla
                current->parent->left=current->right;
            }
            else
            {
                //przyczep z prawej strony parenta wezel bedacy po prawej stronie usuwanego wezla
                current->parent->right=current->right;
            }
        }
        else
        {
            //jezeli wezel jest korzeniem
            if(current->parent==NULL)
            {
                root=current->left;
            }
            //jezeli wezel jest po lewej stronie parenta
            else if(current->parent->left==current)
            {
                //przyczep z lewej strony parenta wezel bedacy po lewej stronie usuwanego wezla
                current->parent->left=current->left;
            }
            else
            {
                //przyczep z prawej strony parenta wezel bedacy po prawej stronie usuwanego wezla
                current->parent->right=current->left;
            }
        }
        free(current);
    }
    else
    {
        //wstaw w miejsce usuwanego elementu - najmniejsza wartosc z prawego poddrzewa
        struct node *temp;
        temp=naj_lewo(current->right);
        //current->wartosc = temp->wartosc;
        strcpy(current->word, temp->word);
        current->arity=temp->arity;
        treeDelete(temp);
    }
}

struct node* naj_lewo(struct node *start)
{
    if(start->left!= NULL)
        return naj_lewo(start->left);
    else
        return start;
}

struct node* szukaj(struct node *start, char *tValue)
{
    //jezeli wezel ma szukana wartosc to odnalezlismy go
    if (strcmp(start->word, tValue)==0)
        return start;
    //jezeli szukana wartosc jest mniejsza to szukamy w lewym poddrzewie o ile istnieje
    else if( strcmp(tValue, start->word) < 0 && start->left != NULL)
        return szukaj(start->left, tValue);
    //jezeli szukana wartosc jest wieksza to szukamy w prawym poddrzewie o ile istnieje
    else if (strcmp(tValue, start->word) > 0 && start->right != NULL)
        return szukaj(start->right, tValue);
    return NULL;
}

Co by tutaj należało poprawić? Potem dodam jeszcze obsługę przypadku, w którym chcemy usunąć coś, co nie istnieje. Na razie to dla mnie mało istotne.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0