/*-------------------------------------------------------------------- * csc 148s, 1997, Assignment 3a: Recursion warm-up * name: >> Insert your name here << * student number: >> Insert your student number here << * lecturer: >> Insert your lecturer's name here << * lecture time: >> Insert your lecture time here << * tutor: >> Insert your tutor's name here << *-------------------------------------------------------------------- */ /* This program is merely a driver for the purpose of testing the * `smallestBigger' function. The program builds a tree of integers read * from the standard input, and then reads in a sequence of integers * and, for each, calls the `smallestBigger' function and prints the result. * This continues until the end of file is reached. * * Input to the program consists of the following, in order: * - an integer indicating the number of values to be read in to the tree * - that many integers * - a sequence of integers whose smallestBigger value is to be determined * Output consists of the following, in order: * - a diagram of the tree (useful for checking the shape of tree * that was built, and the placement of the integers within it) * - for each test integer, a message indicating what smallestBigger * returned. * No validity checking is done on the input. */ #include #include #include #define MAX_LEN 256 /* Global types *----------------------------------------------------------------------------- * `treeNode' represents a single node in a binary tree of integers. */ typedef struct treeNode { int num; struct treeNode *left, *right; } treeNode; /* smallestBigger *----------------------------------------------------------------------------- * Returns the smallest integer, from the tree pointed to by `root', that is * greater than `num', or `num'-1 if there is no integer greater than `num' * in the tree. * Preconditions: `root' and `num' are initialized. */ int smallestBigger(int value, treeNode *root) { return 0; /* >> Replace the statement above with your code that actually solves << * >> the smallestBigger problem. << * >> Do not add code anywhere else. << */ } /* getNextNum *----------------------------------------------------------------------------- * Read the next integer from standard input and places it in num. If * it reaches the end of file (before finding a new number) it returns EOF. * Note: This function is very general. The numbers can be on the same line * or on different lines. There can even be blank lines. * Note 2: In Unix, you can send end-of-file on stdin by typing control-D. * On Borland C++ you can send end-of-file on stdin by typing control-Z. */ int getNextNum(int *num) { static char *curptr = NULL; static char line[MAX_LEN]; char *nextptr = curptr; if(curptr == NULL && !feof(stdin)) { /*need to read in a new line*/ curptr = line; fgets(line, MAX_LEN, stdin); *num = strtol(curptr, &nextptr, 0); /*get past blank lines*/ while(!feof(stdin) && *num == 0 && nextptr == curptr) { fgets(line, MAX_LEN, stdin); *num = strtol(curptr, &nextptr, 0); } curptr = nextptr; if(feof(stdin)) return EOF; else return 1; } else { /*continue working on the current line*/ *num = strtol(curptr, &nextptr, 0); /*make sure we didn't reach the end of the line and get past blank lines*/ while(!feof(stdin) && *num == 0 && nextptr == curptr) { fgets(line, MAX_LEN, stdin); curptr = line; *num = strtol(curptr, &nextptr, 0); } curptr = nextptr; if(feof(stdin)) return EOF; else return 1; } } /* buildNode *----------------------------------------------------------------------------- * Reads in a single integer from the standard input and creates a treeNode * that stores it, along with two nil child pointers. Returns a pointer to * this new node. * Preconditions: The next thing in the standard input is an integer */ treeNode * buildNode() { int value; treeNode *p; if(getNextNum(&value) == EOF) { printf("ERROR: reached EOF\n"); exit(-1); } p = (treeNode *)malloc(sizeof(treeNode)); p->num = value; p->left = NULL; p->right = NULL; return p; } /* buildTree *----------------------------------------------------------------------------- * Returns a pointer to the root of a binary tree containing `numValues' * integers to be read in from the standard input. * Preconditions: numValues >= 0 * The next thing in the standard input is `numValues' integers */ treeNode * buildTree(int numValues) { int numOnLeftSide, numOnRightSide; treeNode *leftChild, *rightChild, *root; if(numValues == 0) { /* If we're to read in zero values, then we must simply return an empty * tree.*/ return NULL; } else if(numValues == 1) { /* If we're to read in one, then we must return a tree with just a root, * containing that one value.*/ return buildNode(); } else { /* numValues >= 2 * We're to build a tree that will need a root and two subtrees * (although one of the subtrees may be nil). * First build the root node. */ root = buildNode(); /* Now determine how many integers will go on each side of the root. * Make it as even as possible, but if they can't be divided evenly, * give the extra node to the left side.*/ numOnLeftSide = (int)ceil((double)(numValues - 1) / 2); numOnRightSide = numValues - 1 - numOnLeftSide; /* Now build the two subtrees, hook them up to the root, and return * a pointer to the root of the resulting tree.*/ leftChild = buildTree(numOnLeftSide); rightChild = buildTree(numOnRightSide); root->left = leftChild; root->right = rightChild; return root; } } /* printSpaces *----------------------------------------------------------------------------- * Prints the given number of spaces, with no newline. */ void printSpaces(int number) { int i; for(i = 0; i < number; i++) { printf(" "); } } /* printTree *----------------------------------------------------------------------------- * Prints the contents of the given binary tree, to the standard output. * The tree is drawn "sideways", with the root at the left hand side and * its descendents to its right. * `numSpaces' indicates how far from the left margin to indent the whole tree. * It may be 0, in which case the tree is drawn up against * the left margin. * Preconditions: `root' points to a well-formed binary tree of integers * `numSpaces' is initialized */ void printTree (treeNode *root, int numSpaces) { if(root != NULL) { printTree(root->right, numSpaces + 3); printSpaces(numSpaces); printf("%d\n",root->num); printTree(root->left, numSpaces + 3); } } /* M a i n P r o g r a m *---------------------------------------------------------------------------- */ void main(void) { int testNum; /* The root of the binary tree to be built.*/ treeNode *root; /* The size of the binary tree to be built, in terms of number of nodes.*/ int howBig; /* Find out how big a tree to build and then build it and draw it.*/ if(getNextNum(&howBig) == EOF) { printf("ERROR: Reached EOF while reading size of tree\n"); exit(-1); } root = buildTree(howBig); printf("\nThe tree:\n"); printTree(root, 0); /* Read test integers until eof. For each one, print its smallestBigger in * the tree. */ while(getNextNum(&testNum) != EOF) { printf("\n"); printf("The smallest value greater than %d in the tree is: %d\n", testNum, smallestBigger(testNum, root)); } printf("\n"); }