* called recursively.  It starts off with a starting guess for where * we want the node to go, and returns the actual result, which is * the column the node ended up in.  For example, I might want my node * to print in column 0.  After recursively evaluating everything under * the node, I may have been pushed over to node -10 ( the tree is * evaluated down the right side first ).  I return that to whoever called * this routine so it can use the nodes position to calculate where * the node in a higher row is to be placed. */int calculate_columns( tree, node, starting_guess )TREE *tree;int node;int starting_guess;{    int next_node;    int right_side;    int left_side;/* * The first thing I check is to see if the node on my immediate right has * already been placed.  If it has, I need to make sure that I am at least * 4 columns to the right of it.  This allows me to print 3 characters plus * leave a blank space between us. */    next_node = positions[ node ].next_member;    if ( next_node != -1 ) {        if ( positions[ next_node ].column < ( starting_guess + 4 ) )            starting_guess = positions[ next_node ].column - 4;    }    if ( tree->nodes[ node ].child_is_leaf ) {        positions[ node ].column = starting_guess;        return( starting_guess );    }/* * After I have adjusted my starting guess, I calculate the actual position * of the right subtree of this node.  I pass it a guess for a starting * node based on my starting guess.  Naturally, what comes back may be * moved over quite a bit. */    right_side = calculate_columns( tree, tree->nodes[ node ].child, starting_guess + 2 );/* * After figuring out where the right side lands, I do the same for the * left side.  After doing the right side, I have a pretty good guess where * the starting column for the left side might go, so I can pass it a good * guess for a starting column. */    left_side = calculate_columns( tree, tree->nodes[ node ].child + 1, right_side - 4 );/* * Once I know where the starting column for the left and right subtrees * are going to be for sure, I know where this node should go, which is * right in the middle between the two.  I calcluate the column, store it, * then return the result to whoever called me. */    starting_guess = ( right_side + left_side ) / 2;    positions[ node ].column = starting_guess;    return( starting_guess );}int find_minimum_column( tree, node, max_row )TREE *tree;int node;int max_row;{    int min_right;    int min_left;    if ( tree->nodes[ node ].child_is_leaf || max_row == 0 )        return( positions[ node ].column );    max_row--;    min_right = find_minimum_column( tree, tree->nodes[ node ].child + 1, max_row );    min_left = find_minimum_column( tree, tree->nodes[ node ].child, max_row );    if ( min_right < min_left )        return( min_right );    else        return( min_left );}/* * Once the columns of each node have been calculated, I go back and rescale * the columns to be actual printer columns.  In this particular program, * each node takes three characters to print, plus one space to keep nodes * separate.  We take advantage of the fact that every node has at least one * logical column between it and the ajacent node, meaning that we can space * nodes only two physical columns apart.  The spacing here consists of * rescaling each column so that the smallest column is at zero, then * multiplying by two to get a physical printer column. */void rescale_columns( factor )int factor;{    int i;    int node;/* * Once min is known, we can rescale the tree so that column min is * pushed over to column 0, and each logical column is set to be two * physical columns on the printer. */    for ( i = 0 ; i < 30 ; i++ ) {        if ( rows[ i ].first_member == -1 )            break;        node = rows[ i ].first_member;        do {            positions[ node ].column -= factor;            node = positions[ node ].next_member;        } while ( node != -1 );    }}/* * print_tree is called after the row and column of each node have been * calculated.  It just calls the four workhorse routines that are * responsible for printing out the four elements that go on each row. * At the top of the row are the connecting lines hooking the tree * together.  On the next line of the row are the node numbers.  Below * them are the weights, and finally the symbol, if there is one. */void print_tree( tree, first_row, last_row )TREE *tree;int first_row;int last_row;{    int row;    for ( row = first_row ; row <= last_row ; row++ ) {        if ( rows[ row ].first_member == -1 )            break;        if ( row > first_row )            print_connecting_lines( tree, row );        print_node_numbers( row );        print_weights( tree, row );        print_symbol( tree, row );    }}/* * Printing the connecting lines means connecting each pair of nodes. * I use the IBM PC character set here.  They can easily be replaced * with more standard alphanumerics. */#ifndef ALPHANUMERIC#define LEFT_END  218#define RIGHT_END 191#define CENTER    193#define LINE      196#define VERTICAL  179#else#define LEFT_END  '+'#define RIGHT_END '+'#define CENTER    '+'#define LINE      '-'#define VERTICAL  '|'#endifvoid print_connecting_lines( tree, row )TREE *tree;int row;{    int current_col;    int start_col;    int end_col;    int center_col;    int node;    int parent;    current_col = 0;    node = rows[ row ].first_member;    while ( node != -1 ) {        start_col = positions[ node ].column + 2;        node = positions[ node ].next_member;        end_col = positions[ node ].column + 2;        parent = tree->nodes[ node ].parent;        center_col = positions[ parent ].column;        center_col += 2;        for ( ; current_col < start_col ; current_col++ )            putc( ' ', stdout );        putc( LEFT_END, stdout );        for ( current_col++ ; current_col < center_col ; current_col++ )            putc( LINE, stdout );        putc( CENTER, stdout );        for ( current_col++; current_col < end_col ; current_col++ )            putc( LINE, stdout );        putc( RIGHT_END, stdout );        current_col++;        node = positions[ node ].next_member;    }    printf( "\n" );}/* * Printing the node numbers is pretty easy. */void print_node_numbers( row )int row;{    int current_col;    int node;    int print_col;    current_col = 0;    node = rows[ row ].first_member;    while ( node != -1 ) {        print_col = positions[ node ].column + 1;        for ( ; current_col < print_col ; current_col++ )            putc( ' ', stdout );        printf( "%03d", node );        current_col += 3;        node = positions[ node ].next_member;    }    printf( "\n" );}/* * Printing the weight of each node is easy too. */void print_weights( tree, row )TREE *tree;int row;{    int current_col;    int print_col;    int node;    int print_size;    int next_col;    char buffer[ 10 ];    current_col = 0;    node = rows[ row ].first_member;    while ( node != -1 ) {        print_col = positions[ node ].column + 1;        sprintf( buffer, "%u", tree->nodes[ node ].weight );        if ( strlen( buffer ) < 3 )            sprintf( buffer, "%03u", tree->nodes[ node ].weight );        print_size = 3;        if ( strlen( buffer ) > 3 ) {            if ( positions[ node ].next_member == -1 )                print_size = strlen( buffer );            else {                next_col = positions[ positions[ node ].next_member ].column;                if ( ( next_col - print_col ) > 6 )                    print_size = strlen( buffer );                else {                    strcpy( buffer, "---" );                    print_size = 3;                }            }        }        for ( ; current_col < print_col ; current_col++ )            putc( ' ', stdout );        printf( buffer );        current_col += print_size;        node = positions[ node ].next_member;    }    printf( "\n" );}/* * Printing the symbol values is a little more complicated.  If it is a * printable symbol, I print it between simple quote characters.  If * it isn't printable, I print a hex value, which also only takes up three * characters.  If it is an internal node, it doesn't have a symbol, * which means I just print the vertical line.  There is one complication * in this routine.  In order to save space, I check first to see if * any of the nodes in this row have a symbol.  If none of them have * symbols, we just skip this part, since we don't have to print the * row at all. */void print_symbol( tree, row )TREE *tree;int row;{    int current_col;    int print_col;    int node;    current_col = 0;    node = rows[ row ].first_member;    while ( node != -1 ) {        if ( tree->nodes[ node ].child_is_leaf )            break;        node = positions[ node ].next_member;    }    if ( node == -1 )        return;    node = rows[ row ].first_member;    while ( node != -1 ) {        print_col = positions[ node ].column + 1;        for ( ; current_col < print_col ; current_col++ )            putc( ' ', stdout );        if ( tree->nodes[ node ].child_is_leaf ) {            if ( isprint( tree->nodes[ node ].child ) )                printf( "'%c'", tree->nodes[ node ].child );            else if ( tree->nodes[ node ].child == END_OF_STREAM )                printf( "EOF" );            else if ( tree->nodes[ node ].child == ESCAPE )                printf( "ESC" );            else                printf( "%02XH", tree->nodes[ node ].child );        } else            printf( " %c ", VERTICAL );        current_col += 3;        node = positions[ node ].next_member;    }    printf( "\n" );}/************************** End of AHUFF.C ****************************/