Problem z BST w C

0

Witam! Mam mały problem z zadaniem domowym. Napisałem szkielet w C lecz występują jakieś błędy i nie wiem jaka mam sobie z nimi poradzić. Z góry dzięki za wszelką pomoc!!!!!!

Napisac program realizujacy słownik angielsko-polski w strukturze drzewa BST.
Program ma umoliwiac wykonanie nastepujacych operacji:
a) wstawienie nowego słowa angielskiego do słownika wraz z polskimi tłumaczeniami tego
słowa. Porzadek symetryczny drzewa jest wyznaczony przez porzadek leksykograficzny
(alfabetyczny) słów angielskich. Mona przyjac, e jedno słowo angielskie ma nie wiecej ni
trzy tłumaczenia.
b) usuniecie słowa angielskiego wraz z tłumaczeniami tego słowa,
c) wyszukanie podanego słowa angielskiego i wypisanie tłumaczen polskich tego słowa,
wzglednie wyswietlenie komunikatu : Brak tłumaczen słowa .......
d) zapis aktualnej zawartosci słownika w pliku binarnym. Trzeba zapamietac wszystkie
słowa angielskie wraz z ich tłumaczeniami. Format danych w pliku prosze ustalic
samodzielnie.
e) odczyt słownika z pliku binarnego i wstawienie wszystkich danych do drzewa BST
(niekoniecznie pustego).
Ustalic koszt pesymistyczny realizowanych przez program operacji opisanych w punktach a)
b) c) d) e) . Za operacje elementarna przyjmujemy porównania miedzy słowami angielskimi
w drzewie, a słowem szukanym, usuwanym badz dodawanym do słownika.

#include <stdio.h>
#include <conio.h>
#include <iomanip>

struct slowa
{
char angielskie[30];
char polskie [3][30];
int liczba; //liczba tlumaczen
};
// definicja wezla BST
struct wezel
{
slowa dane; //do zapamietywania danych
wezel lewy;
wezel
prawy;
};
wezel *r=null;

//search
wezel search( char angielskie , wezel *r , wezel *p, )
{
wezel
current
current=r;
(
p)=NULL;
while( current != NULL )
{
if(strcmp(angielskie,current->dane.angielskie)==0)
{
return current;
} else
{
(p)=current;
if(strcmp(angielskie,current->dane.angielskie )>0)
{
current=(
p)->right;
} else
{
current=(*p)->left;
}
}
}
return null;
}

int insert(slowo e,wezel *r)
{
wezel
temp;
if(search(e,r,p)==NULL)
{
temp=(wezel *)malloc(wezel);
strcpy(....);
//......
temp->right=NULL;
temp->left=NULL;

         if(r==null)
         {
             r=temp;
             return 1;
         }
         else
         {
             if(strmp(.....))
             {p->left=temp;}
             else {
                 p->right=temp;
             return 1;
             }; 

}
else return 0;
}

0

Niemam zabardzo czasu zagłębiania się w ten program ale po pierwsze czy Wezel nie powinien mieć jeszcze wskaźnika do ojca? Bo jak bez tego chcesz usuwać elementy.

A o to coś co ci powinno pomóc rozwiązać problem drzewa, wszystko co ci do tego potrzebne:

/ drzewo.c -- funkcje do obslugi drzewa /
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "drzewo.h"
/ lokalny typ danych /
typedef struct para {
Wezel rodzic;
Wezel
dziecko;
} Para;
/ prototypy funkcji lokalnych /
static Wezel UtworzWezel(const Pozycja wp);
static bool NaLewo(const Pozycja p1, const Pozycja p2);
static bool NaPrawo(const Pozycja p1, const Pozycja p2);
static void DodajWezel(Wezel nowy, Wezel korzen);
static void PoKolei(const Wezel korzen, void ( wfun)(Pozycja pozycja));
static Para SzukajPozycji(const Pozycja wp, const Drzewo wdrzewo);
static void UsunWezel(Wezel *wsk);
static void UsunWszystkieWezly(Wezel
wsk);
/ definicje funkcji /
void InicjujDrzewo(Drzewo wdrzewo)
{
wdrzewo->korzen = NULL;
wdrzewo->rozmiar = 0;
}
bool PusteDrzewo(const Drzewo
wdrzewo)
{
if (wdrzewo->korzen == NULL)
return true;
else
return false;
}
bool PelneDrzewo(const Drzewo wdrzewo)
{
if (wdrzewo->rozmiar == MAXPOZ)
return true;
else
return false;
}
int LiczbaPozycji(const Drzewo
wdrzewo)
{
return wdrzewo->rozmiar;
}
bool DodajPozycje(const Pozycja wp, Drzewo wdrzewo)
{
Wezel nowy;
if (PelneDrzewo(wdrzewo))
{
fprintf(stderr,"Drzewo jest pelne\n");
return false; /
wczesny powrot /
}
if (SzukajPozycji(wp, wdrzewo).dziecko != NULL)
{
fprintf(stderr, "Proba dodania istniejacej pozycji\n");
return false; /
wczesny powrot /
}
nowy = UtworzWezel(wp); /
nowy wskazuje na nowy wezel /
if (nowy == NULL)
{
fprintf(stderr, "Nie mozna utworzyc wezla\n");
return false; /
wczesny powrot /
}
/
utworzenie nowego wezla sie powiodlo /
wdrzewo->rozmiar++;
if (wdrzewo->korzen == NULL) /
przypadek 1: drzewo jest puste /
wdrzewo->korzen = nowy; /
nowy wezel jest korzeniem drzewa /
else /
przypadek 2: drzewo nie jest puste /
DodajWezel(nowy,wdrzewo->korzen); /
dodaje nowy wezel do drzewa /
return true;
}
bool WDrzewie(const Pozycja
wp, const Drzewo wdrzewo)
{
return (SzukajPozycji(wp, wdrzewo).dziecko == NULL) ? false : true;
}
bool UsunPozycje(const Pozycja
wp, Drzewo wdrzewo)
{
Para szuk;
szuk = SzukajPozycji(wp, wdrzewo);
if (szuk.dziecko == NULL)
return false;
if (szuk.rodzic == NULL) /
usuwa pozycje w korzeniu /
UsunWezel(&wdrzewo->korzen);
else if (szuk.rodzic->lewy == szuk.dziecko)
UsunWezel(&szuk.rodzic->lewy);
else
UsunWezel(&szuk.rodzic->prawy);
wdrzewo->rozmiar--;
return true;
}
void Przejdz (const Drzewo
wdrzewo, void ( wfun)(Pozycja pozycja))
{
if (wdrzewo != NULL)
PoKolei(wdrzewo->korzen, wfun);
}
void UsunWszystko(Drzewo
wdrzewo)
{
if (wdrzewo != NULL)
UsunWszystkieWezly(wdrzewo->korzen);
wdrzewo->korzen = NULL;
wdrzewo->rozmiar = 0;
}
/ funkcje lokalne /
static void PoKolei(const Wezel korzen, void ( wfun)(Pozycja pozycja))
{
if (korzen != NULL)
{
PoKolei(korzen->lewy, wfun);
(wfun)(korzen->pozycja);
PoKolei(korzen->prawy, wfun);
}
}
static void UsunWszystkieWezly(Wezel
wsk)
{
Wezel wprawy;
if (wsk != NULL)
{
wprawy = wsk->prawy;
UsunWszystkieWezly(wsk->lewy);
free(wsk);
UsunWszystkieWezly(wprawy);
}
}
static void DodajWezel (Wezel
nowy, Wezel korzen)
{
if (NaLewo(&nowy->pozycja, &korzen->pozycja))
{
if (korzen->lewy == NULL) /
puste poddrzewo /
korzen->lewy = nowy; /
wiec wstawiamy tu wezel /
else
DodajWezel(nowy, korzen->lewy); /
w przeciwnym wypadku /
} /
szukamy szczescia w
poddrzewie /
else if (NaPrawo(&nowy->pozycja, &korzen->pozycja))
{
if (korzen->prawy == NULL)
korzen->prawy = nowy;
else
DodajWezel(nowy, korzen->prawy);
}
else /
nie powinno byc dwoch identycznych pozycji /
{
fprintf(stderr,"Blad funkcji DodajWezel()\n");
exit(1);
}
}
static bool NaLewo(const Pozycja
p1, const Pozycja p2)
{
int porown1;
if ((porown1 = strcmp(p1->imie, p2->imie)) < 0)
return true;
else if (porown1 == 0 &&
strcmp(p1->gatunek, p2->gatunek) < 0 )
return true;
else
return false;
}
static bool NaPrawo(const Pozycja
p1, const Pozycja p2)
{
int porown1;
if ((porown1 = strcmp(p1->imie, p2->imie)) > 0)
return true;
else if (porown1 == 0 &&
strcmp(p1->gatunek, p2->gatunek) > 0 )
return true;
else
return false;
}
static Wezel
UtworzWezel(const Pozycja wp)
{
Wezel
nowy;
nowy = (Wezel ) malloc(sizeof(Wezel));
if (nowy != NULL)
{
nowy->pozycja =
wp;
nowy->lewy = NULL;
nowy->prawy = NULL;
}
return nowy;
}
static Para SzukajPozycji(const Pozycja wp, const Drzewo wdrzewo)
{
Para szuk;
szuk.rodzic = NULL;
szuk.dziecko = wdrzewo->korzen;
if (szuk.dziecko == NULL)
return szuk; / wczesny powrot /
while (szuk.dziecko != NULL)
{
if (NaLewo(wp, &(szuk.dziecko->pozycja)))
{
szuk.rodzic = szuk.dziecko;
szuk.dziecko = szuk.dziecko->lewy;
}
else if (NaPrawo(wp, &(szuk.dziecko->pozycja)))
{
szuk.rodzic = szuk.dziecko;
szuk.dziecko = szuk.dziecko->prawy;
}
else / jesli szukana pozycja nie znajduje sie ani po lewej,/
break; / ani po prawej stronie pozycji szuk.dziecko->
pozycja,
/
} / pozycje sa identyczne; szuk.dziecko jest adresem
wezla
/
return szuk; / przechowujacego szukana pozycje /
}
static void UsunWezel(Wezel *wsk)
/
wsk jest adresem skladnika rodzica, ktory wskazuje na usuwany wezel /
{
Wezel
tymcz;
if ( (wsk)->lewy == NULL)
{
tymcz =
wsk;
wsk = (wsk)->prawy;
free(tymcz);
}
else if ( (wsk)->prawy == NULL)
{
tymcz =
wsk;
wsk = (wsk)->lewy;
free(tymcz);
}
else / usuwany wezel ma dwoje dzieci /
{
/ szukamy miejsca dolaczenia prawego poddrzewa /
for (tymcz = (wsk)->lewy; tymcz->prawy != NULL;
tymcz = tymcz->prawy)
continue;
tymcz->prawy = (
wsk)->prawy;
tymcz = wsk;
wsk =(*wsk)->lewy;
free(tymcz);
}
}

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