question archive Create binary search tree class, which supports the following operations: ?1
Create binary search tree class, which supports the following operations: ?1
Subject:Computer SciencePrice:3.86 Bought14
Create binary search tree class, which supports the following operations:
?1. Insert
?2. Search
?3.Delete
?4.In-order traversal
Important
?
1. The implementation should be template based.
2. The pointer to parent node should also be included in each node. This means each node should
have 3 pointers: left, right and parent. The insert/search/delete should accordingly.
Insert Algorithm:
BST_INSERT(node, newNode) ? Input: root node of tree, node to be inserted ? Output: updated tree with newNode ? Steps: 1. If node == null //base case 2. node = newNode 3. Else If newNode.key < node.key 4. node.left = BST_INSERT(node.left, newNode) 5. Else If newNode.key > node.key 6. node.right = BST_INSERT(node.right, newNode) 7. End If 8. Return node
Deletion Algorithm:
BST_DELETE(node, int key) ? Input: root node of tree, key to be deleted ? Output: updated tree without node that contains key ? Steps: 1. If(node!=null) 2. If key ==node.key 3. If hasLeft(node) and hasRight(node) //case 3 4. successor= INORDER_SUCCESSOR(node) 5. copy(node,successor) 6. node.right= BST_DELETE(node.right, successor.key ) 7. Else //case1, case 2, you can break it in 2 if's 8. node=getChildNode(node); 9. End If 9. Else If key < node.key 10. node.left =BST_DELETE(node.left,key) 11. Else // key > node.key 12. node.right =BST_DELETE(node.right,key) 13. End If 14. return node // updated node 15. End If 16. return node // null getChildNode(node) 1. If hasLeft(node) 2. return node.left 3. Else If hasRight(node) 4. return node.right 5. Else 6. Return NULL// leaf node case 7. End if copy(node,successor) 1. node.key=successor.key 2. Copy other data attributes if present but not child links
Search: Algorithm
? BST_SEARCH(node, key) ? Input: root node of tree, key to be searched ? Output: node which contains value ? Steps: Start 1. If node== null OR value==node.key //one case for both value found or not found return node 2. Else If value < node.key 3. return BST_SEARCH( node.left, key) 4. Else // key> node.key 5. return BST_SEARCH( node.right, key) End
inorder Traversal Algorithm:
Traverse_InOrder(Tree node) If node is not NULL Recursive_InOrder(node.left) print(node) Recursive_InOrder(node.right) End If
Purchase A New Answer
Custom new solution created by our subject matter experts
GET A QUOTE
Answer Preview
CODE:
#include<iostream>
using namespace std;
class Node
{
int data;
Node *right;
Node *left;
public:
Node (int data)
{
this->data = data;
right = left = NULL;
}
void setRight (Node * r)
{
right = r;
}
void setLeft (Node * l)
{
left = l;
}
int getData () const
{
return data;
}
void setData (int d)
{
data = d;
}
Node *getRight () const
{
return right;
}
Node *getLeft () const
{
return left;
}
};
class BST
{
Node *root;
int size;
void inorder (Node * root)
{
if (root == NULL)
{
return;
}
inorder (root->getLeft ());
cout << root->getData () << " ";
inorder (root->getRight ());
}
public:
BST ()
{
root = NULL;
size = 0;
}
void insert (int data)
{
Node *temp = new Node (data);
if (isEmpty ())
{
root = temp;
size++;
return;
}
Node *cur = root;
while (true)
{
if (cur->getData () < data)
{
if (cur->getRight () == NULL)
{
cur->setRight (temp);
size++;
return;
}
cur = cur->getRight ();
}
else if (cur->getData () > data)
{
if (cur->getLeft () == NULL)
{
cur->setLeft (temp);
size++;
return;
}
cur = cur->getLeft ();
}
else
{
cout << "\nDuplicate data Found ";
return;
}
}
}
bool isEmpty ()
{
if (size == 0 || root == NULL)
{
return true;
}
return false;
}
void remove (int data)
{
Node *cur = root;
if (cur->getData () == data)
{
if (cur->getLeft () == NULL && cur->getRight () == NULL)
{
size--;
delete cur;
root = NULL;
return;
}
if (cur->getLeft () == NULL)
{
root = cur->getRight ();
size--;
delete cur;
return;
}
if (cur->getRight () == NULL)
{
root = cur->getLeft ();
size--;
delete cur;
return;
}
Node *tt = cur->getRight ();
while (tt->getLeft () != NULL)
{
tt = tt->getLeft ();
}
tt->setLeft (cur->getLeft ());
root = cur->getRight ();
size--;
delete cur;
return;
}
Node *prev = cur;
int s1 = 0;
while (true)
{
if (data < cur->getData ())
{
if (cur->getLeft () == NULL)
{
cout << "\nNot Found";
return;
}
prev = cur;
cur = cur->getLeft ();
s1 = 1;
}
else if (data > cur->getData ())
{
if (cur->getRight () == NULL)
{
cout << "\nNot Found";
return;
}
prev = cur;
cur = cur->getRight ();
s1 = 2;
}
else
{
if (cur->getLeft () == NULL && cur->getRight () == NULL)
{
size--;
delete cur;
if (s1 == 1)
{
prev->setLeft (NULL);
}
else if (s1 == 2)
{
prev->setRight (NULL);
}
return;
}
if (cur->getLeft () == NULL)
{
if (s1 == 1)
{
prev->setLeft (cur->getRight ());
}
else if (s1 == 2)
{
prev->setRight (cur->getRight ());
}
size--;
delete cur;
return;
}
if (cur->getRight () == NULL)
{
if (s1 == 1)
{
prev->setLeft (cur->getLeft ());
}
else if (s1 == 2)
{
prev->setRight (cur->getLeft ());
}
size--;
delete cur;
return;
}
Node *tt = cur->getRight ();
while (tt->getLeft () != NULL)
{
tt = tt->getLeft ();
}
tt->setLeft (cur->getLeft ());
if (s1 == 1)
{
prev->setLeft (cur->getRight ());
}
else if (s1 == 2)
{
prev->setRight (cur->getRight ());
}
size--;
delete cur;
return;
}
}
}
void search (int data)
{
Node *cur = root;
while (true)
{
if (data < cur->getData ())
{
if (cur->getLeft () == NULL)
{
cout << "\nNot Found";
return;
}
cur = cur->getLeft ();
}
else if (data > cur->getData ())
{
if (cur->getRight () == NULL)
{
cout << "\nNot Found";
return;
}
cur = cur->getRight ();
}
else
{
cout << "\nFound";
return;
}
}
}
void inorder ()
{
inorder (root);
}
};
