C drzewo binarne wyszukiwanie

0

Witam
Zacząłem pisać program do drzewa binarnego, jednak po wywołaniu funkcji Search, crashuje mi się program. Bardzo proszę o pomoc
Pozdrawiam

#include <stdio.h>
#include <string.h>
#define ILOSC_NUMEROW 20        
 
typedef struct dane{
	char imie[20];
	char nazwisko[20];
	int numer[ILOSC_NUMEROW];
}Dane;
 
typedef struct drzewo{
	struct drzewo *lewy;
	struct drzewo *prawy;
	Dane dane;
}Drzewo;
 
void Insert(Drzewo *drzewo);  
void InOrder(Drzewo *root, Drzewo *temp);
//void SearchMin(Drzewo *drzewo);
//void SearchMax(Drzewo *drzewo);
void Search(Drzewo *root); 
//void Wysokosc(Drzewo *drzewo);
Drzewo *Compare(Drzewo *root, char *nazwisko);

 
 
int main(){
	
	fprintf(stderr, "test");
	int liczba_wezlow = 0;
	int wysokoc = 0;
	char ch;
	Drzewo root;
	root.lewy = NULL;
	root.prawy = NULL;
 
	printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
		"c - aby wyszukac maksymalne, d - wyszukac, q - aby wyjsc\n");
         
         
	while ((ch = getchar()) != 'q'){
		
		switch (ch){
			case 'a':
				Insert(&root);
				break;
			case 'b':
				//SearchMin(&root);
				break;
			case 'c':
				//SearchMax(&root);
				break;
			case 'd':
				Search(&root);
				break;
			case 'e':
				//Wysokosc(&root);
				break;
			case 'f':
				printf("%d", liczba_wezlow);
				break;
			default:
				printf("Blad w instrukcji switch!\n");

		}
		printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
		"c - aby wyszukac maksymalne, d - wyszukac, e - ilosc wezlow "
		"f - wysokosc, q - wyjscie\n");

		while(getchar () != '\n')
			continue;
 
		}
 
	return 0;
}
 

//WPROWADZA NOWA POZYCJE
void Insert(Drzewo *root){
 
	printf("insert!\n");
	int i, ilosc;
	Drzewo temp;
	

	printf("Podaj imie");
	scanf("%s", temp.dane.imie);
	printf("Podaj nazwisko");
	scanf("%s",temp.dane.nazwisko);
	printf("Podaj liczbe numerow ktore chcesz dodac");
	scanf("%d", &ilosc);
 
	for (i = 0; i < ilosc; i++)
		scanf("%d", &(temp.dane.numer[i]));

	temp.lewy = NULL;
	temp.prawy = NULL;
	

	InOrder(root, &temp);
	printf("Koniec Insert");
}


//REKURENCYJNIE PRZECHODZI PO DRZEWIE I DODAJE POZYCJE 
void InOrder(Drzewo *root, Drzewo *temp){
	printf("jest!");
	if (strcmp(temp->dane.nazwisko, root->dane.nazwisko) > 0){
		if (root->prawy == NULL)
			 root->prawy = temp;
		InOrder(root->prawy, temp);
	}
	else if (strcmp(temp->dane.nazwisko, root->dane.nazwisko) < 0){
		if (root ->lewy == NULL)
			root->lewy = temp;
		InOrder(root->lewy, temp);
	}
}


//WYSZUKIWANIE POZYCJI
void Search(Drzewo *root){

	char nazwisko[20];
	Drzewo *temp;

	printf("Wpisz nazwisko do wyszukania: ");
	scanf("%s", nazwisko);

	temp = Compare(root, nazwisko);
	if (temp == NULL)
		fprintf(stderr, "Brak pozycji!");

	printf("Imie: %s", temp->dane.imie);

}


//REKURENCYJNIE SPRAWDZA CZY JEST POZYCJA
Drzewo *Compare(Drzewo *root, char *nazwisko){
	printf("compare!");
	if (strcmp(nazwisko, root->dane.nazwisko) > 0){
		if (root->prawy == NULL){
			printf("brak pozycji!");
			return NULL;
		}
		Compare(root->prawy, nazwisko);
	}
	else if (strcmp(nazwisko, root->dane.nazwisko) < 0){
		if (root ->lewy == NULL){
			printf("brak pozycji!");
			return NULL;
		}
		Compare(root->lewy, nazwisko);
	}
	else
		return root;
} 
2

Przerób to w ten sposób:

...
typedef struct galaz
  {
   struct galaz *lewy,*prawy;
   Dane dane;
  } Galaz;
typedef struct drzewo
  {
   struct galaz *korzen;
  } Drzewo;
 
void Insert(Drzewo *drzewo,Dane dane);
void InOrder(Galaz *root);
void Search(Drzewo *drzewo,const char *nazwisko);
int Compare(Galaz *root,const char *nazwisko);

int main()
  {
   Drzewo drzewo={NULL};
   ...

bo tak jak zacząłeś to praktycznie nie da rady.

0

A jak funkcja InOrder ma dodać nową pozycję, mając tylko Galaz?

0
kry5 napisał(a):

A jak funkcja InOrder ma dodać nową pozycję, mając tylko Galaz?

To ciekawa koncepcja! Co ma niby dodawać funkcja InOrder?

0

hmm ma sprawdzać czy pozycja powinna znaleźć się po lewej stronie, czy po prawej i ustawić nową gałąź w odpowiednie miejsce. Dobrze myślę?

0

Zrobiłem coś takiego, jednak dalej nie działa...

 #include <stdio.h>
#include <string.h>
#define ILOSC_NUMEROW 20        
 
typedef struct dane{
	char imie[20];
	char nazwisko[20];
	int numer[20];
}Dane;
 
typedef struct drzewo{
	struct galaz *korzen;
}Drzewo;

typedef struct galaz{
	struct galaz *lewy, *prawy;
	Dane dane;
}Galaz;
 
void Insert(Drzewo *drzewo);  
void InOrder(Galaz *root, Galaz *temp);
//void SearchMin(Drzewo *drzewo);
//void SearchMax(Drzewo *drzewo);
void Search(Drzewo *wdrzewo); 
//void Wysokosc(Drzewo *drzewo);
void Compare(Galaz *root, const char *nazwisko, Galaz *temp);

 
 
int main(){
	
	fprintf(stderr, "test");
	int liczba_wezlow = 0;
	int wysokoc = 0;
	char ch;
	Drzewo wdrzewo;
	Galaz root;
	fprintf(stderr, "test");
	root.lewy = NULL;
	root.prawy = NULL;
	wdrzewo.korzen = &root;
 
	printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
		"c - aby wyszukac maksymalne, d - wyszukac, q - aby wyjsc\n");
         
         
	while ((ch = getchar()) != 'q'){
		
		switch (ch){
			case 'a':
				Insert(&wdrzewo);
				break;
			case 'b':
				//SearchMin(&root);
				break;
			case 'c':
				//SearchMax(&root);
				break;
			case 'd':
				Search(&wdrzewo);
				break;
			case 'e':
				//Wysokosc(&root);
				break;
			case 'f':
				printf("%d", liczba_wezlow);
				break;
			default:
				printf("Blad w instrukcji switch!\n");

		}
		printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
		"c - aby wyszukac maksymalne, d - wyszukac, e - ilosc wezlow "
		"f - wysokosc, q - wyjscie\n");

		while(getchar () != '\n')
			continue;
 
		}
 
	return 0;
}
 

//WPROWADZA NOWA POZYCJE
void Insert(Drzewo *wdrzewo){
 
	printf("insert!\n");
	int i, ilosc;
	Galaz temp;
	

	printf("Podaj imie");
	scanf("%s", temp.dane.imie);
	printf("Podaj nazwisko");
	scanf("%s",temp.dane.nazwisko);
	printf("Podaj liczbe numerow ktore chcesz dodac");
	scanf("%d", &ilosc);
 
	for (i = 0; i < ilosc; i++)
		scanf("%d", &(temp.dane.numer[i]));

	temp.lewy = NULL;
	temp.prawy = NULL;
	

	InOrder(wdrzewo->korzen, &temp);
	printf("Koniec Insert");
}


//REKURENCYJNIE PRZECHODZI PO DRZEWIE I DODAJE POZYCJE 
void InOrder(Galaz *root, Galaz *temp){
	printf("jest!");
	if (strcmp(temp->dane.nazwisko, root->dane.nazwisko) > 0){
		if (root->prawy == NULL)
			 root->prawy = temp;
		InOrder(root->prawy, temp);
	}
	else if (strcmp(temp->dane.nazwisko, root->dane.nazwisko) < 0){
		if (root ->lewy == NULL)
			root->lewy = temp;
		InOrder(root->lewy, temp);
	}
}


//WYSZUKIWANIE POZYCJI
void Search(Drzewo *wdrzewo){

	char nazwisko[20];
	Galaz *temp;

	printf("Wpisz nazwisko do wyszukania: ");
	scanf("%s", nazwisko);

	Compare(wdrzewo->korzen, nazwisko, temp);
	if (temp == NULL)
		fprintf(stderr, "Brak pozycji!");

	printf("Imie: %s", temp->dane.imie);

}


//REKURENCYJNIE SPRAWDZA CZY JEST POZYCJA
void Compare(Galaz *root, const char *nazwisko, Galaz *temp){
	printf("compare!");
	if (strcmp(nazwisko, root->dane.nazwisko) > 0){
		if (root->prawy == NULL){
			temp = NULL;
			fprintf(stderr, "Brak pozycji!");
		}
		Compare(root->prawy, nazwisko, temp);
	}
	else if (strcmp(nazwisko, root->dane.nazwisko) < 0){
		if (root ->lewy == NULL){
			fprintf(stderr, "Brak pozycji!");
			temp = NULL;
		}
		Compare(root->lewy, nazwisko, temp);
	}
	else
		temp = root;
}
0
_13th_Dragon napisał(a):

...

int main()
  {
   Drzewo drzewo={NULL};
   ...

Oczywiście możesz ignorować to co piszę częściowo lub w całości, to twoje prawo.

0

Nie zignorowałem, przyznaję się, że nie zauważyłem tej linijki... Jednak co ta linijka zmienia? Stworzyłem zmienną typu Galaz i od razu przypisałem ją drzewu, natomiast jej wskaźniki lewy i prawy ustawiłem na NULL.

0

... a w nazwisku jakieś śmieci, które porównujesz za pomocą strcmp w funkcji Compare wywołanej z Search

0

Nic już z tego nie rozumiem...

0

Podpiąłeś od drzewo jakiś fikcyjny węzeł bez danych i myślisz że nadal to może działać?

0

Dlaczego fikcyjny? W 41 linii przypisuje go do wdrzewo. A w 117 i 122 przypisuje do ostatniego wskazującego na NULL.

1

W main'ie masz: wdrzewo.korzen = &root; - jakie nazwisko ma ta osoba?

0

Rozumiem. Czy teraz dobrze działa funkcja dodawania pozycji?

 #include <stdio.h>
#include <string.h>
#define ILOSC_NUMEROW 20        
 
typedef struct dane{
    char imie[20];
    char nazwisko[20];
    int numer[20];
}Dane;
 
typedef struct drzewo{
    struct galaz *korzen;
}Drzewo;
 
typedef struct galaz{
    struct galaz *lewy, *prawy;
    Dane dane;
}Galaz;
 
void Insert(Drzewo *drzewo);  
void InOrder(Galaz *root, Galaz *temp);
//void SearchMin(Drzewo *drzewo);
//void SearchMax(Drzewo *drzewo);
void Search(Drzewo *wdrzewo); 
//void Wysokosc(Drzewo *drzewo);
void Compare(Galaz *root, const char *nazwisko, Galaz *temp);
 
 
 
int main(){
 
    fprintf(stderr, "test");
    int liczba_wezlow = 0;
    int wysokoc = 0;
    char ch;
    Drzewo wdrzewo;
	wdrzewo.korzen = NULL;
 
    printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
        "c - aby wyszukac maksymalne, d - wyszukac, q - aby wyjsc\n");
 
 
    while ((ch = getchar()) != 'q'){
 
        switch (ch){
            case 'a':
                Insert(&wdrzewo);
                break;
            case 'b':
                //SearchMin(&root);
                break;
            case 'c':
                //SearchMax(&root);
                break;
            case 'd':
                Search(&wdrzewo);
                break;
            case 'e':
                //Wysokosc(&root);
                break;
            case 'f':
                printf("%d", liczba_wezlow);
                break;
            default:
                printf("Blad w instrukcji switch!\n");
 
        }
        printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
        "c - aby wyszukac maksymalne, d - wyszukac, e - ilosc wezlow "
        "f - wysokosc, q - wyjscie\n");
 
        while(getchar () != '\n')
            continue;
 
        }
 
    return 0;
}
 
 
//WPROWADZA NOWA POZYCJE
void Insert(Drzewo *wdrzewo){
 
    printf("insert!\n");
    int i, ilosc;
    Galaz temp;
 
 
    printf("Podaj imie");
    scanf("%s", temp.dane.imie);
    printf("Podaj nazwisko");
    scanf("%s",temp.dane.nazwisko);
    printf("Podaj liczbe numerow ktore chcesz dodac");
    scanf("%d", &ilosc);
 
    for (i = 0; i < ilosc; i++)
        scanf("%d", &(temp.dane.numer[i]));
 
    temp.lewy = NULL;
    temp.prawy = NULL;
 
	if (wdrzewo->korzen == NULL)
		wdrzewo->korzen = &temp;
	else
		InOrder(wdrzewo->korzen, &temp);
    printf("Koniec Insert");
}
 
 
//REKURENCYJNIE PRZECHODZI PO DRZEWIE I DODAJE POZYCJE 
void InOrder(Galaz *root, Galaz *temp){
    printf("jest!");
    if (strcmp(temp->dane.nazwisko, root->dane.nazwisko) > 0){
        if (root->prawy == NULL)
             root->prawy = temp;
        InOrder(root->prawy, temp);
    }
    else if (strcmp(temp->dane.nazwisko, root->dane.nazwisko) < 0){
        if (root ->lewy == NULL)
            root->lewy = temp;
        InOrder(root->lewy, temp);
    }
}
 
 
//WYSZUKIWANIE POZYCJI
void Search(Drzewo *wdrzewo){
 
    char nazwisko[20];
    Galaz *temp;
 
    printf("Wpisz nazwisko do wyszukania: ");
    scanf("%s", nazwisko);
 
    Compare(wdrzewo->korzen, nazwisko, temp);
    if (temp == NULL)
        fprintf(stderr, "Brak pozycji!");
 
    printf("Imie: %s", temp->dane.imie);
 
}
 
 
//REKURENCYJNIE SPRAWDZA CZY JEST POZYCJA
void Compare(Galaz *root, const char *nazwisko, Galaz *temp){
    printf("compare!");
    if (strcmp(nazwisko, root->dane.nazwisko) > 0){
        if (root->prawy == NULL){
            temp = NULL;
            fprintf(stderr, "Brak pozycji!");
        }
        Compare(root->prawy, nazwisko, temp);
    }
    else if (strcmp(nazwisko, root->dane.nazwisko) < 0){
        if (root ->lewy == NULL){
            fprintf(stderr, "Brak pozycji!");
            temp = NULL;
        }
        Compare(root->lewy, nazwisko, temp);
    }
    else
        temp = root;
}
0

Oczywiście że nie.
Wybierz kolejną rzecz którą zignorowałeś i też zaimplementuj.

0

Jakaś podpowiedź? ;> Bo nie mogę znaleźć.

edit:
Czy chodzi o zapełnione drzewo?

0

Nie rozumiem co tak zaimplementowana funkcja:

void InOrder(Galaz *root); 

ma robić. Mógłbyś mi napisać co powinna robić?

0

A z czym InOrder ma porównywać nazwisko? nie będzie wiedział czy wejść w lewą czy w prawą gałąź.

edit:
Czy teraz jest ok? Jednak funkcja InOrder w ogóle nie jest potrzebna.

 #include <stdio.h>
#include <string.h>
#define ILOSC_NUMEROW 20        
 
typedef struct dane{
    char imie[20];
    char nazwisko[20];
    int numer[20];
}Dane;
 
typedef struct drzewo{
    struct galaz *korzen;
}Drzewo;
 
typedef struct galaz{
    struct galaz *lewy, *prawy;
    Dane dane;
}Galaz;
 
void Insert(Drzewo *wdrzewo, Dane dane);  
//void InOrder(Galaz *root);
//void SearchMin(Drzewo *drzewo);
//void SearchMax(Drzewo *drzewo);
//void Search(Drzewo *wdrzewo, const char *nazwisko); 
//void Wysokosc(Drzewo *drzewo);
//void Compare(Galaz *root, const char *nazwisko, Galaz *temp);
 
 
 
int main(){
 
    fprintf(stderr, "test");
    int liczba_wezlow = 0;
    int wysokoc = 0;
    char ch;
    Drzewo wdrzewo;
	wdrzewo.korzen = NULL;
	Dane dane;
	int ilosc, i;
 
    printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
        "c - aby wyszukac maksymalne, d - wyszukac, q - aby wyjsc\n");
 
 
    while ((ch = getchar()) != 'q'){
 
        switch (ch){
            case 'a':
				

				printf("Podaj imie");
				scanf("%s", dane.imie);
				printf("Podaj nazwisko");
				scanf("%s",dane.nazwisko);
				printf("Podaj liczbe numerow ktore chcesz dodac");
				scanf("%d", &ilosc);
 
				for (i = 0; i < ilosc; i++)
					scanf("%d", &(dane.numer[i]));
				Insert(&wdrzewo, dane);
                break;
            case 'b':
                //SearchMin(&root);
                break;
            case 'c':
                //SearchMax(&root);
                break;
            case 'd':
                //Search(&wdrzewo);
                break;
            case 'e':
                //Wysokosc(&root);
                break;
            case 'f':
                printf("%d", liczba_wezlow);
                break;
            default:
                printf("Blad w instrukcji switch!\n");
 
        }
        printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
        "c - aby wyszukac maksymalne, d - wyszukac, e - ilosc wezlow "
        "f - wysokosc, q - wyjscie\n");
 
        while(getchar () != '\n')
            continue;
 
        }
 
    return 0;
}
 
 
//WPROWADZA NOWA POZYCJE
void Insert(Drzewo *wdrzewo, Dane dane){
 
    printf("insert!\n");
    Galaz temp;
	temp.dane = dane;
 
    temp.lewy = NULL;
    temp.prawy = NULL;
 
	if (wdrzewo->korzen == NULL)
		wdrzewo->korzen = &temp;
	else{
		while (wdrzewo->korzen == NULL){
			if (strcmp(temp.dane.nazwisko, wdrzewo->korzen->dane.nazwisko) > 0)
				wdrzewo->korzen = wdrzewo->korzen->prawy;
			if (strcmp(temp.dane.nazwisko, wdrzewo->korzen->dane.nazwisko) > 0)
				wdrzewo->korzen = wdrzewo->korzen->lewy;
		}
		wdrzewo->korzen = &temp;
	}
    printf("Koniec Insert");
}
 
 
//REKURENCYJNIE PRZECHODZI PO DRZEWIE I DODAJE POZYCJE 
/*void InOrder(Galaz *root){
    printf("jest!");
    if (strcmp(temp->dane.nazwisko, root->dane.nazwisko) > 0){
        if (root->prawy == NULL)
             root->prawy = temp;
        InOrder(root->prawy, temp);
    }
    else if (strcmp(temp->dane.nazwisko, root->dane.nazwisko) < 0){
        if (root ->lewy == NULL)
            root->lewy = temp;
        InOrder(root->lewy, temp);
    }
}*/
 
 
//WYSZUKIWANIE POZYCJI
/*void Search(Drzewo *wdrzewo){
 
    char nazwisko[20];
    Galaz *temp;
 
    printf("Wpisz nazwisko do wyszukania: ");
    scanf("%s", nazwisko);
 
    Compare(wdrzewo->korzen, nazwisko, temp);
    if (temp == NULL)
        fprintf(stderr, "Brak pozycji!");
 
    printf("Imie: %s", temp->dane.imie);
 
}
 
 
//REKURENCYJNIE SPRAWDZA CZY JEST POZYCJA
void Compare(Galaz *root, const char *nazwisko, Galaz *temp){
    printf("compare!");
    if (strcmp(nazwisko, root->dane.nazwisko) > 0){
        if (root->prawy == NULL){
            temp = NULL;
            fprintf(stderr, "Brak pozycji!");
        }
        Compare(root->prawy, nazwisko, temp);
    }
    else if (strcmp(nazwisko, root->dane.nazwisko) < 0){
        if (root ->lewy == NULL){
            fprintf(stderr, "Brak pozycji!");
            temp = NULL;
        }
        Compare(root->lewy, nazwisko, temp);
    }
    else
        temp = root;
}*/
0

Czytanie ze zrozumieniem się kłania: InOrder - to sposób wyświetlenia i ma takowym pozostać.
Wstawianie do drzewa ma się odbyć w funkcji Insert
Zaś wczytywanie danych które u ciebie się robi w Insert ma się odbyć w main'ie lub np w Dane ReadDataStdin() { ... }

0

W poście wyżej, wrzuciłem kod, czy teraz jest ok?

0

Nie:

  1. co się stanie jak spróbujesz wstawić nazwisko które już było?
  2. poczytaj o dynamicznym przydzieleniu pamięci.
  3. napisz ten InOrder aby samemu móc się przekonać czy dobrze.
0

Ok, już zaczynam pisać. Jedno pytanie, czemu funkcja Insert ma dostać dane jako kopia, a nie jako wskaźnik?

0

Aby ktoś nie pomyślał że można przekazać NULL'a

0

Teraz pod opcją 'd' dałem InOrder, jednak wypisuje on tylko ostatnią pozycję... Czy dodawanie jest w końcu dobrze zrobione?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ILOSC_NUMEROW 20        
 
typedef struct dane{
    char imie[20];
    char nazwisko[20];
    int numer[20];
}Dane;
 
typedef struct drzewo{
    struct galaz *korzen;
}Drzewo;
 
typedef struct galaz{
    struct galaz *lewy, *prawy;
    Dane dane;
}Galaz;
 
void Insert(Drzewo *wdrzewo, Dane dane);  
void InOrder(Galaz *root);
//void SearchMin(Drzewo *drzewo);
//void SearchMax(Drzewo *drzewo);
//Dane *Search(Drzewo *wdrzewo, Dane *dane); 
int Duplikat(Drzewo *wdrzewo, Dane *dane);
//void Wysokosc(Drzewo *drzewo);
//void Compare(Galaz *root, const char *nazwisko, Galaz *temp);
void DodajDane(Drzewo *wdrzewo);

 
 
 
int main(){
 
    fprintf(stderr, "test");
    int liczba_wezlow = 0;
    int wysokoc = 0;
    char ch;
    Drzewo wdrzewo;
	wdrzewo.korzen = NULL;
	
 
    printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
        "c - aby wyszukac maksymalne, d - wyszukac, q - aby wyjsc\n");
 
 
    while ((ch = getchar()) != 'q'){
 
        switch (ch){
            case 'a':
				DodajDane(&wdrzewo);
                break;
            case 'b':
                //SearchMin(&root);
                break;
            case 'c':
                //SearchMax(&root);
                break;
            case 'd':
                InOrder(wdrzewo.korzen);
                break;
            case 'e':
                //Wysokosc(&root);
                break;
            case 'f':
                printf("%d", liczba_wezlow);
                break;
            default:
                printf("Blad w instrukcji switch!\n");
 
        }
        printf("Wpisz a - aby dodac dane, b - aby wyszukac minimalne, "
        "c - aby wyszukac maksymalne, d - wyszukac, e - ilosc wezlow "
        "f - wysokosc, q - wyjscie\n");
 
        while(getchar () != '\n')
            continue;
 
        }
 
    return 0;
}
 
void DodajDane(Drzewo *wdrzewo){
	Dane dane;
	int ilosc, i;

	printf("Podaj imie");
	scanf("%s", dane.imie);
	printf("Podaj nazwisko");
	scanf("%s",dane.nazwisko);
	printf("Podaj liczbe numerow ktore chcesz dodac");
	scanf("%d", &ilosc);
 
	for (i = 0; i < ilosc; i++)
		scanf("%d", &(dane.numer[i]));

	Insert(wdrzewo, dane);
}
 
//WPROWADZA NOWA POZYCJE
void Insert(Drzewo *wdrzewo, Dane dane){

    Galaz *temp = (Galaz*)malloc(sizeof(Galaz));
	temp->dane = dane;
    temp->lewy = NULL;
    temp->prawy = NULL;

	if (Duplikat(wdrzewo, &dane))
		fprintf(stderr, "Proba dodania takiej samej pozycji!");
	else{ 
		if (wdrzewo->korzen == NULL)
			wdrzewo->korzen = temp;
		else{
			while (wdrzewo->korzen == NULL){
				if (strcmp(temp->dane.nazwisko, wdrzewo->korzen->dane.nazwisko) > 0)
					wdrzewo->korzen = wdrzewo->korzen->prawy;
				if (strcmp(temp->dane.nazwisko, wdrzewo->korzen->dane.nazwisko) < 0)
					wdrzewo->korzen = wdrzewo->korzen->lewy;
			}
			wdrzewo->korzen = temp;
		}
	}
}
 
int Duplikat(Drzewo *wdrzewo, Dane *dane){

	while (wdrzewo->korzen != NULL){
		if (strcmp(dane->nazwisko, wdrzewo->korzen->dane.nazwisko) > 0)
			wdrzewo->korzen = wdrzewo->korzen->prawy;
		else if (strcmp(dane->nazwisko, wdrzewo->korzen->dane.nazwisko) < 0)
			wdrzewo->korzen = wdrzewo->korzen->lewy;
		else
			return 1;
	}
	return 0;
}
 
//REKURENCYJNIE PRZECHODZI PO DRZEWIE I DODAJE POZYCJE 
void InOrder(Galaz *root){
    printf("jest!");

	if (root->prawy != NULL)
        InOrder(root->prawy);

	printf("\n%s\n", root->dane.nazwisko);

	if (root->lewy != NULL)
        InOrder(root->lewy);
}
 
 
//WYSZUKIWANIE POZYCJI
/*Dane *Search(Drzewo *wdrzewo,const Dane *dane){
 
    while (wdrzewo->korzen == NULL){
		if (strcmp(dane->nazwisko, wdrzewo->korzen->dane.nazwisko) > 0)
			wdrzewo->korzen = wdrzewo->korzen->prawy;
		else if (strcmp(dane->nazwisko, wdrzewo->korzen->dane.nazwisko) > 0)
			wdrzewo->korzen = wdrzewo->korzen->lewy;
		else
			return 
	}
    
 
}*/
 
 
//REKURENCYJNIE SPRAWDZA CZY JEST POZYCJA
/*void Compare(Galaz *root, const char *nazwisko, Galaz *temp){
    printf("compare!");
    if (strcmp(nazwisko, root->dane.nazwisko) > 0){
        if (root->prawy == NULL){
            temp = NULL;
            fprintf(stderr, "Brak pozycji!");
        }
        Compare(root->prawy, nazwisko, temp);
    }
    else if (strcmp(nazwisko, root->dane.nazwisko) < 0){
        if (root ->lewy == NULL){
            fprintf(stderr, "Brak pozycji!");
            temp = NULL;
        }
        Compare(root->lewy, nazwisko, temp);
    }
    else
        temp = root;
}*/ 
1

A co się stanie jeżeli milion razy z rzędu spróbuję dodać już istniejące nazwisko ?

if(!Insert(wdrzewo,dane)) fprintf(stderr, "Proba dodania takiej samej pozycji!");
int Insert(Drzewo *wdrzewo,Dane dane)
  {
   int v;
   Galaz **where,*temp;

   where=&wdrzewo->korzen;   
   while(*where)
     {
      temp=*where;
      v=strcmp(dane.nazwisko,temp->dane.nazwisko);
      if(v>0) where=&temp->prawy;
      else if(v<0) where=&temp->lewy;
      else return 0;
     }
   temp=(Galaz*)malloc(sizeof(Galaz));
   temp->dane=dane;
   temp->lewy=temp->prawy=NULL;
   *where=temp;
   return 1;
  }
0

Super działa, jednak nie rozumiem zapisu z **where, czy jest on związany z tym, że korzeń nie zawsze wskazywał na sam szczyt drzewa?

0

Galaz ** - podwójny wskaźnik.

kry5 napisał(a):

... że korzeń nie zawsze wskazywał na sam szczyt drzewa ...
To jakieś majaczenia, może napisz po ludzku.

0

Żeby szukać wolnego miejsca przy dodawaniu, wskaźnikiem korzeń schodziliśmy co raz niżej, a nie powracał on na samą górę. Więc po to **where? Aby korzeń wskazywał zawszę na szczyt?

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