Tak jak w temacie mauszę napisać funkcję zwracająca wskaźnik do korzenia najwyższego poddrzewa, które ma jednakową liczbę węzłów w obu swoich poddrzewach.
Wiem jak napisać funkcje zliczające wysokość i liczbę węzłów, ale nie potrafię użyć tego w funkcji.
Chciałabym to zrozumieć i wiedzieć krok po kroku, co funkcja powinna sprawdzać i jakie parametry zmieniać. Będę wdzięczna za instrukcje, albo pseudokod ;)
0
0
Napisz funkcje która zwraca dwie rzeczy:
- wysokość drzewa.
- ilość węzłów w nim
0
mam funkcje zliczającą liczbę węzłów i osobno liczącą wysokość, ale nie potrafię ich połączyć w jedną ;(
0
Co znaczy "nie potrafię ich połączyć"? Rozumiesz cokolwiek w tych funkcjach?
void spec(node *n,unsigned *height,unsigned *count,unsigned *max,node **ret)
{
if(node)
{
unsigned heightLf,heightRt,countLf,countRt;
spec(n->left,heightLf,countLf,max,ret);
spec(n->right,heightRt,countRt,max,ret);
*height=(heightLf>heightRt?heightLf:heightRt)+1;
*count=countLf+countRt+1;
if((countLf==countRt)&&(*max<*height))
{
*max=*height;
*ret=node;
}
}
else *height=*count=0;
}
0
MałaMi napisał(a):
mam funkcje zliczającą liczbę węzłów i osobno liczącą wysokość, ale nie potrafię ich połączyć w jedną ;(
Pokaż te funkcje.
0
Napisałam coś takiego, ale zwraca mi lewego syna, zamiast tego, co powinien zwracac, kombinuję na wszelkie sposoby, ale nie wiem jak uzyskać odpowiedni wskaźnik, jakieś wskazówki?
Tree * point(Tree *t, int * wys, int * ilwezlow)
{
if(t==NULL)
{
*wys=0;
*ilwezlow=0;
return NULL;
}
int l_wys, p_wys, l_ilwezlow, p_ilwezlow;
Tree *l=point(t->left, & l_wys, & l_ilwezlow);
Tree *p=point(t->right, & p_wys, & p_ilwezlow);
if(NumberOfNodes(l)==NumberOfNodes(p))
{
*ilwezlow=NumberOfNodes(l)+NumberOfNodes(p)+1;
if(l_wys>p_wys)
{
*wys=l_wys+1;
}
else
{
*wys=p_wys+1;
}
return t;
}
if(l_wys>p_wys)
{
*wys=l_wys;
*ilwezlow=NumberOfNodes(l);
return point(l, &wys, &ilwezlow);
}
else
{
*wys=p_wys;
*ilwezlow=NumberOfNodes(p);
return point(p, &wys, &ilwezlow);
}
}
0
Tamto wyżej napisałam wzorując się na czymś podobnym z lekcji (najwyższe pełne poddrzewo), ale nie radzę sobie z referencją.
A to są funkcje, które mam z wysokością i liczbą węzłów:
int NumberOfNodes(Tree* t)
{
if(t==NULL)
{
return 0;
}
if(t->left==NULL && t->right==NULL)
{
return 1;
}
else
{
return((NumberOfNodes(t->left))+(NumberOfNodes(t->right))+1);
}
}
int HeightOfTree(Tree* t)
{
int hl, hp;
if(t==NULL)
{
return 0;
}
else
{
hl=HeightOfTree(t->left);
hp=HeightOfTree(t->right);
if(hl>hp)
{
return(hl+1);
}
else
{
return(hp+1);
}
}
}