Write a C program to build a tree and print it using different traversals. The program will be invoked as

P0 [file] where file is an optional argument. If the file argument is not given the program reads data from the keyboard as a device (10%). If the argument is given, the program reads data file file.sp18. (note that file is any name and the extension is implicit). Programs improperly implementing file name or executable will not be graded. The remaining 20% is for style. Example invocations:

P0 // read from the keyboard until simulated EOF P0 < somefile // same as above except redirecting from somefile instead of keyboard, testing keyboard input P0 somefile // read from somefile.sp18

Assume you do not know the size of the input file

Assume the input data is all strings separated with standard WS separators (space, tab, new line)

If the input file is not readable for whatever reason, or command line arguments are not correct, the program will abort with an appropriate message

The program will read the data left to right and put them into a tree, which is a binary search tree (BST) with respect to the length of the string (that is strings of the same length are considered the same data.

Tree is never balanced nor restructured other than growing new nodes

A node should contain all data that falls into the node except that literally the same strings will show up only once (set)

The program will subsequently output 3 files corresponding to the 3 traversals, named file.preorder, file.inorder and file.postorder. Note that file is the name of the input file if given, and it is 'out' if the input is from the keyboard.

Treversals

preorder

inorder

postoder

Printing in traversal

a node will print the node's string length intended by 2 x depth of the node followed by the list of strings from the node so that the newer strings show up first

Example will be built in class File xxx.sp18 contains adam ala ada jim ala susan george georg duck invocation: > P0 xxx

Output files: xxx.inorder xxx.preorder xxx.postorder

Invocation: > P0 < xxx.fs17

Output files: out.inorder out.preorder out.postorder

Standards related requirements:

Have the following functions minimum in addition to the main function (the types and arguments are just suggested, the names are required) node_t *buildTree(FILE *); void traverseInorder(node_t*, const char[]); // parameters: tree root, and output basefilename void traversePreorder(node_t*, const char[]); void traversePostorder(node_t*, const char[]);

Put the above four functions into a file tree.c/tree.h

Define the node type in node.h

Keep the main function separate

Processing either keyboard or file input can be done in either way:

If keyboard input, read the input into temporary file, after which the rest of the program always processes file input

If keyboard input, set file pointer to stdin otherwise set file pointer to the actual file, then process always from the file pointer

Files:

node.h, main.c, tree.c+tree.h, makefile

main.c

#include "node.h" #include "traversals.h" #include "buildTree.h" int main(int argc, char* argv[]) { // process command line arguments and make sure file is readable, error otherwise // set up keyboard processing so that below the input is not relevant node_t *root = buildTree(file); preorder(root); inorder(root); postorder(root); return 0; }

Ideas for printing tree with indentations

static void printParseTree(nodeType *rootP,int level) { if (rootP==NULL) return; printf("%*c%d:%-9s ",level*2,' ',level,NodeId.info); // assume some info printed as string printf(" "); printParseTree(rootP->child1,level+1); printParseTree(rootP->child2,level+1); }