#include <stdio.h>
#include <graph.h>
/* tree struct */
typedef struct tnode { /* Standard binary tree node for storage */
struct tnode *left, *right; /* of integer values */
int num;
} TREENODE;
/* Display printing/spacing constants */
#define NUMWID 4 /* Width of a number shown in a binary tree */
#define WIDSTR "%4d\n" /* Format string for number in binary tree */
#define ROWSPC 3 /* Row spacing in showing binary tree */
/* Function prototypes */
static
int width(TREENODE *); /* Determine width of a subtree */
void printtree(TREENODE *), /* Print contents of tree */
showtree(TREENODE *, int, int); /* Draw the tree */
/* Recursive function to graphically display the tree.
Usage: void showtree(node, r, c)
TREENODE *node; /* Pointer to a local root
int r, /* Row coordinate to print the node value
c; /* Column coordinate to print the node value
Returns: Nothing
*/
void showtree(node, r, c)
TREENODE *node;
int r, c;
{
if (node != NULL) {
/* Position graphics line pointer only if within an 80 x 25 screen */
if ((r > 0) && (r < 26) && (c > 0) && (c < 81)) {
_lineto((c << 3) + 13, (r << 3) - 10);
_moveto((c << 3) + 13, r << 3);
}
/* Show left subtree */
if (node->left)
showtree(node->left, r + ROWSPC, c - (NUMWID + width(node->left->right)));
/* Print value only if within 80 x 25 screen */
if ((r > 0) && (r < 26) && (c > 0) && (c < 76)) {
_settextposition(r, c);
printf("%4d", node->num);
_moveto((c << 3) + 13, r << 3);
}
/* Show right subtree */
if (node->right)
showtree(node->right, r + ROWSPC, c + NUMWID + width(node->right->left));
}
}
/* Recursive function to determine the width of a local root. Used in the
graphic display of the tree.
Usage: int width(node)
TREENODE *node; /* Pointer to a local root
Returns: The width of the local root.
*/
int width(node)
TREENODE *node;
{
return(node != NULL ? NUMWID + width(node->left) + width(node->right) : 0);
}
/* Recursive function to perform a simple traversal of the tree in numerical
order while printing the node values.
Usage: void printtree(node)
TREENODE *node; /* A pointer to a local root
Returns: Nothing
*/
void printtree(node)
TREENODE *node;
{
if (node != NULL) {
printtree(node->left);
printf("%d\n", node->num);
printtree(node->right);
}
}