Title

Using a Binary Search Tree to Maintain an Inventory

Introduction

A binary search tree (BST) is a binary tree in which the key value at each node is greater than all keys in its left subtree and less than all keys in its right subtree. A BST can represent an ordered list, and in such an implementation, the operations of search, insertion, and removal are in general fast.

In this project, an interactive program will manipulate an inventory held in an ordered list, and the list will be encapsulated in a class and represented by a pointer-based binary search tree.

Description

Design, implement, document, and test a program that manipulates an inventory of items in a warehouse. The program will be interactive, so the user can read an inventory from a file, insert new items into and remove items from the inventory, and print out the inventory and information about it.

The ordered list that represents the inventory will be provided by a class that represents the inventory with a pointer-based binary search tree. Within the inventory, items will be ordered by their item numbers.

Intput

The program will read commands from the terminal and possibly inventory data from a file.

Output

The program will issue prompts for and responses to commands.

Errors

The program can assume that its input is as described; it need not detect any errors.

Example

If a data file invent.dat is this:

8262 wrench 25 10.50

1173 bucket 15 12.95

4483 chair 40 70.75

4489 desk 12 220.25

3882 stapler 23 9.50

1106 mug 75 5.50

then a run of the program might look like this:

This program responds to the following commands to

manipulate an inventory, which is initially empty.

The commands prompt for additional information, if necessary.

f -- Read an inventory from a file.

i -- Insert an item into the inventory.

r -- Remove an item from the inventory.

e -- Report if the inventory is empty.

a -- Report an item's information.

v -- Report the inventory's total value.

p -- Print the inventory to the terminal.

h -- See this menu.

q -- Quit the program.

--> f

Enter inventory file name: invent.dat

--> e

The inventory is NOT empty.

--> p

Number Name Quantity Price

-------------------------------

1106 mug 75 5.50

1173 bucket 15 12.95

3882 stapler 23 9.50

4483 chair 40 70.75

4489 desk 12 220.25

8262 wrench 25 10.50

-------------------------------

--> r

Item number to remove: 3882

--> p

Number Name Quantity Price

-------------------------------

1106 mug 75 5.50

1173 bucket 15 12.95

4483 chair 40 70.75

4489 desk 12 220.25

8262 wrench 25 10.50

-------------------------------

--> v

The inventory's total value is 6342.25.

--> i

Enter the description of an item:

Number: 2774

Name: monitor

Quantity: 18

Price: 250.75

--> a

Item number to report: 4483

Name: chair

Quantity: 40

Price: 70.75

--> a

Item number to report: 2522

Item not found.

--> p

Number Name Quantity Price

-------------------------------

1106 mug 75 5.50

1173 bucket 15 12.95

2774 monitor 18 250.75

4483 chair 40 70.75

4489 desk 12 220.25

8262 wrench 25 10.50

-------------------------------

--> q

Other Requirements

Implement an inventory as a binary search tree in a class. A inventory's entries have four parts: an item number, the item's name (10 or fewer characters), the number of that item on hand, and the price of the item. The class must provide these operations on an inventory:

A default constructor that initializes a newly-declared inventory to be empty.

A destructor, since an inventory is a pointer-based tree and therefore involves dynamic memory.

A function that tests if an inventory is empty.

A function that inserts a new entry into the invoking inventory.

A function that removes an entry, identified by its item number, from the invoking inventory.

A function that reports to the terminal all the information about an item identified by its number. This should be a boolean function that returns true if the item is found, false if it is not present in the inventory.

A function that returns the total value of all the items currently in the invoking inventory.

A function that prints a table listing all the entries in the invoking inventory in order of their item numbers.

Hints

The nodes in a BST will contain six fields; consider these declarations:

struct Node

{

int id;

char name[10];

int quantity;

double price;

Node *left;

Node *right;

};

Node *root;

Note that the extractor operator ">>" reads strings, and if s1 and s2 are two strings, the function call strcpy(s1,s2); assigns the contents of s2 to s1.