This is the code form section 6.5 of K&R2:
struct tnode
{
char *word;
int count;
struct tnode *left;
struct tnode *right;
};
struct tnode *add_node( struct tnode *p, char *w )
{
int cond;
if ( !p )
{
p = talloc();
p->word = strdup( w );
p->count = 1;
p->left = p->right = NULL;
}
else if( !(cond = strcmp( w, p->word )) )
{
p->count++;
}
else if( cond < 0 )
{
p->left = add_node( p->left, w );
}
else if( cond 0 )
{
p->right = add_node( p->right, w );
}
return p;
}
/* aloocate memory for new node */
struct tnode *talloc( void )
{
return malloc( sizeof( struct tnode ) );
}
for input:
"Now is the time for all good men to come to the aid
of their party"
This produces a tree like this:
now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come
This is an unbalanced-tree, where balanced factor is:
(1 - 3) = -2
balance factor = (height of right-subtree) - (height of left-subtree)
right-subtree starts with word "the" which has only 1 child-node.
left-subtree starts with "is" and it has 3 nodes
Can I convert this binary-tree into an AVL tree which has a balance factor
of 1, 0 or -1 ? I am not able to change the code to do that
conversion.
--
my email ID is @ the above blog.
just check the "About Myself" page :)
struct tnode
{
char *word;
int count;
struct tnode *left;
struct tnode *right;
};
struct tnode *add_node( struct tnode *p, char *w )
{
int cond;
if ( !p )
{
p = talloc();
p->word = strdup( w );
p->count = 1;
p->left = p->right = NULL;
}
else if( !(cond = strcmp( w, p->word )) )
{
p->count++;
}
else if( cond < 0 )
{
p->left = add_node( p->left, w );
}
else if( cond 0 )
{
p->right = add_node( p->right, w );
}
return p;
}
/* aloocate memory for new node */
struct tnode *talloc( void )
{
return malloc( sizeof( struct tnode ) );
}
for input:
"Now is the time for all good men to come to the aid
of their party"
This produces a tree like this:
now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come
This is an unbalanced-tree, where balanced factor is:
(1 - 3) = -2
balance factor = (height of right-subtree) - (height of left-subtree)
right-subtree starts with word "the" which has only 1 child-node.
left-subtree starts with "is" and it has 3 nodes
Can I convert this binary-tree into an AVL tree which has a balance factor
of 1, 0 or -1 ? I am not able to change the code to do that
conversion.
--
my email ID is @ the above blog.
just check the "About Myself" page :)
Comment