Drzewo BST

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);
        }
}
 
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".

0

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

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

?

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.

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.

0

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

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;
}
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-content/uploads/2012/10/i-have-no-idea-what-im-doing-dog-construction.jpg
ustaw sobie jako tapetę ;]

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;
}

0

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

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.

0
struct node* szukaj(struct node *start, char *tValue) // z tym że tak jak  u ciebie wywali się, jeżeli próbujesz coś usunąć kiedy drzewo jest puste
  {
   int v=strcmp(start->word, tValue); // tylko raz wywołujemy strcmp a nie max trzy razy (średnio 2 razy) - jak u ciebie.
   if(v<0) return start->left?szukaj(start->left, tValue):NULL;
   if(v>0) return start->right?szukaj(start->right, tValue):NULL;
   return start;
  }

struct node* szukaj(struct node *start, char *tValue) // więc o wiele lepiej tak
  {
   if(!start) return NULL;
   int v=strcmp(start->word, tValue);
   if(v<0) return szukaj(start->left, tValue);
   if(v>0) return szukaj(start->right, tValue);
   return start;
  }

struct node* szukaj(struct node *current, char *tValue) // lub tak
  {
   int v=0;
   while(current)
     {
      v=strcmp(tValue,current->word); // strcmp - tylko raz na poziom
      if(v<0) current=current->left;
      else if(v>0) current=current->right;
      else break;
     }
   return current;
  }

void treeInsert(struct node *current, char *tValue)
  {
   struct node *parent=NULL;
   int v=0;
   while(current)
     {
      parent=current;
      v=strcmp(tValue,current->word); // strcmp - tylko raz na poziom
      if(v<0) current=current->left;
      else if(v>0) current=current->right;
      else
        {
         ++current->arity;
         return;
        }
     }
   current=(struct node*)malloc(sizeof(struct node));
   current->word=strdup(tValue);
   current->arity=1;
   current->left=current->right=NULL;
   current->parent=parent;
   if(v<0) parent->left=current;
   else if(v>0) parent->right=current;
   else root=current;
  }

Usuwanie to też da się zapisać po ludzku.

0

Sądzisz, że tego typu kosmetyka naprawi te błędy, że czasem zamiast pustego drzewa mam jakiś śmieć przywiązany?

0

To nie kosmetyka, zaś poprawny kod, który przy okazji jest dwa razy krótszy od twojego niepoprawnego. Jak poprawisz jeszcze kasowanie to będzie działać poprawnie.

0

Napisałem według Cormena w ten sposób:

 
void del(struct node *z)
{
    if(z->arity > 1)
    {
        z->arity--;
        return;
    }
    struct node *x, *y;

    if(z->left == NULL || z->right == NULL) y = z;
    else y = naj_lewo(z);

    if(y->left) x = y->left;
    else x = y->right;

    if(x) x->parent = y->parent;

    if(y->parent == NULL) root = x;
    else if(y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;

    if(y!=z)
    {
        z->word = strdup(y->word);
        z->arity = y->arity;
    }
    //return y;
}

Wydaje mi się, że jest czytelniej, tzn nie orientuję się w tym co się dzieje aż tak dobrze jak w tamtym kodzie, ale z pewnością jest o wiele krótszy i zwięzły. Tylko czy to będzie poprawnie działać? Niby książkowe przepisanie pseudokodu, ale nie zwracam tego y, bo mój root jest globalny, więc nic zwracać nie muszę, prawda?

0

Oczywiście że nie będzie działać, bo to twoje wg Cormena. Wiesz Caruso http://pl.wikipedia.org/wiki/Enrico_Caruso bardzo ładnie śpiewał, ale jak ja zaśpiewam to samo to już będzie zupełnie nie to samo, mam nadzieje że rozumiesz aluzję.

0

Dobra, wrzucam jeszcze raz cały kod. Mam wrażenie, że to się nie wysypuje, a rozwiązanie Cormena pasuje do mojego tragicznego programu. W każdym razie bawiłem się nim trochę i nie było błędu.

#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 del(struct node *z);
// 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);
    if(szukaj(current,tValue) == NULL)
        printf("Brak takiego wyrazu.\n");
    else
        del(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)
{
    struct node *parent=NULL;
    int v=0;
    while(current)
    {
      parent=current;
      v=strcmp(tValue,current->word); // strcmp - tylko raz na poziom
      if(v<0) current=current->left;
      else if(v>0) current=current->right;
      else
        {
         ++current->arity;
         return;
        }
     }
   current=(struct node*)malloc(sizeof(struct node));
   current->word=strdup(tValue);
   current->arity=1;
   current->left=current->right=NULL;
   current->parent=parent;
   if(v<0) parent->left=current;
   else if(v>0) parent->right=current;
   else root=current;
}

void del(struct node *z)
{
    if(z->arity > 1)
    {
        z->arity--;
        return;
    }
    struct node *x, *y;

    if(z->left == NULL || z->right == NULL) y = z;
    else y = naj_lewo(z);

    if(y->left) x = y->left;
    else x = y->right;

    if(x) x->parent = y->parent;

    if(y->parent == NULL) root = x;
    else if(y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;

    if(y!=z)
    {
        z->word = strdup(y->word);
        z->arity = y->arity;
    }
    //return y;
}

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

struct node* szukaj(struct node *current, char *tValue)
{
    int v=0;
    while(current)
    {
        v=strcmp(tValue,current->word); // strcmp - tylko raz na poziom
        if(v<0)
            current=current->left;
        else if(v>0)
            current=current->right;
        else break;
    }
   return current;
}


 
0

Nadal jeżeli zaczniesz od usuwania czegokolwiek czego nie ma na drzewie, to się wywali.
Poza tym:

char *D[]={"Aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","Bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"};
unsigned i,k;
treeInsert(root,D[1]);
for(i=0;i<1000000;++i)
  {
   k=i&1;
   treeInsert(D[k]);
   del(szukaj(root,D[1-k]));
   if(!(i&0xFFFF)) printf("\r%d",i);
  }
printf("\r%d\n",i);

Wsadź ten fragment kodu w main'a (tuż przed while), odpal program i obserwuj proces w ProcessMenager'ze.

0

Nie powinien się wywalić, przecież dodałem w funkcji usun zabezpieczenie. Widzę, że je można zmienić żeby dwa razy nie suzkać, ale to już kosmetyka.

0

Ah, skumałem że tam w ogóle nie ma żadnego free w tym usuwaniu. Czy free(y) załatwi sprawę? Nie testowałem jeszcez tego fragmentu kodu, który napisałeś, tak mi na myśl to przyszło po prostu. Mogę pozabierać sporo pamięci, tak?

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