1. (50 min) Complete the following BST program with main.cpp and bst.cpp.

1. bst.cpp

// bst.cpp

#include

using namespace std;

struct node //node declaration

{

int d;

struct node *l;

struct node *r;

};

class bst

{

public:

struct node *root;

node * insert(node *r, int v)

{

// recursively call the insert function refer to algorithm

return r;

}

node * deleteItem(node *p, int v)

{

if (p == NULL)

return p;

if (v < p->d)

else

{

if (v > p->d)

else

{

if () // no child

else if () // one child

{

}

else // two child nodes

{

// use getSuccessor() here

}

}

}

}

node * getSuccessor(node *p) // used in delete function

{

}

void show(node *p, int lvl)

{

int i;

if (p != NULL)

{

if (p == root)

cout << "Root: " << p->d << endl;

else

{

cout << p->d << endl;

}

cout << lvl << "L: ";

show(p->l, lvl + 1);

cout << " " << lvl << "R: ";

show(p->r, lvl + 1);

}

}

bst()

{

root = NULL;

}

};

2. main.cpp

#include

#include "bst.cpp"

using namespace std;

int main()

{

int c, i;

bst tree;

while (1)

{

cout << "1.Insert Element into the tree" << endl;

cout << "2.Delete Element" << endl;

cout << "3.Show Binary Search Tree" << endl;

cout << "4.Exit" << endl;

cout << "Enter your Choice: ";

cin >> c;

switch (c) //perform switch operation

{

case 1:

cout << "Enter value to be inserted: ";

cin >> i;

tree.root = tree.insert(tree.root, i);

break;

case 2:

cout << "Enter value to be deleted: ";

cin >> i;

tree.root = tree.deleteItem(tree.root, i);

break;

case 3:

if (tree.root == NULL)

{

cout << "Tree is Empty" << endl;

continue;

}

cout << "Tree:" << endl;

tree.show(tree.root, 1);

cout<

break;

case 4:

exit(1);

break;

default:

cout << "Wrong Choice" << endl;

}

}

return 0;

}

3. Update the program to create an AVL tree. You should at least add the following functions:

• balance_factor calculate balance factor

• left_rotate perform left rotation

• right_rotate perform right rotation

• lr_rotate perform left right rotation

• rl_rotate perform right left rotation

• balance check the balance factor and perform the rotations if necessary

• height calculate the height of a node

4. Update the program to display the AVL tree with the following orders:

• Inorder traversal

• Preorder traversal

• Postorder traversal