C Programming: Binary Tree Traversal

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.


Overview

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.

Compiling Your Code

NOTE: On all problem sets in CS3410, submit code which adheres to the C99 standard (for gcc, compile with -std=c99).

Manually

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

Makefile

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

Run the Program

Now, you can run the program with the command:

$ ./testbinarytree.out
You 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.

Memory Management

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

Template

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.