|
<![CDATA[
#define K 3
/*** Split the largest, merge the two smallest ***/
tree checkrots( t )
tree t;
{ tree R[K], P[K+1];
int i, j, maxwt, minwt;
if( wt(t) <= K ) return( t );
if( wt( t->left ) < wt( t-> right ) )
{ R[0] = t; R[1] = t->right; P[0] = t->left;
P[1] = R[1]->left; P[2] = R[1]->right; }
else { R[0] = t->left; R[1] = t; P[0] = R[0]->left;
P[1] = R[0]->right; P[2] = t->right; }
/*** Expand ***/
for( i=2; i<K; i++ ) {
for( maxwt=0,j=1; j<=i; j++ )
if( wt(P[maxwt]) < wt(P[j]) ) maxwt = j;
for( j=i-1; j >= maxwt; j-- )
{ P[j+2] = P[j+1]; R[j+1] = R[j]; }
R[maxwt] = P[maxwt];
P[maxwt] = R[maxwt]->left; P[maxwt+1] = R[maxwt]->right;
}
/*** Merge the two smallest neighbours ***/
for( i=K; i>0; i-- ) {
for( minwt=0,j=1; j<i; j++ )
if( wt(P[minwt])+wt(P[minwt+1]) > wt(P[j])+wt(P[j+1]) )
minwt = j;
R[minwt]->left = P[minwt]; R[minwt]->right = P[minwt+1];
R[minwt]->weight = wt(P[minwt]) + wt(P[minwt+1]);
P[minwt] = R[minwt];
for( j=minwt+1; j<i; j++ )
{ R[j-1] = R[j]; P[j] = P[j+1]; }
}
return( P[0] );
}
]]> |
![[Home]](../../images/home_g.gif)
![[Contents]](../../images/contents_g.gif)
![[Chapter]](../../images/chapter_g.gif)
![[Previous Algorithm]](../../images/prevalg_g.gif)
![[Next Algorithm]](../../images/nextalg_g.gif)
C source (34155.chckr.c) 