CS 3410 Spring 2018
Due: Monday, April 23th, 2018 at 11:59 PM. Submit your binarytree.c and testbinarytree 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 executable needs to run on a course machine. In particular, you will need to compile your binarytree.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 binarytree.c is the C source file and testbinarytree is the executable file.
$ gcc -Wall -std=c99 binarytree.c -o testbinarytree
You can run the program with the command:
$ ./testbinarytreeYou 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.
A skeleton has been provided. Do NOT change any of the print statements. You can change the variable names.
#include<stdio.h>
#include<stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node
{
char data;
struct Node* left;
struct Node* right;
};
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* new_node(char data)
{
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Recursive function to construct a binary tree from
inorder traversal in[in_left..in_right] and preorder
traversal pre[pre_left..pre_right]. */
struct Node* build_tree(char in[], char pre[], int in_left, int in_right, int pre_left, int pre_right)
{
// TODO: Your code here
}
void print_postorder(struct Node* node)
{
// TODO: Your code here
}
int main()
{
char preorder[100], inorder[100];
printf("Input the pre-order traversal: ");
// Read in pre-order traversal from the command line
printf("Input the in-order traversal: ");
// Read in in-order traversal from the command line
int len;
// Calculate the length of input strings
// Build the binary tree
struct Node *root = build_tree(inorder, preorder, 0, len - 1, 0, len - 1);
// Output the post-order of the binary tree
printf("The post-order traversal is: ");
print_postorder(root);
printf("\n");
return 0;
}
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.