tree->nodes[ current_node ].weight++;        for ( new_node = current_node ; new_node > ROOT_NODE ; new_node-- )            if ( tree->nodes[ new_node - 1 ].weight >=                 tree->nodes[ current_node ].weight )                break;        if ( current_node != new_node ) {            swap_nodes( tree, current_node, new_node );            current_node = new_node;        }        current_node = tree->nodes[ current_node ].parent;    }}/* * Rebuilding the tree takes place when the counts have gone too * high.  From a simple point of view, rebuilding the tree just means that * we divide every count by two.  Unfortunately, due to truncation effects, * this means that the tree's shape might change.  Some nodes might move * up due to cumulative increases, while others may move down. */void RebuildTree( tree )TREE *tree;{    int i;    int j;    int k;    unsigned int weight;/* * To start rebuilding the table,  I collect all the leaves of the Huffman * tree and put them in the end of the tree.  While I am doing that, I * scale the counts down by a factor of 2. */    printf( "R" );    j = tree->next_free_node - 1;    for ( i = j ; i >= ROOT_NODE ; i-- ) {        if ( tree->nodes[ i ].child_is_leaf ) {            tree->nodes[ j ] = tree->nodes[ i ];            tree->nodes[ j ].weight = ( tree->nodes[ j ].weight + 1 ) / 2;            j--;        }    }/* * At this point, j points to the first free node.  I now have all the * leaves defined, and need to start building the higher nodes on the * tree. I will start adding the new internal nodes at j.  Every time * I add a new internal node to the top of the tree, I have to check to * see where it really belongs in the tree.  It might stay at the top, * but there is a good chance I might have to move it back down.  If it * does have to go down, I use the memmove() function to scoot everyone * bigger up by one node.  Note that memmove() may have to be change * to memcpy() on some UNIX systems.  The parameters are unchanged, as * memmove and  memcpy have the same set of parameters. */    for ( i = tree->next_free_node - 2 ; j >= ROOT_NODE ; i -= 2, j-- ) {        k = i + 1;        tree->nodes[ j ].weight = tree->nodes[ i ].weight +                                  tree->nodes[ k ].weight;        weight = tree->nodes[ j ].weight;        tree->nodes[ j ].child_is_leaf = FALSE;        for ( k = j + 1 ; weight < tree->nodes[ k ].weight ; k++ )            ;        k--;        memmove( &tree->nodes[ j ], &tree->nodes[ j + 1 ],                 ( k - j ) * sizeof( struct node ) );        tree->nodes[ k ].weight = weight;        tree->nodes[ k ].child = i;        tree->nodes[ k ].child_is_leaf = FALSE;    }/* * The final step in tree reconstruction is to go through and set up * all of the leaf and parent members.  This can be safely done now * that every node is in its final position in the tree. */    for ( i = tree->next_free_node - 1 ; i >= ROOT_NODE ; i-- ) {        if ( tree->nodes[ i ].child_is_leaf ) {            k = tree->nodes[ i ].child;            tree->leaf[ k ] = i;        } else {            k = tree->nodes[ i ].child;            tree->nodes[ k ].parent = tree->nodes[ k + 1 ].parent = i;        }    }}/* * Swapping nodes takes place when a node has grown too big for its * spot in the tree.  When swapping nodes i and j, we rearrange the * tree by exchanging the children under i with the children under j. */void swap_nodes( tree, i, j )TREE *tree;int i;int j;{    struct node temp;    if ( tree->nodes[ i ].child_is_leaf )        tree->leaf[ tree->nodes[ i ].child ] = j;    else {        tree->nodes[ tree->nodes[ i ].child ].parent = j;        tree->nodes[ tree->nodes[ i ].child + 1 ].parent = j;    }    if ( tree->nodes[ j ].child_is_leaf )        tree->leaf[ tree->nodes[ j ].child ] = i;    else {        tree->nodes[ tree->nodes[ j ].child ].parent = i;        tree->nodes[ tree->nodes[ j ].child + 1 ].parent = i;    }    temp = tree->nodes[ i ];    tree->nodes[ i ] = tree->nodes[ j ];    tree->nodes[ i ].parent = temp.parent;    temp.parent = tree->nodes[ j ].parent;    tree->nodes[ j ] = temp;}/* * Adding a new node to the tree is pretty simple.  It is just a matter * of splitting the lightest-weight node in the tree, which is the highest * valued node.  We split it off into two new nodes, one of which is the * one being added to the tree.  We assign the new node a weight of 0, * so the tree doesn't have to be adjusted.  It will be updated later when * the normal update process occurs.  Note that this code assumes that * the lightest node has a leaf as a child.  If this is not the case, * the tree would be broken. */void add_new_node( tree, c )TREE *tree;int c;{    int lightest_node;    int new_node;    int zero_weight_node;    lightest_node = tree->next_free_node - 1;    new_node = tree->next_free_node;    zero_weight_node = tree->next_free_node + 1;    tree->next_free_node += 2;    tree->nodes[ new_node ] = tree->nodes[ lightest_node ];    tree->nodes[ new_node ].parent = lightest_node;    tree->leaf[ tree->nodes[ new_node ].child ] = new_node;    tree->nodes[ lightest_node ].child         = new_node;    tree->nodes[ lightest_node ].child_is_leaf = FALSE;    tree->nodes[ zero_weight_node ].child           = c;    tree->nodes[ zero_weight_node ].child_is_leaf   = TRUE;    tree->nodes[ zero_weight_node ].weight          = 0;    tree->nodes[ zero_weight_node ].parent          = lightest_node;    tree->leaf[ c ] = zero_weight_node;}/* * All the code from here down is concerned with printing the tree. * Printing the tree out is basically a process of walking down through * all the nodes, with each new node to be printed getting nudged over * far enough to make room for everything that has come before. *//* * This array is used to keep track of all the nodes that are in a given * row.  The nodes are kept in a linked list.  This array is used to keep * track of the first member.  The subsequent members will be found in * a linked list in the positions[] array. */struct row {    int first_member;    int count;} rows[ 32 ];/* * The positions[] array is used to keep track of the row and column of each * node in the tree.  The next_member element points to the next node * in the row for the given node.  The column is calculated on the fly, * and represents the actual column that a given number is to be printed in. * Note that the column for a node is not an actual column on the page.  For * purposes of analysis, it is assumed that each node takes up exactly one * column.  So, if printing out the actual values in a node takes up for * spaces on the printed page, we might want to allocate five physical print * columns for each column in the array. */struct location {    int row;    int next_member;    int column;} positions[ NODE_TABLE_COUNT ];/* * This is the main routine called to print out a Huffman tree.  It first * calls the print_codes function, which prints out the binary codes * for each symbol.  After that, it calculates the row and column that * each node will be printed in, then prints the tree out.  This code * is not documented in the book, since it is essentially irrelevant to * the data compression process.  However, it is nice to be able to * print out the tree. */void PrintTree( tree )TREE *tree;{    int i;    int min;    print_codes( tree );    for ( i = 0 ; i < 32 ; i++ ) {        rows[ i ].count = 0;        rows[ i ].first_member = -1;    }    calculate_rows( tree, ROOT_NODE, 0 );    calculate_columns( tree, ROOT_NODE, 0 );    min = find_minimum_column( tree, ROOT_NODE, 31 );    rescale_columns( min );    print_tree( tree, 0, 31 );}/* * This routine is called to print out the Huffman code for each symbol. * The real work is done by the print_code routine, which racks up the * bits and puts them out in the right order. */void print_codes( tree )TREE *tree;{    int i;    printf( "\n" );    for ( i = 0 ; i < SYMBOL_COUNT  ; i++ )        if ( tree->leaf[ i ] != -1 ) {             if ( isprint( i ) )                 printf( "%5c: ", i );             else                 printf( "<%3d>: ", i );            printf( "%5u", tree->nodes[ tree->leaf[ i ] ].weight );            printf( " " );            print_code( tree, i );            printf( "\n" );        }}/* * print_code is a workhorse routine that prints out the Huffman code for * a given symbol.  It ends up looking a lot like EncodeSymbol(), since * it more or less has to do the same work.  The major difference is that * instead of calling OutputBit, this routine calls putc, with a character * argument. */void print_code( tree, c )TREE *tree;int c;{    unsigned long code;    unsigned long current_bit;    int code_size;    int current_node;    int i;    code = 0;    current_bit = 1;    code_size = 0;    current_node = tree->leaf[ c ];    while ( current_node != ROOT_NODE ) {        if ( current_node & 1 )            code |= current_bit;        current_bit <<= 1;        code_size++;        current_node = tree->nodes[ current_node ].parent;    };    for ( i = 0 ; i < code_size ; i++ ) {        current_bit >>= 1;        if ( code & current_bit )            putc( '1', stdout );        else            putc( '0', stdout );    }}/* * In order to print out the tree, I need to calculate the row and column * where each node will be printed.  The rows are easier than the columns, * and I do them first.  It is easy to keep track of what row a node is * in as I walk through the tree.  As I walk through the tree, I also keep * track of the order the nodes appear in a given row, by adding them to * a linked list in the proper order.  After calculate_rows() has been * recursively called all the way through the tree, I have a linked list of * nodes for each row.  This same linked list is used later to calculate * which column each node appears in. */void calculate_rows( tree, node, level )TREE *tree;int node;int level;{    if ( rows[ level ].first_member == -1 ) {        rows[ level ].first_member = node;        rows[ level ].count = 0;        positions[ node ].row = level;        positions[ node ].next_member = -1;    } else {        positions[ node ].row = level;        positions[ node ].next_member = rows[ level ].first_member;        rows[ level ].first_member = node;        rows[ level ].count++;    }    if ( !tree->nodes[ node ].child_is_leaf ) {        calculate_rows( tree, tree->nodes[ node ].child, level + 1 );        calculate_rows( tree, tree->nodes[ node ].child + 1, level + 1 );    }}/* * After I know which row each of the nodes is in, I can start the * hard work, which is calculating the columns.  This routine gets