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%) up to end of the file.

If the argument is given, the program reads data file file.fs182. (note that file is any name and the extension is implicit).

Programs improperly implementing file name or executable will not be graded. 20% is for style. 70% for performance. 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.fs182

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 first character of the string (that is strings of the same first character are considered the same data). Letter cases are the same.

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 intended by 2 x depth of the node the list of strings from the node

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

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

Invocation: > P0 < xxx.fs182

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

Traversals taken from the 3130 textbook:

Preorder:

process root

process children left to right

Inorder:

process left child

process root

proccess right child

Postorder:

process children left to right

process root

More suggestions

Using top-down decomposition you have 3 tasks in main:

Process command arguments, set up file to work regardless of source, check if file readable, set the basename for the output file, etc.

Build the tree

Traverse the tree three different ways generating outputs

The main function should handle the 3 functionalities. #1 should be handled inside of main, functions for #2 and #3 should be in another separate source. Any node types should be defined in a separate header file.

For development purposes, do either 1 or 2 first. 3 should follow 2, first with one traversal only.

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); }

Screenshots of code are acceptable!!