Inordered Threaded Binary Tree | Inorder and Preorder | Deletion of Node in Inordered Threaded Binary Tree
Problem Statement: Create an inordered threaded binary tree and perform inorder and preorder traversals. Analyze time and space complexity of the algorithm.
Note:- Scroll horizontally to see the full line of code.
#include <iostream>
using namespace std;
class node
{
int data;
node *left, *right;
bool isRightThreaded, isLeftThreaded;
public:
node(int x)
{
data = x;
left = right = NULL;
isRightThreaded = false;
isLeftThreaded = false;
}
friend class TBT;
};
class TBT
{
node *root, *header;
public:
TBT()
{
root = NULL;
header = new node(999);
header->left = header->right = header;
}
void insertNode(int x);
void inorder();
void preorder();
void deletenode(int x);
void deleteCaseA(node *parent, node *todelete);
void deleteCaseB(node *parent, node *todelete);
void deleteCaseC(node *parent, node *todelete);
node *inPred(node *x);
node *inSucc(node *x);
};
void TBT::insertNode(int x)
{
if (!root)
{
root = new node(x);
root->left = root->right = header;
root->isLeftThreaded = root->isRightThreaded = true;
header->left = root;
header->isLeftThreaded = true;
cout << "\n Data inserted Successfully!" << endl;
return;
}
else
{
node *current = root;
while (current)
{
// move to left sub-tree
if (x < current->data)
{
if (current->isLeftThreaded == true)
{
node *newnode = new node(x);
newnode->left = current->left;
newnode->isLeftThreaded = true;
newnode->right = current;
newnode->isRightThreaded = true;
current->left = newnode;
current->isLeftThreaded = false;
cout << "\n Data inserted Successfully!" << endl;
break;
}
else
{
current = current->left;
}
}
if (x > current->data)
{
if (current->isRightThreaded == true)
{
node *newnode = new node(x);
newnode->right = current->right;
newnode->isRightThreaded = true;
newnode->left = current;
newnode->isLeftThreaded = true;
current->right = newnode;
current->isRightThreaded = false;
cout << "\n Data inserted Successfully!" << endl;
break;
}
else
{
current = current->right;
}
}
}
}
}
void TBT::inorder()
{
node *current = root;
while (current->left != header)
{
current = current->left;
}
while (current != header)
{
cout << current->data << " ";
if (!current->isRightThreaded)
{
current = current->right;
while (!current->isLeftThreaded)
{
current = current->left;
}
}
else
{
current = current->right;
}
}
cout << endl;
}
void TBT::preorder()
{
node *current = root;
while (!current->isLeftThreaded)
{
cout << current->data << " ";
current = current->left;
}
cout << current->data << " ";
while (current != header)
{
if (current->isRightThreaded)
{
current = current->right;
}
else
{
current = current->right;
cout << current->data << " ";
while (!current->isLeftThreaded)
{
current = current->left;
cout << current->data << " ";
}
}
}
cout << endl;
}
void TBT::deletenode(int x)
{
node *current = root;
node *todelete;
node *parent = NULL;
int flag = 1;
while (current)
{
if (x == current->data)
{
todelete = current;
flag = 0;
break;
}
parent = current;
if (x < current->data)
{
if (!current->isLeftThreaded)
{
current = current->left;
}
}
else if (x > current->data)
{
if (!current->isRightThreaded)
{
current = current->right;
}
}
}
if (flag)
{
cout << "Key is not found" << endl;
return;
}
// if todelete has two children
if (!todelete->isLeftThreaded && !todelete->isRightThreaded)
{
deleteCaseC(parent, todelete);
}
// if todelete has no child node
else if (todelete->isLeftThreaded && todelete->isRightThreaded)
{
deleteCaseA(parent, todelete);
}
// if todelete has only one child node
else
{
deleteCaseB(parent, todelete);
}
cout << "Entry Deleted Successfully!!!" << endl;
}
// if todelete has no child node
void TBT::deleteCaseA(node *parent, node *todelete)
{
if (todelete == parent->left)
{
parent->isLeftThreaded = true;
parent->left = todelete->left;
}
else if (todelete == parent->right)
{
parent->isRightThreaded = true;
parent->right = todelete->right;
}
delete (todelete);
}
// if todelete has only one child node
void TBT::deleteCaseB(node *parent, node *todelete)
{
node *child;
if (!todelete->isLeftThreaded)
{
child = todelete->left;
}
else
{
child = todelete->right;
}
if (!parent)
{
root = child;
}
else if (todelete == parent->left)
{
parent->left = child;
}
else
{
parent->right = child;
}
node *s = inSucc(todelete);
node *p = inPred(todelete);
if (!todelete->isLeftThreaded)
{
p->right = s;
}
else
{
if (!todelete->isRightThreaded)
{
s->left = p;
}
}
delete (todelete);
}
// if todelete has two children
void TBT::deleteCaseC(node *parent, node *todelete)
{
node *parentSuccessor = todelete;
node *temp = todelete->right;
while (!temp->isLeftThreaded)
{
parentSuccessor = temp;
temp = temp->left;
}
todelete->data = temp->data;
if (temp->isLeftThreaded && temp->isRightThreaded)
{
deleteCaseA(parentSuccessor, temp);
}
else
{
deleteCaseB(parentSuccessor, temp);
}
}
node *TBT::inPred(node *x)
{
if (x->isLeftThreaded)
{
return x->left;
}
node *temp = x->left;
while (!x->isRightThreaded)
{
x = x->right;
}
return x;
}
node *TBT::inSucc(node *x)
{
if (x->isRightThreaded)
{
return x->right;
}
node *temp = x->right;
while (!x->isLeftThreaded)
{
x = x->left;
}
return x;
}
int main()
{
TBT tree;
char cont = 'y';
while (cont == 'y')
{
cout << "<--------------Menu--------------->" << endl;
cout << "1.Insert Nodes in tree." << endl;
cout << "2.Inorder Traversal of tree" << endl;
cout << "3.Preorder Traversal of tree" << endl;
cout << "4.Delete a node from tree" << endl;
int choice;
cout << "Enter the choice: ";
cin >> choice;
switch (choice)
{
case 1:
int n;
cout << "Enter the no. of entries: ";
cin >> n;
for (int i = 0; i < n; i++)
{
int m;
cout << "Enter the number: ";
cin >> m;
tree.insertNode(m);
}
cout << "All nodes inserted Successfully!" << endl;
break;
case 2:
tree.inorder();
break;
case 3:
tree.preorder();
break;
case 4:
int j;
cout << "Enter the no. to be deleted: ";
cin >> j;
tree.deletenode(j);
break;
default:
cout << "Invalid Choice!!!!" << endl;
break;
}
cout << "Do you want to continue? (y/n): ";
cin >> cont;
}
if (cont == 'n')
{
cout << "Program Ended Successfully!!!" << endl;
}
return 0;
}
Comments
Post a Comment