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.