CSCI 2720 Binary Search Trees

In this assignment, you will create a Binary Search Tree to store and retrieve objects of type ItemType. The purpose of this assignment is for you to become familiar with basic tree operations, and understand the efficiency of trees compared to previously studied data structures. Binary Tree nodes have only two children, left and right. Nodes are compared based on their Key instance variable, which in this assignment is of type ItemType . All elements in the left subtree of a given node have key values less than the given node and, all elements in the right subtree have key values greater than the given node. A Binary tree must maintain this sorted property at all times. In this assignment, the binary tree should not accept duplicate values.

In order to implement this BinaryTree , you will use the ItemType class created in the earlier assignments. You may choose to implement the functions in the Binary Tree class iteratively or recursively. As with the previous assignments, you may create additional functions to implement the features asked in the document. Once all functions have been implemented for the Binary Tree class, you will create a Main application that initializes a tree based on file input and allows the user to interactively modify the tree based on the given commands. Finally, make sure to properly document all the code with comments, and make sure that your output exactly matches the example output.

Project Files:

ItemType.h and ItemType. cpp: Implementation remains the same as previous assignments.

BinaryTree.h:

• Structures
  • Node structure that has the following members:
  • ItemType key
  • Node *left
  • Node *right
• Instance Variables:
  • Node *root
• Public member functions:
  • BinaryTree()
  • ~BinaryTree()
  • void insert(ItemType key);
  • void deleteItem(ItemType key)
  • void retrieve(ItemType &item, bool &found) const
  • void preOrder() const
  • void inOrder() const
  • void postOrder() const
  • int getLength() const

The following function can be implemented however you like, just make sure their input and output formatting matches the sample output below. Implement these functions as a class function using prototypes of your choice. For above functions like preorder the function prototype does not include a parameter so you can implement this by using as auxiliary function (as discussed in lecture) or using a getRoot function etc.

• getNumSingleParent function - This function should return the number of nodes that have one child. Example: If the function getNumSingleParent is called on the BST below in the example output, the function should return 1.
• getNumLeafNodes function - This function should count the number of leaf nodes in the BST (Nodes with no children) and then output the count. Example: If the function getNumLeafNodes is called on the BST shown below in the sample output, the function should return 5.
• getSumOfSubtrees function - This function should take in a node as input, search for that node and then return the sum of both subtrees of the given node. Note: Do not include the node that you call this function on in the sum. Example:
  • If the function getSumOfSubtrees(10) is called on the BST shown below in the sample output, the function should return 16.
  • If the function getSumOfSubtrees(50) is called on the BST shown below in the sample output, the function should return 35.
  • If the function getSumOfSubtrees(4) is called on the BST shown below in the sample output, the function should return 0.
  • If the function getSumOfSubtrees(15) is called on the BST shown below in the sample output, the function should return 90.
  • If the function getSumOfSubtrees(60) is called on the BST shown below in the sample output, the program should print out "Item not in tree".

In the readme file give the pseudo code (steps) for the aboves 3 operations. Using this pseudo-code explain the complexity (big O) of your 3 operations.

• BinaryTree. cpp: Implement all the functions defined in the header file.
• Main. cpp: Create a main application that matches example output exactly.

Example Output:

Outputs are given for the starting binary tree shown in the diagram. see image.

./main input.txt
Commands:
insert (i), delete (d), retrieve (r), length (l), in-order (n), pre-order (p), post-order (o), getNumSingleParent (s), getNumLeafNodes (f), getSumOfSubtrees (t), quit (q)

//1. pre-order(p)
Enter a command: p
Pre-Order: 25 15 10 4 12 22 18 24 50 35

//2. in-order(n)
Enter a command: n
In-Order: 4 10 12 15 18 22 24 25 35 50

//3. post-order(o)
Enter a command: o
Post-Order: 4 12 10 18 24 22 15 35 50 25

//4. length(l)
Enter a command: l
List Length: 10

Enter a command: q
Quitting program...

./main input.txt
Commands:
insert (i), delete (d), retrieve (r), length (l), in-order (n), pre-order (p), post-order (o), getNumSingleParent (s), getNumLeafNodes (f), getSumOfSubtrees (t), quit (q)

//5a. insert(i) - insert an item
Enter a command: i
Item to insert: 13
In-Order: 4 10 12 13 15 18 22 24 25 35 50

Enter a command: p
Pre-Order: 25 15 10 4 12 13 22 18 24 50 35

//5b. insert(i) - insert an item that exists in list
Enter a command: i
Item to insert: 25
Item already in tree.
In-Order: 4 10 12 13 15 18 22 24 25 35 50

Enter a command: q
Quitting program...

./main input.txt
Commands:
insert (i), delete (d), retrieve (r), length (l), in-order (n), pre-order (p), post-order (o), getNumSingleParent (s), getNumLeafNodes (f), getSumOfSubtrees (t), quit (q)

//6a. delete(d)
Enter a command: d
Item to delete: 50
In-Order: 4 10 12 15 18 22 24 25 35

Enter a command: o
Post-Order: 4 12 10 18 24 22 15 35 25

Enter a command: p
Pre-Order: 25 15 10 4 12 22 18 24 35
//6b. delete(d)
Enter a command: d
Item to delete: 10
In-Order: 4 12 15 18 22 24 25 35
Enter a command: p
Pre-Order: 25 15 4 12 22 18 24 35

//6c. delete(d) - delete a non-existent item
Enter a command: d
Item to delete: 100
Item not in tree.
In-Order: 4 10 12 15 18 22 24 25 35

Enter a command: q
Quitting program...

./main input.txt
Commands:
insert (i), delete (d), retrieve (r), length (l), in-order (n), pre-order (p), post-order (o), getNumSingleParent (s), getNumLeafNodes (f), getSumOfSubtrees (t), quit (q)

//7a. retrieve(r) - retrieve an existent item
Enter a command: r
Item to be retrieved: 25
Item found in tree.

//7b. retrieve(r) - retrieve an non-existent item
Enter a command: r
Item to be retrieved: 101
Item not in tree.

Enter a command: q
Quitting program...

./main input.txt
Commands:
insert (i), delete (d), retrieve (r), length (l), in-order (n), pre-order (p), post-order (o), getNumSingleParent (s), getNumLeafNodes (f), getSumOfSubtrees (t), quit (q)

//8.invalid command
Enter a command: k
Command not recognized. Try again

Enter a command: b
Command not recognized. Try again

Enter a command: q
Quitting program...

./main input.txt
Commands:
insert (i), delete (d), retrieve (r), length (l), in-order (n), pre-order (p), post-order (o), getNumSingleParent (s), getNumLeafNodes (f), getSumOfSubtrees (t), quit (q)

//9. getNumSingleParent (s)
Enter a command: s
Number of Single Parents: 1

//10. getNumLeafNodes (f)
Enter a command: f
Number of leaf nodes: 5

//9. getSumOfSubtrees (t)
Enter a command: t
Item to get sum of subtrees: 10
Sum of Subtrees: 16

Enter a command: t
Item to get sum of subtrees: 99
Item not in tree.

Enter a command: q
Quitting program...