PROGRAM TO IMPLEMENT INORDER TRAVERSAL using STACK.

PROGRAM TO IMPLEMENT INORDER TRAVERSAL using STACK.

  4:09 PM    Unknown

---

#include <iostream>
#include <stdlib.h>
#include <conio.h>

using namespace std;

class Node;
class B_Tree;

template <class Type>

class Stack
{
private:
Type *Arr;
int Top, Size;

public:
Stack(int Siz)
{
Size = Siz;

Arr = new Type[Size];
for (int I = 0; I <Size; I++)
{
Arr[I] = 0;
}

Top = -1;
}

void Push(Type Num)
{
if (Top == Size - 1)
{
cout << "\nStack Overflowed..........." << endl;
exit(1);
}

Arr[++Top] = Num;
}

Type Pop()
{
if (IsEmpty())
{
cout << "\nStack Underflowed..........." << endl;
return 0;
}

return Arr[Top--];
}

inline bool IsEmpty()
{
return (Top == -1);
}
};

class Node
{
private:
    int Info;
    Node *Left, *Right;

    friend class B_Tree;
};

class B_Tree
{
private:
    Node *Root;

public:
    B_Tree()
    {
        Root = NULL;
    }

    Node* Make_Root(int Value)
    {
        Node *Temp = new Node;

        Temp->Info = Value;

        Temp->Left = NULL;
        Temp->Right = NULL;

        return Temp;
    }

    void Set_Left(Node *P, int Value)
    {
        if(P == NULL || P->Left != NULL)
        {
            cout << "\nCannot Insert On Left Of It...!!!\n" << endl;
            exit(1);
        }

        P->Left = Make_Root(Value);
    }

    void Set_Right(Node *P, int Value)
    {
        if(P == NULL || P->Right != NULL)
        {
            cout << "\nCannot Insert On Right Of It...!!!\n" << endl;
            exit(1);
        }

        P->Right = Make_Root(Value);
    }

    void Make_Tree()
    {
        int No;
        Node *P, *Q;

        cout << "\nEnter Number To Make Root: ";
        cin >> No;

        cout << endl;

        Root = Make_Root(No);

        while(No != 25)
        {
            cout << "Enter Any Number: ";
            cin >> No;

            P = Q = Root;

            while(P->Info != No && Q != NULL)
            {
                P = Q;

                if(No < P->Info)
                    Q = P->Left;

                else
                    Q = P->Right;
            }

            if(No == P->Info)
            {
                cout << "\nDuplicate Numbers Occurred...!!!\n" << endl;
                exit(1);
            }

            else if(No < P->Info)
                Set_Left(P, No);

            else
                Set_Right(P, No);
        }
    }

    void InTraverse_2()
    {
        Stack <Node*> Obj(20);

        Node *New = Root;

        do
        {
            while(New != NULL)
            {
                Obj.Push(New);
                New = New->Left;
            }

            if(!Obj.IsEmpty())
            {
                New = Obj.Pop();

                cout <<  New->Info << " ";

                New = New->Right;
            }
        }
        while(!Obj.IsEmpty() || New != NULL);
    }
};


int main()
{
    B_Tree Obj;

    cout << "\t\t\tEnter 25 to End Making Nodes....." << endl;

    Obj.Make_Tree();

    cout << "\nTree In InOrder Traverse is: ";
    Obj.InTraverse_2();

    getch();
    return 0;
}