CS 3410 Spring 2019
Due: Friday, April 19th, 2019 at 11:59 PM. Submit your main.c,
treeTraversal.c and testbinarytree.out on CMS.
This is intended to be an individual assignment. However, you are allowed to work individually or in a group of two. If you work in a group, then group yourself on the CMS for this assignment and submit together. The group does not need to be the same as the project group.
Executable Environment. For this C homework, your testbinarytree.out executable needs to
run
on a course machine. In particular, you will need to compile your main.c
treeTraversal.h treeTraversal.c source file by either using the course virtual
machine (VM) or by SSH'ing into a UGCLINUX machine. See Lab0 Part1a (VM) or Part1b (SSH)
Academic Integrity. Adhere to the highest levels of academic integrity. Submit your work individually or as a group. Cite any sources that you have referred to. Also, state anyone who you may have discussed your approach with. Use the 'Whiteboard approach' discussed in lecture at the beginning of the semester.
For this assignment, you will write a C program that first reads two strings from the command line representing the pre-order and in-order traversal of a binary tree, and then outputs the post-order traversal of that tree. For the definition of tree traversals, please reference Wikipedia . You can assume that the input only consists of upper and lower case letters and digits. You can also assume that the input is valid. e.g. there exists a binary tree, each of its nodes is labeled by a different character, whose pre-order and in-order are the given strings. Please submit the C file on CMS. Your program must compile and run on the course provided VM and /or the CSUG computers.
NOTE: On all problem sets in CS3410, submit code which adheres to the C99 standard (for
gcc, compile with -std=c99).
To compile the C program you should use the following command, where main.c and
treeTraversal.c are the C source files and testbinarytree.out is the executable
file.
$ gcc -Wall -std=c99 main.c treeTraversal.c -o testbinarytree.out
make is a build automation tool to generate targets and goals specified in a configuration file
called Makefile at the same directory. You can find more details about make and
Makefile at here, here and here.
We have provided you a Makefile for this homework. Try run make in the C homework 2 directory.
You will see the following.
$ make gcc -std=c99 -Wall -Werror -c -o main.o main.c gcc -std=c99 -Wall -Werror -c -o treeTraversal.o treeTraversal.c gcc -std=c99 -Wall -Werror -o testbinarytree.out main.o treeTraversal.o $ ls Makefile main.c tests_lite/ treeTraversal.h autograder_lite.py testbinarytree.out treeTraversal.c
Now, you can run the program with the command:
$ ./testbinarytree.outYou should now see the fruits of your labor!
For example:
Input the pre-order traversal: bac Input the in-order traversal: abc The post-order traversal is: acb Input the pre-order traversal: 31254 Input the in-order traversal: 12345 The post-order traversal is: 21453 Input the pre-order traversal: ABCDEFG Input the in-order traversal: CBDAFEG The post-order traversal is: CDBFGEA
You may assume the input strings are less than 100 characters long. You may not use any functions
from the string.h library. stdio.h and stdlib.h are the only
libraries you can use.
In this assignment, you are also expected to manage your memory and prevent memory leaks from happening. A good tool for checking whether your program has memory leak is Valgrind. You can learn how to use it here. A short example is below. We will deduct points if you fail to free all memory before the program exits.
valgrind --leak-check=yes ./testbinarytree.out
A skeleton has been pushed to your github repository. Do NOT change any
of
the print statements.
You can change the variable names. We will use our own treeTraversal.h for grading your
submission, so
you don't need to submit it on CMS.
Note: autograder_lite will check treeTraversal.h
if
you run it locally,
becuase this file is required to compile the binary file.
main.c
#include <stdio.h>
#include <stdlib.h>
#include "treeTraversal.h"
int main()
{
char preorder[100], inorder[100];
printf("Input the pre-order traversal: ");
//TODO: Read in pre-order traversal from the command line
printf("Input the in-order traversal: ");
//TODO: Read in in-order traversal from the command line
int len;
//TODO: Calculate the length of input strings
//TODO: Build the binary tree
printf("The post-order traversal is: ");
//TODO: Output the post-order of the binary tree
printf("\n");
return 0;
}
treeTraversal.h
/**
* This file is a C header file.
* You are expected to implement all functions mentioned here in TreeTraversal.c.
*/
/* A binary tree node has data, pointer to left child
and a pointer to right child */
typedef struct Node {
char data;
struct Node *left;
struct Node *right;
} node_t;
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
extern node_t *new_node(char data);
/* Recursive function to construct a binary tree from
inorder traversal in[in_left..in_right] and preorder
traversal pre[pre_left..pre_right]. */
extern node_t *build_tree(char in[], char pre[], int start, int end);
extern node_t *build_tree2(char in[], char pre[], int in_left, int in_right, int pre_left, int pre_right);
/* Prints the post order traversal of the given root of a tree [node] */
extern void print_postorder(node_t *node);
treeTraversal.c
#include <stdio.h>
#include <stdlib.h>
#include "treeTraversal.h"
/** Helper function that allocates a new node with the
* given data and NULL left and right pointers.
* We have implemented this function for your conveninece becuase this function uses malloc that you probably are not familiar with.
* Don't forget to free all memory allocted here before your program terminates. */
node_t *new_node(char data)
{
node_t *node = (node_t *)malloc(sizeof(node_t));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/**
* TODO: Implement functions defined in treeTraversal.h here.
*/
If you have a problem or question, you can have a look at Professor Anne Bracy's book: All of Programming. Many common questions are also the top result on your favorite search engine.