Mam drzewo w którym każdy element może mieć do 10 dzieci. Muszę podać głębokość elementu o id=2, w jaki sposób to zrobić? Struktura wygląda tak:
struct node {
int id;
struct node* dziecko[10];
};
Mam drzewo w którym każdy element może mieć do 10 dzieci. Muszę podać głębokość elementu o id=2, w jaki sposób to zrobić? Struktura wygląda tak:
struct node {
int id;
struct node* dziecko[10];
};
Jakie to drzewo?
Zrównoważone jest?
Jak nie wiesz nic o drzewie, to możesz brutalnie szukać wszerz lub w głąb, dla każdego elementu.
Drzewa są różne, napisałem rekurencyjną funkcję która zwraca wskaźnik na element który ma dane id, ale nie wiem w którym miejscu zwiększać licznik głębokości.
struct node* find(struct node *root, char id) {
struct node *current=root;
if(current->id==id) {
wskaznik=current;
}
else {
for(int i=0; i<10; i++) {
if(current->dziecko[i]!=NULL) {
wskaznik=find(current->dziecko[i],id);
}
}
}
return wskaznik;
}
@panstudent: póki co nie widzę żadnego licznika.
Twoja funkcja musi zwrócić dwie wartości – wskaźnik na węzeł pasujący danymi do ID oraz liczbę określającą stopień zagłębienia. Obie te dane możesz przekazać na zewnątrz poprzez parametry, możesz też jedną zwrócić przez parametr a drugą w rezultacie funkcji, albo obie dane w rezultacie (tu potrzebna pomocnicza struktura).
Najpierw wybierz sobie sposób, a jak to zrobisz, to pomyślimy o rozwiązaniu problemu.
int glebokosc=1; //zmienna globalna
struct node* findtwo(struct node *root) {
int test=0;
struct node *current=root;
if(current->id==2) {
wskaznik=current;
}
else {
for(int i=0; i<10; i++) {
if(current->dziecko[i]!=NULL) {
wskaznik=findtwo(current->dziecko[i]);
test=1;
}
}
if(test==1)
glebokosc++;
}
return wskaznik;
}
Zmienne globalne nie istnieją po to, aby używać ich wszędzie tam, gdzie nie potrafi się napisać sensownego kodu.
Zresztą, tych globali w Twoim kodzie jest więcej – gdzie deklaracja wskaznik
? Poza tym, dlaczego piszesz kod po angielsku i wtrącasz do niego polskie identyfikatory? Nie wiesz, że dziecko
to child
, że wskaznik
to pointer
/ptr
i że glebokosc
to depth
? Użyj translatora, jeśli nie wiesz.
Pisz sobie jak chcesz, w każdym razie spróbuj tego:
struct node* find_two(struct node *current, int curr_depth)
{
if(current->id == 2)
{
depth = curr_depth;
return current;
}
else
{
struct node *child;
for(int i = 0; i < 10; i++)
{
if(current->child[i] != null)
{
child = find_two(current->child[i], curr_depth + 1);
if(child != null)
return child;
}
}
return null;
}
}
Przykładowe wywołanie:
struct node *result = find_two(root, 1);
Mogłem coś z tymi gwiazdkami pomieszać – rzadko piszę cokolwiek w C, w sumie głównie na potrzeby forum.
Dziękuję za pomoc, już wszystko działa. W przyszłości będę się starał nie mieszać polskich i angielskich nazw. Wesołych Świąt! ;)