Please show all the steps as detail as possible.... I need help with this.... **

Question

Please show all the steps as detail as possible.... I need help with this....

*****************************************************************

Need Help on C++ Programming. Can you show me and teach me how to make this programming.

*Make sure the programming is working and do not turn in a handwriting.

*Do not separate the file, use main.cpp that make me understand how to do this programming. Use "iostream"

*No handwriting please

*****************************************************************

Write a BTS for strings with pointers -

ADD a balancing routing

Test it by creating a DRIVER/Test class with int main.

Use your classes in it to test that they are working.

Explanation / Answer

/*
* C++ Program to Implement Self Balancing Binary Search Tree
*/
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

/* Class SBBSTNode */

class SBBSTNode
{
public:
int height;
string data;
SBBSTNode *left, *right;
/* Constructor */
SBBSTNode()
{
left = NULL;
right = NULL;
data = "";
height = 0;
}

/* Constructor */
SBBSTNode(string s)
{
left = NULL;
right = NULL;
data = s;
height = 0;
}
};

/*
* Class SelfBalancingBinarySearchTree
*/

class SelfBalancingBinarySearchTree
{
private:
SBBSTNode *root;
public:
/* Constructor */
SelfBalancingBinarySearchTree()
{
root = NULL;
}

/* Function to check if tree is empty */
bool isEmpty()
{
return root == NULL;
}

/* Make the tree logically empty */
void makeEmpty()
{
root = NULL;
}

/* Function to insert data */
void insert(string data)
{
root = insert(data, root);
}

/* Function to get height of node */
int height(SBBSTNode *t)
{
return t == NULL ? -1 : t->height;
}

/* Function to max of left/right node */
int max(int lhs, int rhs)
{
return lhs > rhs ? lhs : rhs;
}

/* Function to insert data recursively */
SBBSTNode *insert(string x, SBBSTNode *t)
{
if (t == NULL)
t = new SBBSTNode(x);
else if (x < t->data)
{
t->left = insert(x, t->left);
if (height(t->left) - height(t->right) == 2)
if (x < t->left->data)
t = rotateWithLeftChild(t);
else
t = doubleWithLeftChild(t);
}
else if (x > t->data)
{
t->right = insert(x, t->right);
if (height(t->right) - height(t->left) == 2)
if (x > t->right->data)
t = rotateWithRightChild(t);
else
t = doubleWithRightChild(t);
}
t->height = max(height(t->left), height(t->right)) + 1;
return t;
}

/* Rotate binary tree node with left child */
SBBSTNode *rotateWithLeftChild(SBBSTNode* k2)
{
SBBSTNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1->height = max(height(k1->left), k2->height) + 1;
return k1;
}

/* Rotate binary tree node with right child */
SBBSTNode *rotateWithRightChild(SBBSTNode *k1)
{
SBBSTNode *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2->height = max(height(k2->right), k1->height) + 1;
return k2;
}

/*
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child
*/
SBBSTNode *doubleWithLeftChild(SBBSTNode *k3)
{
k3->left = rotateWithRightChild(k3->left);
return rotateWithLeftChild(k3);
}

/*
* Double rotate binary tree node: first right child
* with its left child; then node k1 with new right child
*/
SBBSTNode *doubleWithRightChild(SBBSTNode *k1)
{
k1->right = rotateWithLeftChild(k1->right);
return rotateWithRightChild(k1);
}

/* Functions to count number of nodes */
int countNodes()
{
return countNodes(root);
}

int countNodes(SBBSTNode *r)
{
if (r == NULL)
return 0;
else
{
int l = 1;
l += countNodes(r->left);
l += countNodes(r->right);
return l;
}
}

/* Functions to search for an element */
bool search(string val)
{
return search(root, val);
}

bool search(SBBSTNode *r, string val)
{
bool found = false;
while ((r != NULL) && !found)
{
string rval = r->data;
if (val < rval)
r = r->left;
else if (val > rval)
r = r->right;
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}

/* Function for inorder traversal */
void inorder()
{
inorder(root);
}

void inorder(SBBSTNode *r)
{
if (r != NULL)
{
inorder(r->left);
cout<<r->data<<" ";
inorder(r->right);
}
}

/* Function for preorder traversal */
void preorder()
{
preorder(root);
}
void preorder(SBBSTNode *r)
{
if (r != NULL)
{
cout<<r->data<<" ";
preorder(r->left);
preorder(r->right);
}
}

/* Function for postorder traversal */
void postorder()
{
postorder(root);
}
void postorder(SBBSTNode *r)
{
if (r != NULL)
{
postorder(r->left);
postorder(r->right);
cout<<r->data<<" ";
}
}
};

int main()
{
SelfBalancingBinarySearchTree sbbst;
cout<<"SelfBalancingBinarySearchTree Test ";
string val;
char ch;
/* Perform tree operations */
do
{
cout<<" SelfBalancingBinarySearchTree Operations ";
cout<<"1. Insert "<<endl;
cout<<"2. Count nodes"<<endl;
cout<<"3. Search"<<endl;
cout<<"4. Check empty"<<endl;
cout<<"5. Make empty"<<endl;
int choice;
cout<<"Enter your Choice: ";
cin>>choice;
switch (choice)
{
case 1 :
cout<<"Enter string element to insert: ";
cin>>val;
sbbst.insert(val);
break;
case 2 :
cout<<"Nodes = " <<sbbst.countNodes()<<endl;
break;
case 3:
cout<<"Enter string element to search: ";
cin>>val;
if (sbbst.search(val))
cout<<val<<" found in the tree"<<endl;
else
cout<<val<<" not found"<<endl;
break;
case 4 :
cout<<"Empty status = ";
if (sbbst.isEmpty())
cout<<"Tree is empty"<<endl;
else
cout<<"Tree is non - empty"<<endl;
break;
case 5 :
cout<<" Tree cleared ";
sbbst.makeEmpty();
break;
default :
cout<<"Wrong Entry ";
break;
}

/* Display tree*/
cout<<" Post order : ";
sbbst.postorder();
cout<<" Pre order : ";
sbbst.preorder();
cout<<" In order : ";
sbbst.inorder();
cout<<" Do you want to continue (Type y or n): ";
cin>>ch;
}
while (ch == 'Y'|| ch == 'y');
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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