Threaded Binary Tree

#include<iostream.h>
#include<string.h>

class Node
{
    /* Each node of a threaded Binary tree contains two integer values to
  differentiate between a thread and a link. 0 specifies that it
       is a thread and 1 specifies that it is a normal pointer. */
public:
int lthread; /* integer value indicating if left child is a thread */
Node *lchild; /* Left child of the node */
char info[50]; /*Information contained in the node */
Node *rchild; /* Right child of the node */
int rthread; /* integer value indicating if right child is a thread */
//Node(int lt,Node *lc, int d,Node *rc,int rt):lthread(lt),lchild(lc),info(d),rchild(rc),rthread(rt){}
Node(int lt,Node *lc,char i[20],Node *rc,int rt)
{
lthread=lt;
lchild=lc;
strcpy (info, i);
rchild = rc;
rthread= rt;
} //Constructor for the Node class
};
class Operations
{
public:
Node *head;
Operations();
void find(char element[50],Node **parent,Node **currentNode);
void insert(char element[50]);
Node * Inorder_successor(Node *currentNode);
Node * Inorder_predecessor(Node *currentNode);
void Inorder_traversal();
void remove();
void case_1(Node *par, Node *loc);
void case_2(Node *par, Node *loc);
void case_3(Node *par, Node *loc);
};

Operations :: Operations()
{
/* In a threaded binary tree, we have a dummy node called the header node.
       The threaded binary tree is represented as the left subtree of the header
       node, which means that the left child of the header node points to the root.
       When the tree is empty then the left child of head is a thread pointing to itself.
       Here in the constructor, we are initializing the header node whose left pointer
       is pointing to itself since the tree is initially empty. */
head=new Node(0,head,"header",head,0);
head->lchild=head;
head->rchild=head;
}
void Operations :: find(char element[50], Node **parent, Node ** currentNode)
{
/* find() function provides the currentNode of the node in question and its parent. */

if (head->lchild == head)
            {
                /* If the tree is empty then the currentNode of the node in search is null
                   and the parent is head.*/
                *currentNode = NULL;
                *parent = head;
                return;
            }
            *currentNode = head->lchild;
            *parent = head;

            while(strcmp((*currentNode)->info,element) !=0)
            {
                *parent = *currentNode;
                if (strcmp(element,(*currentNode)->info)<0)
                {
                    if ((*currentNode)->lthread == 1)
                        *currentNode = (*currentNode)->lchild;
                    else
                    {
                        *currentNode = NULL;
                        return;
                    }
                }
                else
                {
                    if ((*currentNode)->rthread == 1)
                        *currentNode = (*currentNode)->rchild;
                    else
                    {
                        *currentNode = NULL;
                        return;
                    }
                }
            }

}
void Operations :: insert(char element[50]) /* Inserts an element in the tree */
{
Node *tmp,*parent,*currentNode;
find(element,&parent,&currentNode);
if(currentNode!=NULL)
{
/* Insertion is not allowed if the node is already
           present in the tree. */
cout<<"\nDuplicates not allowed";
return;
}
tmp=new Node(0,NULL,element,NULL,0);
if(parent==head) /* If the node to be inserted is the root */
{
head->lthread=1; /* Indicates that the left child of the header is now a pointer and not thread */
head->lchild=tmp; /* The left child of header node is set to the root */
tmp->lchild=head; /* Initially the left and the right child of the root points to header node */
tmp->rchild=head;
}
else
{
if(strcmp(element,parent->info)<0)
{
/* If the value to be inserted is less that the parent's value then the
               new node will become the left child of its parent.
               The inorder predecessor of the parent is now the inorder predecessor of the
               new node. The inorder successor of the new node will be its parent.
               The value in the left thread of parent should be changed from 0 to 1
               indicating that the left child of the parent is now a pointer and not a thread. */        

tmp->lchild = parent->lchild;
            tmp->rchild = parent;
            parent->lthread = 1;
            parent->lchild = tmp;
}
else
{
/* If the value to be inserted is greater than the parent's value then the
               new node will become the right child of its parent. the inorder successor of
               the parent is now the inorder successor of the new node. The inorder predecessor
               of the new node will be its parent.
               The value in the right thread of parent should be changed from 0 to 1
               indicating that the right child of the parent is now a pointer and not a thread. */              

tmp->rchild = parent->rchild;
            tmp->lchild = parent;                  
            parent->rthread = 1;
            parent->rchild = tmp;
}
}
}
Node * Operations :: Inorder_successor(Node *currentNode)//Finds the inorder successor of a node
{
  /* Inorder successor of a node refers to the leftmost node in the right
     sub tree of that node. */
Node *successor;
    if (currentNode->rthread == 0)
        successor = currentNode->rchild;
    else
       {
        currentNode = currentNode->rchild;
        while (currentNode->lthread == 1)
           {
             currentNode = currentNode->lchild;
            }
                successor = currentNode;
            }
   return successor;
}

Node * Operations :: Inorder_predecessor(Node *currentNode)//Finds the inorder predecessor of a node
        {
            /* The inorder predecessor of a node is the rightmost node in the left subtree
               of that node. */
            Node *predecessor;
            if (currentNode->lthread == 0)
                predecessor = currentNode->lchild;
            else
            {
                currentNode = currentNode->lchild;
                while (currentNode->rthread == 1)
                {
                    currentNode = currentNode->rchild;
                }
                predecessor = currentNode;
            }
            return predecessor;
        }

void Operations :: Inorder_traversal() /* Performs inorder traversal of the tree */
        {
            /* In an inorder traversal, the leftmost node of the tree is traversed first.
               Once we traverse the leftmost node,the rest of the tree is traversed by
               finding the inorder successor of each node. This process continues until
               we reach the header node. This is because the righmost node of the tree
               is the last node to be traversed and the right pointer of this node is
               a thread pointing to the header node. */

            Node *currentNode;
            if (head->lchild == head)
            {
                cout<<"Tree is empty\n";
                return;
            }
            currentNode = head->lchild;
            while (currentNode->lthread == 1)
            {
                currentNode = currentNode->lchild;
            }
            cout<<currentNode->info<<"   ";
            while (true)
            {
                currentNode = Inorder_successor(currentNode);
                if (currentNode == head)
                    break;
                cout<<currentNode->info <<"   ";
            }
           cout<<endl;
        }

void Operations :: remove() /* Deletes node from the tree */
        {          
            if (head->lchild == head)
            {
                cout<<"\nTree is empty\n";
                return;
            }
Node *parent,*currentNode;
char element[50];
cout<<"\nEnter the word to be deleted: ";
cin>>element;
            find(element, &parent, &currentNode);
            if (currentNode == NULL)
            {
                cout<<"\nWord not found in the dictionary\n";
                return;
            }
            if (currentNode->lthread == 0 && currentNode->rthread == 0) /* Checks if both right and left children */
                case_1(parent, currentNode);
            if (currentNode->lthread == 1 && currentNode->rthread == 0)
                case_2(parent,currentNode);
            if (currentNode->lthread == 0 && currentNode->rthread == 1)
                case_2(parent,currentNode);
            if (currentNode->lthread == 1 && currentNode->rthread == 1)
                case_3(parent,currentNode);              
        }

void Operations :: case_1(Node *parent, Node *currentNode)
        {
            /* This function is called when the node to be deleted is the leaf node */
            if (parent == head)
            {
                head->lthread = 0;
                head->lchild = head;
            }
            else
                if (currentNode == parent->lchild)
                {
                    parent->lthread = 0;
                    parent->lchild = currentNode->lchild;
                }
                else
                {
                    parent->rthread = 0;
                    parent->rchild = currentNode->rchild;
                }
delete currentNode;
        }

void Operations :: case_2(Node *parent, Node *currentNode)
/* This function is invoked if the node to be removed has only one child (left or right) */
        {
            Node *child, *successor, *predecessor;
            if (currentNode->lthread == 1)
                child = currentNode->lchild;
            else
                child = currentNode->rchild;
            if (parent == head)
                head->lchild = child;
            else
                if (currentNode == parent->lchild)
                    parent->lchild = child;
                else
                    parent->rchild = child;
            successor = Inorder_successor(currentNode);
            predecessor = Inorder_predecessor(currentNode);

            if (currentNode->rthread == 1)
                successor->lchild = predecessor;
            else
            {
                if (currentNode->lthread == 1)
                    predecessor->rchild = successor;
            }
delete currentNode;
        }

void Operations :: case_3(Node *parent, Node *currentNode)
 /* This function is invoked if the node to be removed has two children */
        {
         
Node *inorder_suc, *inorder_parent;
            inorder_parent = currentNode;
            inorder_suc = currentNode->rchild;
            while (inorder_suc->lthread ==1)
            {
                inorder_parent = inorder_suc;
                inorder_suc = inorder_suc->lchild;
            }

            currentNode->info = inorder_suc->info;
            if (inorder_suc->lthread == 0 && inorder_suc->rthread == 0)
                case_1(inorder_parent, inorder_suc);
            else
                case_2(inorder_parent, inorder_suc);


        }

void main()
{
Operations t;
char ch,word[50];
int num;
while(true)
{
cout<<"\nMenu";
cout<<"\n1. Implement insert operation"<<endl;
cout<<"2. Implement a delete operation"<<endl;
cout<<"3. Perform inorder traversal"<<endl;
cout<<"4. Exit"<<endl;
cout<<"\nEnter your choice (1-4): ";
cin>>ch;
switch(ch)
{
case '1':
{
cout<<"\nEnter a word: ";
                cin>>word;
                t.insert(word);
}
break;
case '2':
{
                t.remove();
}
break;
case '3':
{
cout<<"\n";
t.Inorder_traversal();
}
break;
case '4':
{
exit(0);
}
break;
default:
{
cout<<"Invalid option"<<endl;
}
break;
}

}
}