Binary Search Trees and Object-oriented Programming In this individual assignmen

Question

Binary Search Trees and Object-oriented Programming In this individual assignment, 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 a 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

I prefer to use stack and queue container classes(collection classes as mentioned in ques.) available in Standard Template Library(STL).

The basic layout of your two classes(one for BST and other for node) would look like:

#include<queue>

#include<stack>

using namespace std;

#ifndef B_S_T

#define B_S_T

template<class T>

class Node {

public:

Node() {

left = right = 0;

}

Node(const T& d, Node *l = 0, Node *r = 0) {

data = d;

left = l;

right = r;

}

T data;

Node *left, *right;

};

template<class T>

class Bst {

public:

Bst() {

root = 0;

}

~Bst() {

removeusingpostorder();

}

void add(const T&);

void edit(const T&);

void findanddisplay(const T&);

void view();

void delete(const T&);

T* findandpurchase(const T&);

void displaycurrentorder();

void clearcurrentorder();

protected:

Node<T>* root;

};

#endif

This .h file will be more or less your definition of function and variables.

Note:- Pay close attention to the access specifiers for each declaration as this maintains the rules for information hiding.

queue container class will be used for breadth-first traversal(level traversal) and stack will be used for depth first traversal(inorder, preorder, postorder).

A sample layout for preorder traversal would look like:

template<class T>

void Bst<T>:: displaycurrentorder() {

stack<Node<T>*> tr;

Node *r=root;

if(r != 0) {

tr.push(r);

while(...) {

//visit each node acc. to preorder traversal

}

}

}

The stack used above is the container class in STL and has inbuilt basic functions associated with it. I recommend you go through them.

Use concepts of file handling in C++ to read and write in text files.

I hope i am able to help you proceed a bit further in your problem.

Please let me know if you want help with any of the implementation of the function or any other problem that arrives.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.