C Programming: Binary Tree

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.

---

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.

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:

$ ./testbinarytree

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.

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.