Expression Tree (using BST)

/*For given expression eg. a-b*c-d/e+f construct inorder sequence and traverse 

it using postorder traversal(non recursive).*/

#include<iostream>
#include<string>

using namespace std;
typedef struct node
{
char cData;

class Cstack
struct node  *pRt,*pLf;
}NODE;
{
 NODE *pS[20];

void fPush(NODE* pPtr)
int iTop;
public:
 Cstack()
    {
  iTop=-1;
    }
 {

pTmp=pS[iTop];
iTop++;
  pS[iTop]=pPtr;
 }
 NODE* fPop()
 {
 NODE *pTmp;

return(pS[iTop]);
iTop--;
 return(pTmp);
 }
 NODE* fTop()
 {
 }
 int fIsempty()
 {

string sExpr;
if(iTop==-1)
   return 1;
   return 0;
 }
};
class Cexp
{
Cstack oS1,oS2;

void fDisplayPos(NODE*);
int iLen;
public:
void fGetExp();
int fPriority(char);
NODE* fBuildTree();

cout<<"Enter Expression : ";
void fDisplay(NODE*,int,NODE*);
};
void Cexp::fGetExp()
{

 cin>>sExpr;
 iLen=sExpr.size();

}

if(sExpr[i]!='*'&&sExpr[i]!='/'&&sExpr[i]!='+'&&sExpr[i]!='-')
NODE* Cexp::fBuildTree()
{
 NODE *pNn,*pOpr,*pOp1,*pOp2;

 for(int i=iLen-1;i>=0;i--)
 {
  {
  pNn=new NODE;

if(!oS2.fIsempty()&&(fPriority((oS2.fTop())->cData)>fPriority(sExpr[i])))
pNn->cData=sExpr[i];
  pNn->pLf=pNn->pRt=NULL;
  oS1.fPush(pNn);
  }
  else
  {
   {

pOp1=oS1.fPop();
while(  fPriority((oS2.fTop())->cData)>fPriority(sExpr[i])  )
    {
    pOpr=oS2.fPop();
    pOp2=oS1.fPop();
    pOpr->pRt=pOp1;

while(!oS2.fIsempty())
pOpr->pLf=pOp2;
    oS1.fPush(pOpr);
    }
         }
   pNn=new NODE;
   pNn->cData=sExpr[i];
   pNn->pRt=pNn->pLf=NULL;
   oS2.fPush(pNn);
  }
 }
{

int Cexp::fPriority(char cCh)
pOpr=oS2.fPop();
    pOp2=oS1.fPop();
    pOp1=oS1.fPop();
    pOpr->pRt=pOp1;
    pOpr->pLf=pOp2;
    oS1.fPush(pOpr);
}

return oS1.fTop();

}
{
 if(cCh=='+'||cCh=='-')

oS2.fPush(pTmp);
return 1;
 else
  return 2;
}
void Cexp::fDisplayPos(NODE *pRoot)
{
Cstack oS1,oS2;
NODE *pTmp;
oS1.fPush(pRoot);
while(!oS1.fIsempty())
{
pTmp=oS1.fTop();
oS1.fPop();
if(pTmp->pLf)

void Cexp::fDisplay(NODE *ptr, int level,NODE *pRoot)
oS1.fPush(pTmp->pLf);
if(pTmp->pRt)
oS1.fPush(pTmp->pRt);
}
while(!oS2.fIsempty())
{
pTmp=oS2.fTop();
oS2.fPop();
cout<<pTmp->cData<<" ";
}
}
{
int i;
if (ptr != NULL)
{
fDisplay(ptr->pRt, level+1,pRoot);

pRoot=o.fBuildTree();
cout<<endl;
if (ptr == pRoot)
cout<<"Root->:  ";
else
{
for (i = 0;i < level;i++)
cout<<"       ";
}
cout<<ptr->cData;
fDisplay(ptr->pLf, level+1,pRoot);
}
}
int main()
{
NODE *pRoot;
Cexp o;
o.fGetExp();

o.fDisplay(pRoot,1,pRoot);
cout<<"\n";
o.fDisplayPos(pRoot);
cout<<"\n";

return 0;


}

Dictionary using BST

/*
A Dictionary stores keywords & its meanings. Provide facility for adding new
keywords, deleting keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Binary Search Tree for implementation.
*/

#include<iostream>
using namespace std;

typedef struct node
{
struct node *pRt,*pLf;
string sWord,sMeaning;
}NODE;

class cQueue
{
 NODE *pQ[20];
 int iF,iR;
public:
 cQueue()
    {
  iF=iR=-1;
    }
 void fInsert(NODE*);
 NODE* fDelete();
 int fIsempty();

};

void cQueue::fInsert(NODE *pT)
{
 pQ[iR++]=pT;
}

NODE* cQueue::fDelete()
{
 return(pQ[iF++]);
}

int cQueue::fIsempty()
{
 if(iF==iR)
 return 1;
 return 0;
}

class cDictionary
{
public:
    NODE* fCreate();
    void fAdd(NODE*);
    void fDelete(NODE*,string);
    void fUpdate(NODE*);
    void fDisplay(NODE*,NODE*,int);
    void fDisplayIna(NODE*);
    void fDisplayPre(NODE*);
    void fDisplayPos(NODE*);
    void fDisplayLev(NODE*);

};

NODE* cDictionary::fCreate()
{
    NODE *pRoot,*pNn,*pCn,*pParent;
    char cCh;
    pRoot=NULL;
    do
    {
        pNn=new NODE;
        pNn->pLf=pNn->pRt=NULL;
        cout<<"Enter word: ";
        cin>>pNn->sWord;
        cout<<"Enter meaning: ";
        cin>>pNn->sMeaning;

        if(pRoot==NULL)
        pRoot=pNn;
        else
        {
            pCn=pRoot;
            while(pCn)
            {
                pParent=pCn;
                if(pCn->sWord<pNn->sWord)
                pCn=pCn->pRt;
                else
                pCn=pCn->pLf;

            }
            if(pParent->sWord<pNn->sWord)
            pParent->pRt=pNn;
            else
            pParent->pLf=pNn;

        }
        cout<<"do you want to continue(y/n) : ";
         cin>>cCh;

    }while(cCh=='y'||cCh=='Y');
return pRoot;
}

void cDictionary::fAdd(NODE *pRoot)
{
    NODE *pCn,*pNn,*pParent;
    pNn=new NODE;
    pNn->pLf=pNn->pRt=NULL;
    cout<<"Enter word: ";
    cin>>pNn->sWord;
    cout<<"enter Meaning";
    cin>>pNn->sMeaning;
    pCn=pRoot;
    while(pCn)
    {
        pParent=pCn;
        if(pCn->sWord<pNn->sWord)
            pCn=pCn->pRt;
        else
            pCn=pCn->pLf;
    }
    if(pParent->sWord<pNn->sWord)
    pParent->pRt=pNn;
    else
    pParent->pLf=pNn;
    cout<<"Word is added Succesfully to the Dictionary\n";


}


void cDictionary::fDelete(NODE *pPtr,string sData)
{
    NODE *pParent;
    while(pPtr)
    {
    if(pPtr->sWord==sData)
    break;
    pParent=pPtr;
    if(pPtr->sWord<sData)
    pPtr=pPtr->pRt;
    else
    pPtr=pPtr->pLf;

    }
        //case 1 leaf node
        if(pPtr->pLf==NULL&&pPtr->pRt==NULL)
        {
            if(pParent->pRt==pPtr)
            pParent->pRt=NULL;
            else
            pParent->pLf=NULL;
            delete(pPtr);
            cout<<"Node is deleted !\n";

        }

        //case 2 only 1 child
        else if(pPtr->pLf==NULL)
        {
            if(pParent->pRt==pPtr)
            pParent->pRt=pPtr->pRt;
            else
            pParent->pLf=pPtr->pRt;
            delete(pPtr);
            cout<<"Node is deleted !\n";

        }

        else if(pPtr->pRt==NULL)
        {
            if(pParent->pRt==pPtr)
            pParent->pRt=pPtr->pLf;
            else
            pParent->pLf=pPtr->pLf;
            delete(pPtr);
            cout<<"Node is deleted !\n";

        }

        //case 3 two childs
        else
        {
         pParent=pPtr;
         NODE *pTemp;
         pTemp=pPtr->pRt;
         while(pTemp->pLf)
         {
          pParent=pTemp;
          pTemp=pTemp->pLf;
         }
         pPtr->sWord=pTemp->sWord;
         pPtr->sMeaning=pTemp->sMeaning;
         if(pParent==pPtr)
         pPtr->pRt=pTemp->pRt;
         else
         pParent->pLf=NULL;
         delete(pTemp);
         cout<<"Node is deleted !\n";

        }

}


void cDictionary::fUpdate(NODE *pRoot)
{
    NODE *pCn;
    string sW;
    cout<<"Enter word to Update : ";
    cin>>sW;
    pCn=pRoot;
    while(pCn)
    {
        if(pCn->sWord==sW)
        {
            cout<<"Enter New Meaning : ";
            cin>>pCn->sMeaning;
            cout<<"Meaning Updated succesfully\n";
            return;

        }
        else
        {
        if(pCn->sWord<sW)
        pCn=pCn->pRt;
        else
        pCn=pCn->pLf;
        }

    }
cout<<"Word not found!\n";
}

void cDictionary::fDisplay(NODE *pRoot,NODE *pPtr, int level)

{
int i;
if(pPtr!=NULL)
{
fDisplay(pRoot,pPtr->pRt, level+1);
cout<<endl;
if (pPtr == pRoot)
cout<<"Root->:  ";
else
{
for (i = 0;i < level;i++)
cout<<"       ";
}
cout<<pPtr->sWord<<"->"<<pPtr->sMeaning;
fDisplay(pRoot,pPtr->pLf, level+1);
}
}


void cDictionary::fDisplayIna(NODE *pPtr)
{
    if(pPtr)
    {
        fDisplayIna(pPtr->pLf);
        cout<<pPtr->sWord<<"->"<<pPtr->sMeaning<<"\n";
        fDisplayIna(pPtr->pRt);

    }

}

void cDictionary::fDisplayPre(NODE *pPtr)
{
if(pPtr!=NULL)
{
 cout<<pPtr->sWord<<"->"<<pPtr->sMeaning<<" ";
 fDisplayPre(pPtr->pLf);
 fDisplayPos(pPtr->pRt);
}
}

void cDictionary::fDisplayPos(NODE *pPtr)
{
if(pPtr!=NULL)
{
     fDisplayPos(pPtr->pLf);
  fDisplayPos(pPtr->pRt);
  cout<<pPtr->sWord<<"->"<<pPtr->sMeaning<<" ";
}
}

void cDictionary::fDisplayLev(NODE *pPtr)
{
 cQueue oObj;
 NODE *pT;
 oObj.fInsert(pPtr);
 while(oObj.fIsempty()==0)
 {
  pT=oObj.fDelete();
  cout<<pT->sWord<<"->"<<pT->sMeaning<<"\n";
  if(pT->pLf)
  oObj.fInsert(pT->pLf);
  if(pT->pRt)
  oObj.fInsert(pT->pRt);
 }

}

int main()
{
    NODE *pRoot;
    string sW;
    cDictionary oObj;
    char cCh;
    int iCh;
    do
    {
     cout<<"\n\n";
        cout<<"1]Create dictionary\n";
        cout<<"2]Add new Word to the Dictionary\n";
        cout<<"3]Update Meaning of a Word\n";
        cout<<"4]Delete a word from Dictionary\n";
        cout<<"5]Display Dictionary Inorder\n";
        cout<<"6]Display Dictionary Preorder\n";
        cout<<"7]Display Dictionary Postorder\n";
        cout<<"8]Display Dictionary Levelorder\n";
        cout<<"9]Display Tree like structure\n";
        cout<<"\n\nEnter your Choice : ";
        cin>>iCh;
        switch(iCh)
        {
        case 1:
            pRoot=oObj.fCreate();
            break;

        case 2:
            oObj.fAdd(pRoot);
            break;

        case 3:
            oObj.fUpdate(pRoot);
            break;

        case 4:
            cout<<"enter word to delete : ";
            cin>>sW;
            oObj.fDelete(pRoot,sW);
            break;
        case 5:
            oObj.fDisplayIna(pRoot);
            break;

        case 6:
         oObj.fDisplayPre(pRoot);
            break;
        case 7:
            oObj.fDisplayPos(pRoot);
            break;
        case 8:
         oObj.fDisplayLev(pRoot);
      break;
        case 9:
          oObj.fDisplay(pRoot,pRoot,1);
            break;
        }
        cout<<"\npress 1 for main and 2 to exit ";
        cin>>cCh;
    }while(cCh=='1');

return 0;
}