/* Program by Bruce Terry
Written 04/14/1989
Revised 11/02/1990
Program designed to illustrate the technique of optimizing a binary tree
without using AVL or similar algorithims.
Designed for the Microsoft C 6.0 compiler.
Compatible with Microsoft QuickC 2.x
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
#include <graph.h>
#include <bios.h>
/* Global structs */
typedef struct tnode { /*Standard binary tree node */
/* Must put left and right child node pointers first */
struct tnode *left, *right;
int num;
} TREENODE;
/* Function prototypes */
TREENODE *addnode(TREENODE *, int); /* Add to tree */
int getnum(void); /* Get a number for action */
void keypause(void), /* Allow for pause */
main(void); /* Declaration of main */
extern
void *optimize(void *); /* Optimize a tree */
extern
void printtree(TREENODE *), /* Print contents of tree */
showtree(TREENODE *, int, int); /* Draw the tree */
void main()
{
int num, /* Number stored in tree */
choice; /* Menu choice */
TREENODE *root = NULL; /* Root of tree */
do {
_clearscreen(_GCLEARSCREEN);
puts("1)Add to tree\n2)Optimize tree\n3)Print tree\n4)Draw tree\n5)End");
switch(choice = getch()) {
case '1': /* Add number to tree */
num = getnum();
root = addnode(root, num);
break;
case '2': /* Optimize the tree */
root = (TREENODE *) optimize((void *) root);
break;
case '3': /* Print contents of tree */
_clearscreen(_GCLEARSCREEN);
_settextposition(1, 1);
puts("Nodes of binary tree in numerical order\n\n");
printtree(root);
keypause();
break;
case '4': /* Draw tree in 640 x 200 CGA screen */
_setvideomode(_HRESBW);
_clearscreen(_GCLEARSCREEN);
_moveto(333, 6);
showtree(root, 2, 40);
_settextposition(24, 1);
keypause();
_setvideomode(_DEFAULTMODE);
break;
}
} while (choice != '5');
_clearscreen(_GCLEARSCREEN);
puts("Program terminated.\n");
}
/* Function to retrieve an integer value that will be stored in the tree.
Usage: int getnum(void);
Returns: The number given.
*/
int getnum()
{
int number; /* The number entered*/
_clearscreen(_GCLEARSCREEN);
do {
while (_bios_keybrd(_KEYBRD_READY))
_bios_keybrd(_KEYBRD_READ);
fputs("Enter an integer for storage: ", stdout);
} while (scanf("%d", &number) == 0);
return(number);
}
/* Recursive function to add an integer to the binary tree.
Usage: TREENODE *addnode(node, number)
TREENODE *node; /* Pointer to a local root
int number; /* Number to add
Returns: A pointer to the updated local root.
*/
TREENODE *addnode(node, number)
TREENODE *node;
int number;
{
if (node == NULL) {
if ((node = ((TREENODE *) malloc(sizeof(TREENODE)))) == NULL) {
fputs("Error in allocation\n", stderr);
exit(1);
}
node->num = number;
node->left = node->right = NULL;
}
else
if (number < node->num)
node->left = addnode(node->left, number);
else
if (number > node->num)
node->right = addnode(node->right, number);
return(node);
}
/* Function to display a prompt and wait for a response.
Usage: void keypause(void);
Returns: Nothing
*/
void keypause()
{
puts("Press a key to continue...");
_bios_keybrd(_KEYBRD_READ);
}