[C] Problem z usuwaniem elementów w drzewie BST


(Wojcirej) #1

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


(Grzelix) #2

dość wczesna pora na myślenia i musiałbym sobie co nieco przypomnieć o bst drzewach ale...

bez wnikania w szczegóły ta linijka w metodzie usuń wydaje mi się podejrzana

if(z->left==NULL||x->right==NULL)

czy nie powinno tam być;

if(z->left==NULL||z->right==NULL)

(Wojcirej) #3

Heh, oczywiście, że z. :slight_smile:

To nie był jedyny problem, ale już sobie poradziłem. Mnie osobiście poranki do myślenia sprzyjają. :slight_smile:

Dzięki za pomoc. Inaczej bym w ogóle nie przejrzał jeszcze raz tej metody. :smiley:

Można zamknąć.