Code:
#include iostream
#include cstdlib
#define MAX_VALUE 65536
using namespace std;
/* Class Node */
class Node
{
public:
int key;
Node *left, *right;
bool leftThread, rightThread;
};
/* Class ThreadedBinarySearchTree */
class ThreadedBinarySearchTree
{
private:
Node *root;
public:
/* Constructor */
ThreadedBinarySearchTree()
{
root = new Node();
root->right = root->left = root;
root->leftThread = true;
root->key = MAX_VALUE;
}
/* Function to clear tree */
void makeEmpty()
{
root = new Node();
root->right = root->left = root;
root->leftThread = true;
root->key = MAX_VALUE;
}
/* Function to insert a key */
void insert(int key)
{
Node *p = root;
for (;;)
{
if (p->key < key)
{
if (p->rightThread)
break;
p = p->right;
}
else if (p->key > key)
{
if (p->leftThread)
break;
p = p->left;
}
else
{
/* redundant key */
return;
}
}
Node *tmp = new Node();
tmp->key = key;
tmp->rightThread = tmp->leftThread = true;
if (p->key < key)
{
/* insert to right side */
tmp->right = p->right;
tmp->left = p;
p->right = tmp;
p->rightThread = false;
}
else
{
tmp->right = p;
tmp->left = p->left;
p->left = tmp;
p->leftThread = false;
}
}
/* Function to search for an element */
bool search(int key)
{
Node *tmp = root->left;
for (;;)
{
if (tmp->key < key)
{
if (tmp->rightThread)
return false;
tmp = tmp->right;
}
else if (tmp->key > key)
{
if (tmp->leftThread)
return false;
tmp = tmp->left;
}
else
{
return true;
}
}
}
/* Fuction to delete an element */
void Delete(int key)
{
Node *dest = root->left, *p = root;
for (;;)
{
if (dest->key < key)
{
/* not found */
if (dest->rightThread)
return;
p = dest;
dest = dest->right;
}
else if (dest->key > key)
{
/* not found */
if (dest->leftThread)
return;
p = dest;
dest = dest->left;
}
else
{
/* found */
break;
}
}
Node *target = dest;
if (!dest->rightThread && !dest->leftThread)
{
/* dest has two children*/
p = dest;
/* find largest node at left child */
target = dest->left;
while (!target->rightThread)
{
p = target;
target = target->right;
}
/* using replace mode*/
dest->key = target->key;
}
if (p->key >= target->key)
{
if (target->rightThread && target->leftThread)
{
p->left = target->left;
p->leftThread = true;
}
else if (target->rightThread)
{
Node *largest = target->left;
while (!largest->rightThread)
{
largest = largest->right;
}
largest->right = p;
p->left = target->left;
}
else
{
Node *smallest = target->right;
while (!smallest->leftThread)
{
smallest = smallest->left;
}
smallest->left = target->left;
p->left = target->right;
}
}
else
{
if (target->rightThread && target->leftThread)
{
p->right = target->right;
p->rightThread = true;
}
else if (target->rightThread)
{
Node *largest = target->left;
while (!largest->rightThread)
{
largest = largest->right;
}
largest->right = target->right;
p->right = target->left;
}
else
{
Node *smallest = target->right;
while (!smallest->leftThread)
{
smallest = smallest->left;
}
smallest->left = p;
p->right = target->right;
}
}
}
/* Function to print tree */
void printTree()
{
Node *tmp = root, *p;
for (;;)
{
p = tmp;
tmp = tmp->right;
if (!p->rightThread)
{
while (!tmp->leftThread)
{
tmp = tmp->left;
}
}
if (tmp == root)
break;
cout<
}
cout<
}
};
/* Main Contains Menu */
int main()
{
ThreadedBinarySearchTree tbst;
cout<<"ThreadedBinarySearchTree Test\n";
char ch;
int choice, val;
/* Perform tree operations */
do
{
cout<<"\nThreadedBinarySearchTree Operations\n";
cout<<"1. Insert "<
cout<<"2. Delete"<
cout<<"3. Search"<
cout<<"4. Clear"<
cout<<"Enter Your Choice: ";
cin>>choice;
switch (choice)
{
case 1 :
cout<<"Enter integer element to insert: ";
cin>>val;
tbst.insert(val);
break;
case 2 :
cout<<"Enter integer element to delete: ";
cin>>val;
tbst.Delete(val);
break;
case 3 :
cout<<"Enter integer element to search: ";
cin>>val;
if (tbst.search(val) == true)
cout<<"Element "<
else
cout<<"Element "<
break;
case 4 :
cout<<"\nTree Cleared\n";
tbst.makeEmpty();
break;
default :
cout<<"Wrong Entry \n ";
break;
}
/* Display tree */
cout<<"\nTree = ";
tbst.printTree();
cout<<"\nDo you want to continue (Type y or n): ";
cin>>ch;
}
while (ch == 'Y'|| ch == 'y');
return 0;
}
Output:
ThreadedBinarySearchTree Test
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 28
Tree = 28
Do you want to continue (Type y or n): y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 5
Tree = 5 28
Do you want to continue (Type y or n):
y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 19
Tree = 5 19 28
Do you want to continue (Type y or n): y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 63
Tree = 5 19 28 63
Do you want to continue (Type y or n): y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 14
Tree = 5 14 19 28 63
Do you want to continue (Type y or n): y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 7
Tree = 5 7 14 19 28 63
Do you want to continue (Type y or n): y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 70
Tree = 5 7 14 19 28 63 70
Do you want to continue (Type y or n): y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 2
Enter integer element to delete: 24
Tree = 5 7 14 19 28 63 70
Do you want to continue (Type y or n): y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 2
Enter integer element to delete: 14
Tree = 5 7 19 28 63 70
Do you want to continue (Type y or n): y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 3
Enter integer element to search: 63
Element 63 found in the tree
Tree = 5 7 19 28 63 70
Do you want to continue (Type y or n): y
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 4
Tree Cleared
Tree =
Do you want to continue (Type y or n): n
------------------
(program exited with code: 1)
Press return to continue
More C++ Programs:
