C++ You will create a binary search tree for a product catalogue. The catalogue
ID: 3593031 • Letter: C
Question
C++
You will create a binary search tree for a product catalogue. The catalogue will be used to display products. The program’s user will add and delete products as well as be able to create an order of products. A product class will consist of a name, its price, and the number of items that the user is buying (all initial buying quantities are 0). Your products should be related so that program is selling related products.
Your binary search tree class will be a collection class (like the list class in the previous project with .h and .cpp files). Your tree class will make use of node pointers/objects defined in a node class. The node class will consist of the product data and node pointers left and right. The tree class will have a root data attribute that will also be a node pointer.
When the program starts, the program should read from a textfile at least 16 products with their names, prices, and quantities being purchased (quantities initially should equal 0). As the data is read, it should be added into the binary search tree. Arrange the data so that the tree will be reasonably balanced. Use the name of the product as the sorting key for the binary search tree.
After the data has been loaded from the text file, a menu should appear that prompts the user to (1) add a product, (2) edit a product, (3) find and display a product, (4) view all products, (5) delete a product, (6) find and purchase a product, (7) display the current order, (8) clear the current order, or (9) quit the program.
When the program quits, the products in the current program, including those just added and having removed all those removed, are saved to the text file so that the updated collection of products will be loaded when the program runs the next time. The quantities should all be set to 0 when saving the text file.
Additional requirements (to practice traversals): Your tree of products should have a destructor that uses a post-order traversal strategy. The view all products menu option should use an in-order traversal strategy. When displaying the current order, use a pre-order traversal strategy. When clearing the current order use a level traversal strategy.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node *left;
struct node *right;
};
// A utility function to create a node
struct node* newNode (int data)
{
struct node* temp = (struct node *) malloc( sizeof(struct node) );
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// A recursive function to construct Full from pre[]. preIndex is used
// to keep track of index in pre[].
struct node* constructTreeUtil (int pre[], int* preIndex,
int low, int high, int size)
{
// Base case
if (*preIndex >= size || low > high)
return NULL;
// The first node in preorder traversal is root. So take the node at
// preIndex from pre[] and make it root, and increment preIndex
struct node* root = newNode ( pre[*preIndex] );
*preIndex = *preIndex + 1;
// If the current subarry has only one element, no need to recur
if (low == high)
return root;
// Search for the first element greater than root
int i;
for ( i = low; i <= high; ++i )
if ( pre[ i ] > root->data )
break;
// Use the index of element found in preorder to divide preorder array in
// two parts. Left subtree and right subtree
root->left = constructTreeUtil ( pre, preIndex, *preIndex, i - 1, size );
root->right = constructTreeUtil ( pre, preIndex, i, high, size );
return root;
}
// The main function to construct BST from given preorder traversal.
// This function mainly uses constructTreeUtil()
struct node *constructTree (int pre[], int size)
{
int preIndex = 0;
return constructTreeUtil (pre, &preIndex, 0, size - 1, size);
}
// A utility function to print inorder traversal of a Binary Tree
void printInorder (struct node* node)
{
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
// Driver program to test above functions
int main ()
{
int pre[] = {10, 5, 1, 7, 40, 50};
int size = sizeof( pre ) / sizeof( pre[0] );
struct node *root = constructTree(pre, size);
printf("Inorder traversal of the constructed tree: ");
printInorder(root);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.