ASSIGNMENT: BST

Write a program in C++ to create a Binary Search tree (BST) of characters. The program will perform these operations: Insert node(s), Traverse Preorder, Search BST, Delete node, Leaf Count, Sibling of a node and Quit.

Use the heard file similar to this:

#include

#ifndef BT_H

#define BT_H

using namespace std;

class BT

{

private:

struct node

{

char data;

node* left;

node* right;

};

node* root;

public:

BT(); //Constructor

bool isEmpty() const { return root == NULL; } //Check for empty

void insert(char); //Insert item in BST

void print_preorder(); //Preorder traversing driver

void preorderTrav(node*); //Preorder traversing

void searchBST(char); //Searches BST for a specific node

void deleteNode(char); //Delete item in BST

int count(); //Count driver

int leafCount(node*); //Counts number of leaves in BST

void nodeSibling(char); //Finds sibling of a node

};

#endif

Use the following menu in your program.

-------------------- MENU ----------------------

1. Insert node(s)

2. Traverse Preorder

3. Search BST

4. Delete node

5. Leaf Count

6. Sibling of a node

7. Quit

Enter your choice:__

Use the following characters in the given order to form the BST tree:

Q K T M D R Y B J

(Hints: 1. Before you start working on the program, you draw the BST for the given order of the above characters. It will help you check your output for the options in the menu. 2. While working on the program, use few items to save time for testing-such as Q K T M, 3. You work on one menu at a time then it is easier to test and manage the program instead of writing the whole thing for entire menu then test your program.)

Option 1: Inserts node(s) in a BST.

Enter Your Choice <1 - 7> 1

Enter number of nodes to insert: 4

Enter node: Q

Inserted.

Enter node: K

Inserted.

Enter node: T

Inserted.

Enter node: M

Inserted.

Option 2: Traverse the tree in preorder and display the node info and its left child info and right child info. If a node does not have a child then print NIL.

Enter Your Choice <1 - 7> 2

Sample output:

Traversing Preorder

Node Info Left Child Info Right Child Info

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

Q K T

K NIL M

M NIL NIL

T NIL NIL

Option 3: Search for the item in the BST.

It will prompt: Enter item you want to search for: K

If the item is found, then display the message ___ is found in the BST. If the item is not found then it will display ____ is not found in the BST

K is found in the BST.

Option 4: Deletes a node from the BST.

It will prompt: Enter item you want to delete:

If the item is found then delete the item from the BST and displays the message ___ is deleted. If the item is not in the BST, then it will display ____ is not found in the BST

Option 5: Counts the number of leaves in the BST and displays

There are ____ number of leaves in the BST.

Option 6: Enter the item and it will display the sibling of that item.

It will prompt: Enter item you want to find the sibling of:

The sibling of ____ is _____

If the item has no sibling then it displays:

____ has no sibling.

Ex: Enter the item: K

The sibling of K is T.

Option 7: Quit the program.