Chapter 6, Problem 19E

Explanation of Solution

C++ program for preorder iterator:    

• The Example 6.69 explains how C++ use iterator () function different from Java.
• The program explains the use of pointers, references, inner classes and operator overloading.
• The tree node take the input of integer datatype.

//Defining the header files

#include <stack>

#include <iostream.h>

//Using namespace std

using namespace std;

//Defining the class tree_node

class tree_node

{   

    //Defining the left node variable

    tree_node* left;

    //Defining the right node variable

    tree_node* right;

    //Defining the public variable val

    public:int val;

    //Defining the constructor

    tree_node(tree_node *l, tree_node *r, int v)

    {

        //assigning the value for     left and right node

        left = l; right = r; val = v;

    }

    //Defining another constructor with one parameter   

    tree_node(int v)

    {

        //Assigning value to tree node and val

        left = 0; right = 0; val = v;

    }

    //Defining the inner class

    class iterator

    {

        //Defining the variable with reference

        stack<tree_node*> *s;

        tree_node *cur;

        //Defining the constructor for iterator as public

        public:iterator(tree_node& n)

        {

            //Defining a stack to store the tree

            s = new stack<tree_node*>();

            //Assigning current value to n

            cur = &n;

            //Checking current position

            if (cur)

            {

                //If current position in right side then                 push the element to the stack

                if (cur->right) s->push(cur->right);

                //If current position in left side then                 push the element to the stack

                if (cur->left) s->push(cur->left);

            }

        }

        //Destructor for iterator

        ~iterator()

        {

            //Deleting the stack

            delete s;

        }

        //Checking current position with pointer

        bool operator!=(void *p) const

        {

            //Return statement if current!=0

            return (cur != 0);

        }

        //Use of reference

        iterator& operator++()

        {

            //if condition for checking the stack is empty             or not

            if (s->empty())

            {

                //if stack is empty then it assign the                     current position to 0

                cur = 0;

            }

            //If stack is not empty

            else

            {

                //The current position value points to top                 of the stack

                cur = s->top();

                //use of pop() method

                s->pop();

                if (cur)

                {

                    //Pushing the right element to stack

                    if (cur->right) s->push(cur->right);

                    //Pushing the right element to stack

                    if (cur->left) s->push(cur->left);

                }

            }

            //returning the object

            return *this;

        }

        //operator method using reference

        int& operator*() const

        {

            //it return the current position as val

            return cur->val;

        }

        //operator method pointers

        int* operator->() const

        {

            //it return the current position as val

            return &(cur->val);

        }

    };

    //Defining the begin method of iterator which uses     reference method

    iterator& begin()

    {

        //Creating a new pointer i

        iterator *i = new iterator(*this);

        //Returing the pointer i

        return *i;

    }

    //End method

    void *end()

    {

        //which return 0

        return 0;

    }

};

Explanation:

• The program creates a class “tree_node” which is used to get the left and right nodes of the tree.
• The “tree_node” class used constructors to create the tree.
• Then the program creates an inner class with the name of “iterator”, which incorporates the reference, operator overloading, and pointers method.
• It creates a stack and pushing the elements to the stack based on current position of the variable.