Will need to modify the node structure for this. I have completed some of the co
ID: 3849788 • Letter: W
Question
Will need to modify the node structure for this. I have completed some of the code below.
#include <iostream>
#include <cstdlib>
using namespace std;
class BinarySearchTree
{
private:
class node
{
public:
node* left;
node* right;
int key;
string data;
};
public:
node* root;
BinarySearchTree()
{
root = NULL;
}
bool isEmpty() const { return root == NULL; }
void INORDER_TREE_WALK(node*);
void TREE_INSERT(int );
};
void BinarySearchTree::TREE_INSERT(int d)
{
// This implements the algorithm in page 261 of the textbook
node* z = new node();
z->key = d;
z->left = NULL;
z->right = NULL;
node* y = NULL;
node* x = root;
node* parent = NULL;
while (x != NULL)
{
y = x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
parent = y;
if (y == NULL)
root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
}
void BinarySearchTree::INORDER_TREE_WALK(node* x)
{
if (x != NULL)
{
if (x->left) INORDER_TREE_WALK(x->left);
cout << " " << x->key << " ";
if (x->right) INORDER_TREE_WALK(x->right);
}
}
int main()
{
BinarySearchTree bst;
int choice, key;
while (true)
{
cout << endl << endl;
cout << " Binary Search Tree Example " << endl;
cout << " ----------------------------- " << endl;
cout << " 1. Insertion " << endl;
cout << " 2. In-Order Traversal " << endl;
cout << " 3. Exit " << endl;
cout << " Enter your choice : ";
cin >> choice;
switch (choice)
{
case 1: cout << " Enter key (int value) to be inserted : ";
cin >> key;
bst.TREE_INSERT(key);
break;
case 2: cout << endl;
cout << " In-Order Traversal " << endl;
cout << " -------------------" << endl;
bst.INORDER_TREE_WALK(bst.root);
break;
case 3: system("pause");
return 0;
break;
default:
cout << "Invalid choice";
}
}
}
Explanation / Answer
Code To Copy:
#include <iostream>
#include <cstdlib>
using namespace std;
class BinarySearchTree
{
private:
class node
{
public:
node* left;
node* right;
node* parent;
int key;
string data;
};
public:
node* root;
BinarySearchTree()
{
root = NULL;
}
bool isEmpty() const { return root == NULL; }
void INORDER_TREE_WALK(node*);
void TREE_INSERT(int );
void pre_order(node* x)
{
if (x != NULL)
{
cout << " " << x->key << " ";
if (x->left) pre_order(x->left);
if (x->right) pre_order(x->right);
}
}
void post_order(node* x)
{
if (x != NULL)
{
if (x->left) post_order(x->left);
if (x->right) post_order(x->right);
cout << " " << x->key << " ";
}
}
int find_max(node* x)
{
if(x==NULL)
{
cout<<"The tree is empty."<<endl;
return -999;
}
while(x->right!=NULL)
{
x=x->right;
}
cout<<"The maximum element "
<<"present in the tree is :"
<< x->key;
return x->key;
}
void remove_max(node* x)
{
int curr=find_max(x);
del_node(curr);
}
void successor(int val)
{
node* x = root;
while(x!=NULL)
{
if(val<x->key)
{
x=x->left;
}
else if(val>x->key)
{
x = x->right;
}
else
{
break;
}
}
if(x==NULL)
{
cout<<"Key not found"<<endl;
}
if(x->right!=NULL)
{
node* curr = x->right;
while(curr->left!=NULL)
{
curr=curr->left;
}
cout<<"The successor is :"<<curr->key<<endl;
}
else{
node *par = x->parent;
node *curr = x;
while(par != NULL && curr == par->right)
{
curr = par;
par = par->parent;
}
if(par!=NULL)
{
cout<<"The successor is :"<<par->key<<endl;
}
else
{
cout<<"The node has no successor."<<endl;
}
}
}
void del_node(int val)
{
node * x = root;
while(x!=NULL)
{
if(val<x->key)
{
x=x->left;
}
else if(val>x->key)
{
x = x->right;
}
else
{
break;
}
}
if(x==NULL)
{
cout<<"Key not found"<<endl;
return;
}
//node* temp = successor(x);
if(x->right!=NULL)
{
node*temp = x->right;
while(temp->left!=NULL)
{
temp=temp->left;
}
x->key = temp->key;
if(temp->parent == x)
{
x->right = temp->right;
if(temp->right!=NULL)
{
temp->right->parent = temp->parent;
}
}
else
{
temp->parent->left = temp->right;
if(temp->right!=NULL)
{
temp->right->parent = temp->parent;
}
}
free(temp);
}
else if(x->left!=NULL)
{
node*temp = x->left;
while(temp->right!=NULL)
{
temp=temp->right;
}
x->key = temp->key;
if(temp->parent == x)
{
x->left = temp->left;
if(temp->left!=NULL)
{
temp->left->parent = temp->parent;
}
}
else
{
temp->parent->right = temp->left;
if(temp->left!=NULL)
{
temp->left->parent = temp->parent;
}
}
free(temp);
}
else
{
if(x==root)
{
root = NULL;
return;
}
if(x->key>x->parent->key)
{
x->parent->right=NULL;
}
else{
x->parent->left = NULL;
}
}
}
};
void BinarySearchTree::TREE_INSERT(int d)
{
// This implements the algorithm in page 261 of the textbook
node* z = new node();
z->key = d;
z->left = NULL;
z->right = NULL;
z->parent = NULL;
node* y = NULL;
node* x = root;
while (x != NULL)
{
y = x;
if (z->key < x->key)
x = x->left;
else if (z->key >x->key)
x = x->right;
else
{
cout<<"The key already exists in the tree."<<endl;
return;
}
}
z->parent = y;
if (y == NULL)
root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
}
void BinarySearchTree::INORDER_TREE_WALK(node* x)
{
if (x != NULL)
{
if (x->left) INORDER_TREE_WALK(x->left);
cout << " " << x->key << " ";
if (x->right) INORDER_TREE_WALK(x->right);
}
}
int main()
{
BinarySearchTree bst;
int choice, key;
while (true)
{
cout << endl << endl;
cout << " Binary Search Tree Example " << endl;
cout << " ----------------------------- " << endl;
cout << " 1. Insertion " << endl;
cout << " 2. Pre-Order Traversal " << endl;
cout << " 3. Post-Order Traversal " << endl;
cout << " 4. In-Order Traversal " << endl;
cout << " 5. Find Max "<<endl;
cout << " 6. Remove Max "<<endl;
cout << " 7. Successor " <<endl;
cout << " 8. Delete a node "<<endl;
cout << " 9. Exit " << endl;
cout << " Enter your choice : ";
cin >> choice;
switch (choice)
{
case 1: cout << " Enter key (int value) to be inserted : ";
cin >> key;
bst.TREE_INSERT(key);
break;
case 2: cout << endl;
cout << " Pre-Order Traversal " << endl;
cout << " -------------------" << endl;
bst.pre_order(bst.root);
break;
case 3: cout << endl;
cout << " Post-Order Traversal " << endl;
cout << " -------------------" << endl;
bst.post_order(bst.root);
break;
case 4: cout << endl;
cout << " In-Order Traversal " << endl;
cout << " -------------------" << endl;
bst.INORDER_TREE_WALK(bst.root);
break;
case 5:
bst.find_max(bst.root);
break;
case 6:
bst.remove_max(bst.root);
break;
case 7:
cout<<"Enter the key to find the successor: ";
cin>>key;
bst.successor(key);
break;
case 8:
cout<<"Enter the key to be deleted: ";
cin>>key;
bst.del_node(key);
break;
case 9: system("pause");
return 0;
break;
default:
cout << "Invalid choice";
}
}
}
Sample Output:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.