program :

#include

#include "bst.cpp"

using namespace std;

int main()

{

int c, i;

bst tree;

int ex = 0;

while (ex == 0)

{

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:

ex = 1;

break;

default:

cout << "Wrong Choice" << endl;

}

}

return 0;

}

bts :

// 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

if (r==NULL)

{

r = new node;

r -> d=v;

r ->l = NULL;

r->r= NULL;

}

else if (v < r->d)

{

r-> l = insert(r->l,v);

}

else if (v >= r->d)

{

r-> r = insert(r->r,v);

}

return r;

}

node * deleteItem(node *p, int v)

{

if (p == NULL)

return p;

if (v < p->d)

{

p->l = deleteItem(p->l,v);

}

else

{

if (v > p->d)

{

p->r = deleteItem(p->r,v);

}

else

{

if ((p->l == NULL) && (p->r ==NULL)) // no child

{

p = NULL;

}

else if ((p->r == NULL) || (p->l == NULL)) // one child

{

node * t;

if (p->l != NULL)

{

t = p->l;

}

else

{

t = p->r;

}

p=t;

}

else // two child nodes

{

// use getSuccessor() here

node * t = getSuccessor(p->l);

p -> d = t -> d;

p -> l = deleteItem(p->l,t->d);

}

}

}

}

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

{

if (p->r == NULL)

{

return p;

}

else

{

return getSuccessor(p->r);

}

}

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;

}

};

(c) 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 (d) Update the program to display the AVL tree with the following orders: Inorder traversal Preorder traversal Postorder traversal