[C++] Problem z algorytmem sortowania w drzewie BST


(niesuszek) #1

Witam. Mój problem dotyczy algorytmu sortowania w drzewie BST. W czym błąd?

Algorytm sortowania:

void sort(BST *root) {

		while(root != NULL) {

			BST *pomoc = elementMIN(root);

			cout << pomoc << " ";

			root = pomoc;

			delete pomoc;

		}

	}

Algorytm elemenMIN (najmniejszy element w drzewie):

BST* elementMIN(BST *root) {

		if(root->lewy != NULL)

			return elementMIN(root->lewy);

		else

			return root;

	}

#2

Na moje kiepskie oko masz taki problem:

Przenosisz najmniejsza wartosc na początek poprzez znalezienie jej a następnie robisz to samo, znów

tylko że bierzesz pod uwagę też tą wartość którą aktualnie przeniosłeś, czyli przesuwasz ją znów na początek, czyli tam gdzie jest.


(niesuszek) #3
BST* sort(BST *korzen) {

		BST *pomoc = NULL;

		if(korzen != NULL) {

			while(korzen != NULL) {

				elementMIN(korzen);

				int pomoc2 = korzen->element;

				cout << pomoc2 << " ";

				del(member2(korzen, pomoc2));

			}

		}

		return korzen;

	}

gdzie **del**:

void del(BST *root)

KOD FUNKCJI 

delete root;

**member2**:

BST* member2(BST *start, int wartosc) {

		// jesli element jest szukana wartoscia to odnalezlismy ja

		if (start->element == wartosc) 

			return start;


		// jesli szukana wartosc jest mniejsza to idziemy do lewego poddrzewa - o ile istnieje

		else if (wartosc < start->element && start->lewy != NULL) 

			return member2(start->lewy, wartosc);


		// jesli szukana wartosc jest wieksza to idziemy do prawego poddrzewa - o ile istnieje     

		else if (wartosc > start->element && start->prawy != NULL) 

			return member2(start->prawy, wartosc);


		return NULL;

	}

Teraz wyświetla 4 liczby z 6 i wyrzuca błąd. W czym błąd?


([alex]) #4

Co to za głupoty usuwające coś sortowanie? To jakieś bzdury. niesuszek, może wytłumacz po ludzku o co ci biega?


(kostek135) #5

Używanie drzewa BST do sortowania (kiedy celem nadrzędnym jest sortowanie) to ekhm… najdziwniejsza rzecz jaką widziałem. Jesteś pewny że nie chodziło o bin-heap? W każdym razie jeśli wypiszesz węzły w kolejności in-order, otrzymasz ciąg posortowany rosnąco (oczywiście odczytanie go od końca da ciąg malejący, ale to już oczywiste)

Wypisywanie in-order rekurencyjnie można zapisać jako:

  1. Dla węzła jeśli ma lewe dziecko to wywołaj dla lewego dziecka

  2. Jeśli nie ma już lewych dzieci to wypisz mnie

  3. Wywołaj dla prawego dziecka - o ile możliwe