evo moje rješenje, djeluje mi točno...
ideja je proći kroz stablo i sve čvorove koji imaju k listova zapamtiti u niz.
zatim taj niz uspoređivati fjom usporedi, koja vrati 0 ako su jednaki, a nešto veće od 0 ako nisu.
[code:1]int broj_listova( node i, BTREE T )
{
if( i == LAMBDA )
return 0;
if( LEFT_CHILD(i,T) == LAMBDA && RIGHT_CHILD(i,T) == LAMBDA )
return 1;
return broj_listova(LEFT_CHILD(i,T),T) + broj_listova(RIGHT_CHILD(i,T),T);
}
void prodji_i_zapamti( node i, BTREE T, node* niz, int* duljina, int k )
{
if( i == LAMBDA )
return;
if( broj_listova(i,T) == k )
{
niz[*duljina] = i;
(*duljina)++;
}
prodji_i_zapamti(LEFT_CHILD(i,T),T,niz,duljina,k);
prodji_i_zapamti(RIGHT_CHILD(i,T),T,niz,duljina,k);
}
int usporedi( node a, node b, BTREE T )
{
if( a == LAMBDA && b == LAMBDA )
return 0;
if( LABEL(a,T) != LABEL(b,T) )
return 1;
return usporedi(LEFT_CHILD(a,T),LEFT_CHILD(b,T),T) + usporedi(RIGHT_CHILD(a,T),RIGHT_CHILD(b,T),T);
}
int listovi(BTREE T, int k)
{
node a[MAX];
int n, i, j;
prodji_i_zapamti(ROOT(T),T,a,&n,k);
for( i = 0; i < n-1; i++ )
for( j = i+1; j < n; j++ )
if( usporedi(a[i],a[j],T) )
return 1;
return 0;
}[/code:1]
evo moje rješenje, djeluje mi točno...
ideja je proći kroz stablo i sve čvorove koji imaju k listova zapamtiti u niz.
zatim taj niz uspoređivati fjom usporedi, koja vrati 0 ako su jednaki, a nešto veće od 0 ako nisu.
Kod: | int broj_listova( node i, BTREE T )
{
if( i == LAMBDA )
return 0;
if( LEFT_CHILD(i,T) == LAMBDA && RIGHT_CHILD(i,T) == LAMBDA )
return 1;
return broj_listova(LEFT_CHILD(i,T),T) + broj_listova(RIGHT_CHILD(i,T),T);
}
void prodji_i_zapamti( node i, BTREE T, node* niz, int* duljina, int k )
{
if( i == LAMBDA )
return;
if( broj_listova(i,T) == k )
{
niz[*duljina] = i;
(*duljina)++;
}
prodji_i_zapamti(LEFT_CHILD(i,T),T,niz,duljina,k);
prodji_i_zapamti(RIGHT_CHILD(i,T),T,niz,duljina,k);
}
int usporedi( node a, node b, BTREE T )
{
if( a == LAMBDA && b == LAMBDA )
return 0;
if( LABEL(a,T) != LABEL(b,T) )
return 1;
return usporedi(LEFT_CHILD(a,T),LEFT_CHILD(b,T),T) + usporedi(RIGHT_CHILD(a,T),RIGHT_CHILD(b,T),T);
}
int listovi(BTREE T, int k)
{
node a[MAX];
int n, i, j;
prodji_i_zapamti(ROOT(T),T,a,&n,k);
for( i = 0; i < n-1; i++ )
for( j = i+1; j < n; j++ )
if( usporedi(a[i],a[j],T) )
return 1;
return 0;
} |
|