Nie działające szukanie pozycji w drzewie binarnym C++

Question

Hej ,irytuje mnie pewien problem  ,stworzyłem drzewo binarne oparte na wskaźnikach ,dodawanie do niego elementów raczej działa ok ale jest problem przy wyszukiwanie pozycji danej liczby w strukturze .Zamiast dostać numer odpowiedniego więzła (k) to jest zwracana liczba jaka się tam znajduje . Nie mam zielonego pojęcia gdzie znajduje się błąd \: . Jak jest coś nie jasne to dajcie znać ,z góry dziękuje za pomoc  ,a oto kod (problem chyba tkwi w funkcji search() :

#include <iostream>
#include <windows.h>
#include <conio.h>

using namespace std;

struct drzewo { //nasze dreewo
	int dane;
	drzewo *lewy_potomek;
	drzewo *prawy_potomek;
};

drzewo *korzen = NULL; //korzen

void add(int x, drzewo *&rodzic) { //dodaj element
	if(rodzic==NULL) { //jezeli jest wolne miejsce 
		rodzic = new drzewo;
		rodzic->dane = x;
		rodzic->lewy_potomek = NULL;
		rodzic->prawy_potomek = NULL;
	} else { //jezeli nie to wstaw na prawo lub na lewo
		if(x>=rodzic->dane) add(x,rodzic->prawy_potomek);
		if(x<rodzic->dane) add(x,rodzic->lewy_potomek);
	}
}

int search(int x, drzewo *&rodzic) { //szukaj
	int k = 1; //pozucja na start wynosi jeden
	drzewo *bufor = rodzic; //pomocnicze drzewko

	while(x!=bufor->dane) { //powtazaj do puki nie znajadzemy tej liczby

		if(bufor==NULL) { //jak jej nie ma o zwroc zero (to nie dzala...)
			return 0;
			break;
		}

		else if(x==bufor->dane) {
			return k; //jak znalezlismy to zwroc *pozycje* wezel a nie bufor->dane !!!
		}

		else {
			if(x>bufor->dane) { //odpowiedznie kierowanie sie 
				bufor = bufor->prawy_potomek;
				k=(k*2)+1; //2k+1
			} else if(x<bufor->dane) {
				bufor = bufor->lewy_potomek;
				k*=2; //2k
			}
		}
	}
}

int main() {

	while(true) {
		cout<<"---MENU---"<<endl;
		cout<<"1. dodaj"<<endl;
		cout<<"2. szukaj"<<endl;
		cout<<"----------"<<endl;

		char z = getch();

		switch(z) {
			case '1': {
				int value;
				cout<<"value: ";
				cin>>value;
				add(value,korzen);
				break;
			}
			case '2': {
				int value; //a moze tu jest cos nie tak ?
				cout<<"value: ";
				cin>>value;
				cout<<"position: "<<search(value,korzen);
				getch();
				break;
			}
		}
		
		system("cls");
	}

	return 0;
}

 

Answer 1

Nie wiem co rozumiesz przez 'numer węzła', a tym bardziej jaki by to miało sens. IMO największy sens miałoby zwrócenie wskaźnika na znaleziony węzeł (drzewo*). W ten sposób ze znalezionego węzła możesz się nadal poruszać jak ci się podoba. Z 'numerem węzła' nie wiem co mógłbyś zrobić. (czyli wystarczy, że będziesz zwracał bufor (albo nullptr w wypadku nie znalezienia).

Kilka uwag:

1. Nie ma u ciebie absolutnie żadnego powodu, żeby przekazywać pointer przez referencje. Wystarczy sam pointer albo sama referencja. Tak na dobrą sprawe, przekazywanie przez wartość też niczego specjalnie by nie zmieniło, ale ok - nie chcemy kopiować całego obiektu.
2. Funkcja search: jeśli już rodzic okaże się być tym właściwym węzłem, to twoja funkcja nie dojdzie do żadnego return (nie wejdzie w ogóle w pętle). Innymi słowy - użyj do..while. Dodatkowo - warunek pętli jest niepotrzebny - możesz postawić do..while(true) - i tak (o ile sterowanie wejdzie w pętle) każdy możliwy przypadek zostaje rozpatrzony i funkcja się prędzej czy później zakończy.
3. Używaj const w argumentach funkcji. Szczególnie przy pointerach czy referencjach. Bardzo ułatwia czytanie kodu, a tobie na pewno zaoszczędzi kłopotów. Dodatkowo const lvalue referencja "złapie" też rvalue.
   Zauważ też znaczenie const przy wskaźnikach: słowo const przy nazwie typu (po lewej stronie gwiazdki) zapobiega zmianie zmiennej pod wskaźnikiem, a const przy nazwie wskaźnika (po prawej stronie gwiazdki) zapobiega zmianie samego wskaźnika (adresu który przetrzymuje).
   const int * const ptr;

Comments

(Ja próbuję dać wędkę, a tu spoilery :/ )

---

Przepraszam XD stosunkowo długo to pisałem i nawet nie widziałem twojej odpowiedzi.

---

(ale ogólnie ładnie napisane)

---

(Dziękuje :3)

---

przepraszam że tak późno wracam do tematu ale dokonałem pewnych zmian i dalej mi nie działa (cały czas teraz już inna find funkcja zwraca 0 ,to jest w kodzie zapisane w komentarzach )

Zamiast szukać pozycji danej liczby to teraz wpisujemy numer więzła i zwracana jest liczba jaka się tam znajduje ... Dodałem też nowy element do struktury ,ale to już widać w kodzie w komentarzach ,może zanim dam kod to wytłumaczę czym jest ten numer więzła ,dziękuje za twoją pomoc :

liczby to numery więzła :

              1

    2                 3

4    5            6       7    itd... na lewo 2k a na prawo 2k+1

 

kod:

#include <iostream>
#include <windows.h>
#include <conio.h>

using namespace std;

struct drzewo { //nasze dreewo
	int dane;
	int nr_wezla; //nowy element (pozycja w drzewie)
	drzewo *lewy_potomek;
	drzewo *prawy_potomek;
};

drzewo *korzen = NULL; //korzen
int k = 1; //poczattkowa wartosc wezla 

void add(int x, drzewo *rodzic, int k) { //dodaj element
	if(rodzic==NULL) { //jezeli jest wolne miejsce
		rodzic = new drzewo;
		rodzic->dane = x;
		rodzic->nr_wezla = k;
		rodzic->lewy_potomek = NULL;
		rodzic->prawy_potomek = NULL;
		
		if(korzen==NULL){ //jezeli jest to pierwszy element to zapelnij koren
			korzen = rodzic;
		}
		
	} else { //jezeli nie to wstaw na prawo lub na lewo
		if(x>=rodzic->dane) add(x,rodzic->prawy_potomek,(k*2)+1);
		if(x<rodzic->dane) add(x,rodzic->lewy_potomek,k*2);
	}
}

int find(int position) {
	drzewo *rodzic = korzen;
	do{ //do while
		if(rodzic==NULL){ //jezeli danego elementu nie ma 
			return 0;
			break;
		}
		else if(position==rodzic->nr_wezla){ //jezeli znaleziono
			return rodzic->dane;
			break;
		}
		else if(position>rodzic->nr_wezla){//na prawo
			rodzic = rodzic->prawy_potomek;
		}
		else if(position<rodzic->nr_wezla){//na lewo
			rodzic = rodzic->lewy_potomek;
		}
	}while(true);
}

int main() {

	while(true) {
		cout<<"---MENU---"<<endl;
		cout<<"1. dodaj"<<endl;
		cout<<"2. szukaj"<<endl;
		cout<<"----------"<<endl;

		char z = getch();

		switch(z) {
			case '1': {
				int value;
				cout<<"value: ";
				cin>>value;
				add(value,korzen,k);
				break;
			}
			case '2': {
				int position; //a moze tu jest cos nie tak ?
				cout<<"position: ";
				cin>>position;
				cout<<"number: "<<find(position);
				cout<<korzen->dane<<endl; //*to dla testu( ,niby korzen miesci w sobie odpowiedznie dane ale find zawsze zwraca zero 
				getch();
				break;
			}
		}

		system("cls");
	}

	return 0;
}

 

---

Ok, rozumiem teraz twoje numerowania węzłów. Sensu jednak nadal nie, ale nieważne.

Po pierwsze - przepraszam za jedną rzecz. Napisałem, że nie ma u ciebie żadnego powodu na przekazywanie pointera przez referencje. Cóż - w funkcji add jest - nie zauważyłem, że przypisujesz do przekazanego wskaźnika wywołanie new. Także i w pierwszym kodzie i teraz powód jest. Co prawda - nie powinieneś alokować tak wewnątrz funkcji (utradnia zarządzanie), ale nie o tym teraz mówimy. (możesz użyć smart pointerów jeśli są ci znane, albo doczytać :P) To z pewnością był jeden z powodów problemów. Jak nie teraz to w przyszłości. Jeszcze dopowiem, że nie zwalniasz nigdzie tej zaalokowanej pamięci.

Znalazłem też jeden błąd logiczny w kodzie:
 

else if(position>rodzic->nr_wezla){//na prawo
   rodzic = rodzic->prawy_potomek;
}
else if(position<rodzic->nr_wezla){//na lewo
   rodzic = rodzic->lewy_potomek;
}

Poszukiwany 'numer węzła' zawsze będzie większy od 'numeru' rodzica (skoro jeszcze nie trafiliśmy na poszukiwany i musimy iść głębiej) - w końcu numery dzieci to odpowiednio 2k i 2k+1 gdzie k to nr rodzica. W twoim kodzie zakładasz, że jeśli poszukiwany nr jest mniejszy, to powinniśmy iść w lewo co się nigdy nie powinno zdarzyć. To skutkuje tym, że poszukiwania idą cały czas w prawo.
Możliwe, że jest więcej błędów ale na razie nie widze.

Moja rada: skończ z tymi 'numerami węzłów' albo chociaż wytłumacz mi czemu to ma służyć.

PS: if w linii 25. wygląda bardzo brzydko. Nagle jakaś zmienna globalna wchodzi nie wiadomo skąd i po co. W ogóle pozbądź się zmiennych globalnych.
 

---

dzięki za pomoc ,to mi dało więcej do myślenia i swoją drogą ten kod if-ów w ogóle był bez sensu . Te całe węzły nie służą do niczego konkretnego ale używam ich do ćwiczeń ,po za tym słyszałem o czymś takim jak 'przeszukiwanie w głąb' oraz o tym iż drzewa binarne dają możliwość szybszego szukania danych bo za pierwszym razem odrzucamy połowę wartości  . Dokładne jednak nie wiem jak to działa ,może właśnie w tym jest problem że mało poczytałem o budowie i zastosowaniu drzew binarnych .Coś pomyśle a jak mi dalej nie zadziała to zerknę na gotową implementacje ;(

---

słyszałem o czymś takim jak 'przeszukiwanie w głąb'

Mówisz o DFS - taki algorytm trawersowania drzew. Jest też analogiczny BFS 'przeszukiwanie w szerz'. Z tymi hasłami pewnie łatwiej ci będzie dojść do informacji.

 drzewa binarne dają możliwość szybszego szukania danych bo za pierwszym razem odrzucamy połowę wartości  . Dokładne jednak nie wiem jak to działa

Większe wartości (lub ew. równe) są zawsze po prawej, a mniejsze po lewej. W dość oczywisty sposób oszczędzasz sobie sprawdzania pewnej części elementów do czego byłbyś zmuszony np. w tablicy. 

Answer 2

1. Włącz ostrzeżenia kompilatora. Powinien krzyczeć na `search`.

2. masz pętlę while, która próbuje czytać bufor, a potem sprawdzasz czy bufor jest NULLem.

Comments

dzięki za odpowiedź ,zrobiłem kilka zmian ale problem jest cały czas taki sam "funkcja zwraca dane a nie k" . Wiem że mogłem coś nie tak zrozumieć , jak coś to przepraszam i będe wdzięczny za dalszą pomoc .

kod ,tu dałem też w komentarzach informacje o zmianach :

int find(int x, drzewo *&rodzic) { //szukaj (zmiana nazwy na find)
	int k = 1; //pozucja na start wynosi jeden
	drzewo *bufor = rodzic; //pomocnicze drzewko

	if(bufor==NULL) { //sprawdzanie czy nie zdazylo sie tak ze stos jest pusty
		return 0;
	}

	while(x!=bufor->dane) { //powtazaj do puki nie znajadzemy tej liczby

		if(bufor==NULL) { //to jest po to by nie kontyulowac iteracje gdy juz doslismy do konca drzewa
			return 0;
			break;
		}

		else if(x==bufor->dane) {
			return k; //jak znalezlismy to zwroc *pozycje* wezel a nie bufor->dane !!!
		}

		else {
			if(x>bufor->dane) { //odpowiedznie kierowanie sie
				bufor = bufor->prawy_potomek;
				k=(k*2)+1; //2k+1
			} else if(x<bufor->dane) {
				bufor = bufor->lewy_potomek;
				k*=2; //2k
			}
		}
	}
}

 

---

*nawet gdy zamiast return k dam dla głupoty return 1 to i tak funkcja zwraca mi "wartosc" elementu stosu

---

Um... nie poprawiłeś żadnego z dwóch problemów, które wspomniałem. (jaki używasz edytor/kompilator?)