|
<![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) 