1    Data Structures and Functions

In class, we studied the binary search tree (BST) data structure, and the functions associated with BST. In this project, you will implement this dat a structure and all of the associated functions. In addition, you will implement a data structure to manage the tree nodes deleted from the BST for future use.

1.1    Data Types

The project description will make reference to the following three data types.  You may use them with modifications, but you do not have to use them.

typedef  struct  TAG_NODE{

float   key;

struct  TAG_NODE  *P;

struct  TAG_NODE  *L;

struct  TAG_NODE  *R;

}NODE;

typedef  struct  TAG_BST{

int       size;

struct  TAG_NODE  *root;

}TREE;

typedef  struct  TAG_STORE{

int       size;

struct  TAG_NODE  *head;

}STORE;

Here NODE defines the data type for tree nodes, TREE defines the data type for BST, and STORE defines the data type for the local list of deleted tree nodes. The meanings for the fields are straightforward.

1.2    Functions

You need to implement the necessary functions for operations of BST. These should be implemented in the module for BST. You also need to implement the necessary functions to maintain the local list of tree nodes. These should be implemented in the module for local memory management. You need to modify the files util .h and util .cpp provided to you in your first project to read in the next instructions in this project. See Section 3 for the list of instructions and functions.

2    Modular Design

You will continue to do modular design, provide a Makefile to compile various modules to generate the executable file named PJ3. Among other things, you need to have at least the following modules:

1. main .cpp, which coordinates all modules;

2. util .h and util .cpp, which provides utility services including command line interpretation;

3. MM .h and MM .cpp, which maintains a local list of tree nodes;

4. BST .h and BST .cpp, which implements the functions of BST.

For each module other than the main program, you should have a header file which specifies the data structures and the prototypes of the functions in the module, and an implementation file which implements all of the functions specified in the header file. It is recommended that you define all data types in a header file named data structures .h.

3    Flow of the Project

3.1    Valid Execution

A valid execution of your project has the following form:

./PJ3  flagMM

where  ./PJ3 tells the system to search for the executable file PJ3 in the current directory, and flagMM is either 0 or 1.  When the value of flagMM is 1, your program must maintain a local list of tree nodes: when a new tree node is needed for insertion, your program takes the first node on the local list when it is not empty, and allocate memory for a tree node only when the local list is empty; when a tree node is deleted from the tree, it is inserted at the front of the local list. When the value of flagMM is 0, your program does not maintain a local list of tree nodes:  when a new tree node is needed for insertion, your program allocates memory for a tree node. when a tree node is deleted from the tree, your program returns it to the system.

Your program should check whether the execution is valid.  If the execution is not valid, your program should print out the following message to stderr and stop.

Usage:  ./PJ3  flagMM

Note that your program should not crash when the execution is not valid.

3.2    Flow of the Program

Upon a valid execution, your program should allocate memory for an object T of type NODE  * and allocate memory for an object store of type STORE  * to be used for the binary search tree and the local list of tree nodes.  The naming of T and store is for the descriptions in this document only. You can use any names you like. After that, the program goes into a loop, expecting the following instructions from stdin and acting accordingly:

❼ Stop:

On reading Stop, the program stops.

❼ PreOrder  0:

On reading PreOrder  0, the program should do the following.

1. Print tree T to stdout in pre-order, one node per line, ignoring the NULL nodes.

2. Wait for the next instruction from stdin.

Use the "%f" format for the key value. Refer to posted test cases for output format.

❼ PreOrder  1:

On reading PreOrder  1, the program should do the following.

1. Print tree T to stdout in pre-order, one node per line, printing the string NULL for the NULL nodes.

2. Wait for the next instruction from stdin.

Use the  "%f" format for the key value of a non-NULL node.  Refer to posted test cases for output format.

❼ InOrder  0:

On reading InOrder  0, the program should do the following.

1. Print tree T to stdout in in-order, one node per line, ignoring the NULL nodes.

2. Wait for the next instruction from stdin.

Use the "%f" format for the key value. Refer to posted test cases for output format.

❼ InOrder  1:

On reading InOrder  1, the program should do the following.

1. Print tree T to stdout in in-order, one node per line, printing the string NULL for the NULL nodes.

2. Wait for the next instruction from stdin.

Use the  "%f" format for the key value of a non-NULL node.  Refer to posted test cases for output format.

❼ PostOrder  0:

On reading PostOrder  0, the program should do the following.

1. Print tree T to stdout in post-order, one node per line, ignoring the NULL nodes.

2. Wait for the next instruction from stdin.

Use the "%f" format for the key value. Refer to posted test cases for output format.

❼ PostOrder  1:

On reading PostOrder  1, the program should do the following.

1. Print tree T to stdout in post-order, one node per line, printing the string NULL for the NULL nodes.

2. Wait for the next instruction from stdin.

Use the  "%f" format for the key value of a non-NULL node.  Refer to posted test cases for output format.

❼ Read  <FileName>:

On reading Read  <FileName>, the program should do the following.

1. If the tree is non-empty, i.e., T->size  >  0, print the following error message to stderr and wait for the next instruction from stdin:

Error:  Reading  into non-empty  tree

2. If the tree is empty, i.e., T->size  ==  0, open the file FileName in read mode and read in the BST stored in the file (in pre-order format, with the first line being the number of nodes in the tree) to construct the nodes in T.

3. Wait for the next instruction from stdin.

Note that memory allocation may be necessary when reading the tree from a file. When the file FileName cannot be opened for reading, the program should print some error message to stderr and indicate that the reading is unsuccessful.  After successful reading, the program should close the file. When the reading is successful, print the following to stdout:

Reading  successful

otherwise, print the following to stdout:

Reading unsuccessful

Refer to Example xx for format.

❼ Write  <FileName>:

On reading Write  <FileName>, the program should do the following.

1.  Open the file <FileName> in write mode, and write T->size in the first line of the file.

2. Write the tree T into <FileName> in pre-order, one line per node, ignoring the NULL nodes.

3. Wait for the next instruction from stdin.

When the file FileName cannot be opened for writing, the program should print some error message to stderr and indicate that the reading is unsuccessful. After successful writing, the program should close the file. When the writing is successful, print the following to stdout:

Writing  successful

otherwise, print the following to stdout:

Writing unsuccessful

Refer to Example yy for format.

❼ Search  <Key>:

On reading Search  <Key>, the program should do the following.

1.  Search the tree T, return a pointer to the tree node node whose key field matches <Key> if such a node exists, return NULL otherwise.

2. If the search found a tree node, print the following message to stdout: <Key>  found

If the search is unsuccessful, print the following message to stdout:

<Key> not  found

3. Wait for the next instruction from stdin.

Refer to posted test cases for format.

❼ Insert  <Key>:

On reading Insert  <Key>, the program should do the following.

1. If the tree T contains a node with key field equal to <Key>, print the following message to stdout:

<Key>  already  in  tree, no  insertion

2. If the tree T does not contain a node with key field equal to <Key>, insert a node with key field equal to <Key> to T, and print the following message to stdout:

<Key>  inserted

3. Wait for the next instruction from stdin.

Refer to posted test cases for format.

❼ Delete  <Key>:

On reading Delete  <Key>, the program should do the following.

1. If the tree T does not contain a node with key field equal to <Key>, print the following message to stdout:

<Key> not  in  tree, no  deletion

2. If the tree T contains a node with key field equal to <Key>, delete that node, and print the following message to stdout:

<Key>  deleted

3. Wait for the next instruction from stdin.

Refer to posted test cases for format.

❼ PrintList  <Count>:

On reading PrintList  <Count>, the program should do the following.

1. Print the key fields of the first <Count> nodes on store to stdout, one node per line.

2. Wait for the next instruction from stdin.

Refer to posted test cases for format.

❼ Unknown  Instructions:

If your program reads in an unknown instruction (other than the ones listed in the above), the program should do the following.

1. Write the following message to stderr Warning:  Invalid  instruction

2. Wait for the next instruction from stdin.

4    Format of the Input File

Refer to posted test cases for the format of the input file.

5    Submission

You should submit your project to Gradescope via the link on Canvas. Submit your Makefile along with all header files and implementation files. You should put your name and ASU ID at the top of each of the header files and the implementation files, as a comment.

Submissions are always due before  11:59pm on the deadline date.   Do not expect the clock on your machine to be synchronized with the one on Canvas/Gradescope.  This project is due on Wednesday, 4/26/2023.  It is your responsibility to submit your project well before the deadline.

Since you have more than three weeks to work on this project, no extension request (too busy, sick, need more time accommodations) is a valid one.

6    Grading

All programs will be compiled and graded on Gradescope.  If your program does not compile and work on Gradescope, you will receive 0 on this project. If your program works well on general .asu .edu, there should not be much problems. The maximum possible points for this project is 100. The following shows how you can have points deducted.

1. Non-working program:  If your program does not compile or does not execute on Grade- scope, you will receive a 0 on this project. Do not claim “my program works perfectly on my PC, but I do not know how to use Gradescope.”

2. Posted test cases:  For each of the 20 posted test cases that your program fails, 4 points will be marked off.

3. UN-posted test cases:  For each of the 5 un-posted test cases that your program fails, 4 points will be marked off.

7    Progress Log

You are advised to implement your project on general .asu .edu. You should submit a version to Gradescope on each of the Mondays and Fridays (4/10/2023, 4/14/2023, 4/17/2023, 4/21/2023, and 4/24/2023).

8    Examples and Test Cases

Test cases will be posted on Canvas shortly. We will use the BST (with 8 nodes) shown in Figure 1 in our examples.

 

Figure 1: A BST with 8 nodes

The following is the content of the input file ifile01, which contains the BST in Figure 1 in pre-order format.

8

9

3

1

20

12

10

15

30

Some examples are presented in the following subsections.  I used the shell script run with the following content

#!/bin/bash

Execution  <  Commands  >  Output .txt

as sample executions for given files Execution and Commands to generate these examples.

8.1    Example 1

The content of Execution is

#!/bin/bash

./PJ3  0

The content of Commands is

PreOrder  1

The content of produced Output .txt is

NULL

8.2    Example 2

The content of Execution is

#!/bin/bash

./PJ3  0

The content of Commands is

Read  ifile01

PreOrder  1

The content of produced Output .txt is

Reading  successful

9.000000

3.000000

1.000000

NULL

NULL

NULL

20.000000

12.000000

10.000000

NULL

NULL

15.000000

NULL

NULL

30.000000

NULL

NULL

8.3    Example 3

The content of Execution is

#!/bin/bash

./PJ3  1

The content of Commands is

Read  ifile01

PreOrder  0

The content of produced Output .txt is

Reading  successful

9.000000

3.000000

1.000000

20.000000

12.000000

10.000000

15.000000

30.000000

8.4    Example 4

The content of Execution is

#!/bin/bash

./PJ3  1

The content of Commands is

Read  ifile01

Insert  40

Insert  50

Insert  35

PreOrder  1

PrintList  8

The content of produced Output .txt is

Reading  successful

40 .000000  inserted

50 .000000  inserted

35 .000000  inserted

80 .000000 not  in  tree, no  deletion

50 .000000  deleted

9 .000000  deleted

10.000000

3.000000

1.000000

NULL

NULL

NULL

20.000000

12.000000

NULL

15.000000

NULL

NULL

30.000000

NULL

40.000000

35.000000

NULL

NULL

NULL

Key  values  on  local  list:

9.000000

50.000000