CSE310 Project 3: Binary Search Tree + Local Memory Management
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSE310 Project 3: Binary Search Tree + Local Memory Management
Due: 04/26/2023, Posted: 04/04/2023.
This should be your individual work. While you can use the internet to aid your work, you should write your own code. As in the case of your first two programming projects, it should be written using the standard C++ programming language, and compiled using the g++ compiler on a Linux platform. Your project will be graded on Gradescope. If you compile your project on general .asu .edu using the compiler commands provided in the sample Makefile for the first project, you should expect the same behavior of your project on both general .asu .edu and Grade- scope. Therefore, you are highly recommended to develop your project on general .asu .edu.
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
9 Suggested Schedule
The workload for this project is not light. There is not much room for extension, near the end of the semester. It is recommended that you start working on it immediately.
I suggest that you try the following schedule, starting immediately.
1. Day 1: Get the data types compiled on general .asu .edu.
2. Day 2: Work on util .h and util .cpp to make sure that it can read in all valid instructions from stdin.
3. Day 3: Work on MM .h and MM .cpp Make sure it compiles and works correctly on general .asu .edu.
4. Day 4: Work on BST insertion. Make sure it compiles and works correctly on general .asu .edu.
5. Day 5: Work on BST print (pre-order, in-order, post-order). Make sure it compiles and works correctly on general .asu .edu.
6. Day 6: Work on BST Minimum. Make sure it compiles and works correctly on general .asu .edu.
7. Day 7: Work on BST Deletion. Make sure it compiles and works correctly on general .asu .edu.
8. Day 8: Submit to Gradescope and see how many test cases your code passes.
If you can keep up with the proposed schedule, you should be on target to get a perfect score. If you cannot keep up with the proposed schedule, you need to work harder.
Good Luck!
2023-04-07