Assignment #5 – Binary Trees and Recursion (60 pts) Solution

$30.00

Description

This assignment is similar to #4 except

  • The Team information should be represented as an ascending ordered binary tree. (Keep the tree nodes in order as they are inserted.)
  • Your search for a Team Id is using a recursive binary tree traversal.
  • The command file will have a new subcommand, PPRINT, for TEAM. We will be able to pretty print the binary tree of teams. See the output below.
  • You will be provided with a driver program (cs1713p5Driver.c) (see below)
  • Your code must be created in a separate C file (p5abc123.c). (see below)
  • There is a new include file, cs1713p5.h
  • Several of the functions must be recursive: searchT, insertT, prettyPrintT, printInOrder
  • We have provided a Makefile to reduce the chances of errors typing in your gcc commands.

 

Input:

Team same as Programming Assignment #4; however, instead of placing it in linked list, you will put it into an ascending ordered binary tree. Some of the data may have changed.

Command Same as assignment 4 plus this new subcommand for TEAM:

TEAM PPRINT

This pretty prints the binary tree. You only have to print the Team IDs in a pretty print manner. In the following example, notice that the right most child is printed first.

UTSA01

UNKN01

SOUTH1

NEWB01

HACK02

COM001

ALHGHT

Driver program:

You will be provided with a driver program, cs1713p5Driver.c which

  1. invokes the driver’s processCommandSwitches
  2. invokes the driver’s getTeams to read the original team information into a binary tree ordered by Team ID using your insertT function.
  3. invokes your printTeams to print the original team information.
  4. invokes a driver-provided processCommands which
    • reads input lines from the command file until eof:
      • prints the input line
      • determines command and subcommand
      • invokes either
        • your processGameCommand to process a GAME subcommand
        • your processTeamCommand to process a TEAM subcommand
  1. invokes your printTeams to print the resulting team information
  2. Larry also provided these functions:
  • allocateNodeT
  • getTeams

Note: do not change the cs1713p5Driver.c

Your p5abc123.c code:

  • You should probably copy your p4abc123.c into a file named p5abc123.c.
  • It does the following includes:

#include <stdio.h>

#include <string.h>

#include “cs1713p5.h”

  • It must not include cs1713p5Driver.c within your p5abc123.c file. Look at the notes below on Compiling Using the make Utility.
  • Remove insertLL. We will be using insertT.
  • Remove searchLL. We will be using searchT.
  • Change printTeams:
    • Receives NodeT *pRoot instead of the linked list pHead.
    • It should still print the column heading for the table of teams; however, it should invoke printInOrder to print the tree in order.
  • Add the recursive function printInOrder which prints all the information about teams in order recursively. This is called by printTeams.
  • Change processGameCommand:
    • Receives NodeT *pRoot instead of the Node **ppHead. Notice that we are not passing the address of pRoot to this function.
    • Invokes processGame passing pRoot and game
    • Invokes processGameFix passing pRoot, game, and the two old scores.
  • Change processGame:
    • Receives NodeT *pRoot instead of the Node *pHead
    • Uses searchT to find a team in the binary tree.

p1 = searchT(pRoot, game.szTeamId1);

  • Change processGameFix:
    • Receives NodeT *pRoot instead of the Node *pHead
    • Uses searchT to find a team in the binary tree.
  • Change processTeamCommand:
    • Receives NodeT **ppRoot instead of the Node **ppHead.
    • Uses searchT to find a team in the binary tree. You will have to dereference ppRoot.

p = searchT(*ppRoot, team.szTeamId1);

    • The NEW subcommand uses insertT to insert a new team into the binary tree.

*ppRoot = insertT(*ppRoot, team);

    • Add code for the new TEAM PPRINT subcommand. This should invoke prettyPrintT.
  • Add the function prettyPrintT which prints a binary tree by printing its right most node first. You only have to print the team IDs.
  • You must create the following routines (see the include file):
    • insertT – using the reconstruct approach, this recursively inserts a team into the ordered binary tree. This returns a pointer to the referenced subtree which is either the pointer it was passed or a pointer to a new node.
    • searchT – recursively searches for a Team Id in the ordered binary tree. If found, it returns a pointer to the node that contains it. If not found, it returns NULL.

Please review the cs1713p5.h include file.

Compiling Using the make Utility

Before using the make utility, you must:

  • Download the Makefile.txt file and rename it simply Makefile (i.e., remove the .txt suffix)
  • Edit Makefile to change p5abc123.o with your abc123 id. Note that you are changing a .o file reference. The make utility will automatically reference your .c file if you properly name the p5abc123.o file:

# Define the machine object files for your program

OBJECTS = p5abc123.o cs1713p5Driver.o

# Define your include file

INCLUDES = cs1713p5.h

# make for the executable

p5: ${OBJECTS}

gcc -g -o p5 ${OBJECTS}

# Simple suffix rules for the .o

%.o: %.c ${INCLUDES}

gcc -g -c $<

# Clean the .o files

clean:

rm -f ${OBJECTS}

Based on the rules in the Makefile, when you tell make to make your executable, it will automatically compile your .c file and the driver .c file. (For more information about the make utility, click here.)

make p5

Executing the p5 executable:

./p5 -c p5Command.txt -t p5Team.txt

Turn in:

Your include file (if it changed)

Your p5abc123.c file.

Your Makefile (since you changed it for your p5abc123.c). The TA/grader will use your Makefile to make the code.

Your output based on the data provided.

Sample Partial Output:

Initial Teams

Id Team Name Wins Loss Fee Amt Paid Amt

Contact Name Phone Email

ALHGHT Cake Eaters 4 4 175.00 100.00

E Z Street (210)555-6666 sliverspoon@xyz.com

COM001 Comm Eagles 7 1 150.00 75.00

Mae King (210)555-2222 maeking@xyz.com

HACK02 Hackers 3 5 150.00 75.00

Tom E Gunn (210)555-5555 cyber@gmail.com

NEWB01 River Rats 0 8 120.00 75.00

Rock D Boat (210)555-4444 riverrat@xyz.com

SOUTH1 Slam Dunk 5 3 120.00 75.00

Jerry Tall (210)555-3333 slamdunk@gmail.com

UNKN01 Org New Blk 1 7 150.00 50.00

Bob Wire (210)555-1234 bobwire@xyz.com

UTSA01 Armadillos 8 0 150.00 80.00

Jean E Us (210)555-1111 utsa@xyz.com

TEAM PPRINT

UTSA01

UNKN01

SOUTH1

NEWB01

HACK02

COM001

ALHGHT

GAME RESULT UTSA01 NEWB01 55 12