Podjąłem się implementacji drzewa BST na strukturach wskaźnikowych w języku C.
Tak to się prezentuje w kodzie:
#include
struct element
{
int k;
struct element *left;
struct element *right;
struct element *parent;
};
void bst_inorder(struct element *x);
struct element *bst_wstaw(struct element *root, struct element *z);
struct element *bst_min(struct element *x);
struct element *bst_nastepnik(struct element *x);
struct element *bst_szukaj(struct element *x, int k);
struct element *bst_usun(struct element *root, struct element *z);
int main()
{
struct element *root=NULL, *nowy=NULL;
char z;
int liczba;
while(1)
{
system("cls");
printf("Co chcesz zrobic?");
printf("\nD - Dodac");
printf("\nS - Szukac");
printf("\nU - Usunac");
printf("\nW - Wystwietlic metoda inorder");
printf("\nQ - Wyjsc");
fflush(stdin);
printf("\nWybor: ");
z=getchar();
switch(z)
{
case 'd':
nowy=(struct element*) malloc(sizeof(struct element));
printf("\nPodaj wartosc do wstawienia: ");
scanf("%d",&liczba);
nowy->k=liczba;
nowy->left=NULL;
nowy->right=NULL;
root=bst_wstaw(root,nowy);
break;
case 's':
printf("\nPodaj wartosc do znalezienia: ");
scanf("%d",&liczba);
nowy=bst_szukaj(root,liczba);
fflush(stdin);
if(nowy==NULL)
{
printf("\nNie znaleziono elemenu w drzewie.");
getchar();
}
else
{
printf("\nSzukany element znajduje sie w drzewie.");
getchar();
}
break;
case 'w':
if(root==NULL) printf("\nDrzewo puste");
else
bst_inorder(root);
fflush(stdin);
getchar();
break;
case 'u':
printf("\nPodaj element do usuniecia ");
scanf("%d",&liczba);
nowy=bst_szukaj(root,liczba);
fflush(stdin);
if(nowy==NULL)
{
printf("\nNie znaleziono elementu do usuniecia");
getchar();
}
else
{
nowy=bst_usun(root,nowy);
root=nowy;
printf("\nElement usuniety");
}
getchar();
break;
case 'q': return 0;
}
}
}
void bst_inorder(struct element *x)
{
if (x!=NULL)
{
bst_inorder(x->left);
printf("%d ",x->k);
bst_inorder(x->right);
}
}
struct element *bst_wstaw(struct element *root, struct element *z)
{
struct element *y=NULL, *x=root;
while(x!=NULL)
{
y=x;
if(z->kk)
x=x->left;
else x=x->right;
}
z->parent=y;
if(y==NULL)
root=z;
else if(z->kk)
y->left=z;
else y->right=z;
return root;
}
struct element *bst_min(struct element *x)
{
while(x->left!=NULL)
x=x->left;
return x;
}
struct element *bst_nastepnik(struct element *x)
{
struct element *y;
if(x->right!=NULL)
return bst_min(x->right);
y=x->parent;
while(y!=NULL&&x==y->right)
{
x=y;
y=y->parent;
}
return y;
}
struct element *bst_szukaj(struct element *x, int k)
{
while(x!=NULL&&k!=x->k)
{
if(kk)
x=x->left;
else x=x->right;
}
return x;
}
struct element *bst_usun(struct element *root, struct element *z)
{
struct element *x=NULL, *y;
int temp;
if(z->left==NULL||x->right==NULL)
y=z;
else y=bst_nastepnik(z);
if(y->left!=NULL)
x=y->left;
else x=y->right;
if(x!=NULL)
{
x->parent=y->parent;
y->parent=NULL;
root=x;
}
else if(y==x->parent->left)
y->parent->left=x;
else y->parent->right=x;
if(y!=z)
{
temp=y->k;
y->k=z->k;
z->k=temp;
}
free(z);
return root;
}
I prawie wszystko działa, kompiluje się poprawie, ale jest problem z usuwaniem.
Bowiem jeżeli dodam kilka elementów do drzewa (załóżmy 5,2,8,16,14) i będę chciał usunąć najmniejszy (w tym wypadku) 2, to wszystko jest okej. Kiedy jednak chcę usunąć którąś ze “środkowych” wartości (w porządku inorder będzie 2,5,8,14,16 i przykładowo chcę wywalić 5), to element o kluczu 5 się usuwa, jednak znika też dwójka… a gdybym chciał usunąć maxa, to już wtedy program całkiem się wysypuje, bo pewnie lecą wszystkie klucze i nie ma co zwrócić…
Co robię źle? Chcę usunąć tylko ten klucz, który wstuka użyszkodnik z klawiatury.
Używam Win 7 SP1, Dev C++ 4.9.9.2
