0

I know *what* the problem is, I'm just not sure how to proceed...

Here's the code I have so far:

void BinarySearchTree::writeIteratively(ostream& outfile) const
{
    TemplateStack<Node*> stack; // this is to set up the actual stack
    Node* current = root; 
    
    while (current != 0 || !stack.isEmpty())
    {
        // here is the problem
        [B]if (stack.getHead() != root)[/B] // if it's root, then we've already checked the left, need to skip
        {
            while (current->getLeft() != 0)
            {
                stack.push(current);
                cout << "Just pushed " << *current << endl;
                current = current->getLeft();
                cout << "Current is now " << *current << endl;
            }   
        }

        // current->getLeft() == 0
        cout << *current << endl;
            
        // then check the right
        while (current->getRight() != 0)
        {
            current = current->getRight();
            
            if (current->getRight() == 0)
            {
                cout << *current << endl;
                stack.pop(current); 
                //cout << "left: " << *current->getLeft();
                //cout << endl;
                //cout << "right: " << *current->getRight();
                //cout << endl;
            }
        }
        
        cout << *current << endl;
        stack.pop(current);
        
    }
}

The problem starts when the program gets back to the root of my binary search tree. In my case, it's Smith. Then it tries to go back down the left side. So I added the bold/red if statement. I'm just not certain how to obtain the head. The following are the template files I'm using for this entire program. I'll highlight where head is. I've attempted several different ways to obtain the head, including a function called getHead in the TemplateStack.h file.

So long story short: the assignment is to create an iterative write function to print out my binary tree (with phone numbers) in alphabetical format by converting the tree to a stack and printing from that stack. I know this works on paper if I use the if (head != root) for the left side while loop. Thanks in advance for any help!

// ***** TemplateList.h *****

template <class T> 
class TemplateList
{
    public:
                        TemplateList<T>(void);
            bool        isEmpty(void) const;
            bool        addAtHead(T newData);
            bool        removeFromHead(T& oldData);
            void        write(ostream& outfile) const;
    private:
            [B]TemplateNode<T>*    head;[/B]
};
            template <class T>
            ostream&    operator << (ostream& outfile, const TemplateList<T>& list);

template <class T> 
TemplateList<T>::TemplateList<T>(void) // constructor
{
    // initialize the head pointer
    head = 0;
}

template <class T> 
bool TemplateList<T>::isEmpty(void) const
{
    // tests the value in private data's head pointer
    return head != 0;
}

template <class T> 
bool TemplateList<T>::addAtHead(T newData)
{
    // allocate storage for a new TemplateNode<T>
    TemplateNode<T>* newNode = new TemplateNode<T>(newData);
    
    if (newNode != 0) // operator new did NOT return zero
    {
        newNode->setNext(head);
        head = newNode;
    }
    
    return newNode != 0; // either new did or didn't return zero
}

template <class T> 
bool TemplateList<T>::removeFromHead(T& oldData)
{
    // reverses the steps of addAtHead
    Node* temp = oldData;
    
    if (head != 0) // list isn't empty, there are things to remove
    {
        oldData = head->getData();
        cout << "oldData is: " << *oldData << endl;
        head = head->getNext();     // point head to next node
        delete temp;                // break the link from the removed node
    }    
    return head != 0; // return false if list was empty 
}

template <class T> 
void TemplateList<T>::write(ostream& outfile) const
{
    // iterates through list, invoking << for each node in turn
    TemplateNode<T>* current = head;
    
    while (current != 0)
    {
        outfile << *current << endl;
        current = current->getNext();
    }
}

template <class T>
// corresponding overloaded << operator
ostream& operator << (ostream& outfile, const TemplateList<T>& list)
{
    list.write(outfile);
    return outfile;
}
// ***** TemplateNode.h *****

template <class T>
class TemplateNode
{
    public:
                        TemplateNode(T newData);
        T               getData(void) const;
        void            setNext(TemplateNode<T>* newNext);
        TemplateNode<T>*getNext(void) const;
        void            debugWrite(ostream& outfile) const;
    private:
        T               data;
        TemplateNode<T>*next;
};
        template <class T>
        ostream&    operator << (ostream& outfile, const TemplateNode<T>& node);

template <class T>
TemplateNode<T>::TemplateNode<T>(T newData) // constructor
{
    // should copy formal parameter into the private data field
    data = newData;
    
    // initialize the next pointer to zero
    next = 0;
}

// access functions for private data follow....
// next 3 functions.....
template <class T>
T TemplateNode<T>::getData(void) const
{
    return data;
}

template <class T>
void TemplateNode<T>::setNext(TemplateNode<T>* newNext)
{
    next = newNext;
}

template <class T>
TemplateNode<T>* TemplateNode<T>::getNext(void) const
{
    return next;
}

// write function
template <class T>
void TemplateNode<T>::debugWrite(ostream& outfile) const
{
    outfile << data << ' ';
        
    if (next != 0)
        outfile << "(->" << next->data << ") ";
    else
        outfile << "(-> /) ";
    
    return;
}

template <class T>
// corresponding overloaded << operator function
ostream& operator << (ostream& outfile, const TemplateNode<T>& node)
{
    node.debugWrite(outfile);
    return outfile;
}
// ***** TemplateStack.h *****

template <class T>
class TemplateStack
{
    // no constructor prototype because the private data of this class
    // consists of an instance of another class
    public:
            bool    isEmpty(void) const;
            T       getHead(void) const;
            bool    push(T operand);
            bool    pop(T& operand);
            void    debugWrite(ostream& outfile) const; // debug use only
    private:
            TemplateList<T> list;
};
        template <class T>
        ostream&    operator << (ostream& outfile, const TemplateStack<T>& stack);

template <class T>
T TemplateStack<T>::getHead(void) const
{
    return list.head;
}

// next four functions invoke corresponding method of data member list
template <class T>
bool TemplateStack<T>::isEmpty(void) const
{
    return list.isEmpty();
}

template <class T>
bool TemplateStack<T>::push(T operand)
{
    return list.addAtHead(operand);
}

template <class T>
bool TemplateStack<T>::pop(T& operand)
{
    return list.removeFromHead(operand);
}

template <class T>
void TemplateStack<T>::debugWrite (ostream& outfile) const
{
    list.write(outfile);
}

// overloaded operator to simply call TemplateStack<T>::debugWrite
template <class T>
ostream& operator << (ostream& outfile, const TemplateStack<T>& stack)
{
    stack.debugWrite(outfile);
    return outfile;
}
1
Contributor
1
Reply
2
Views
7 Years
Discussion Span
Last Post by muffinhead
0

So I've been working at this for a few hours now and realized that the head is not what I needed. I tried rewriting the write function like the following to exclude the root until the last part, but I'm still getting an infinite loop of the right side of my tree. It doesn't print root at all.

void BinarySearchTree::writeIteratively(ostream& outfile) const
{
    TemplateStack<Node*> stack; // this is to set up the actual stack
    Node* current = root; 
  
    stack.push(current);            // pushing this because it's the root and we know it will need to be pushed
    current = current->getLeft();   // since we just pushed the root, we need to start by checking the left
    
    while (current != 0)
    {
        if (current != root) // if it's root, then we've already checked the left, need to skip
        {
            while (current->getLeft() != 0)
            {
                stack.push(current);
                cout << "Just pushed " << *current << endl;
                current = current->getLeft();
                cout << "Current is now " << *current << endl;
            }   
        }

        // current->getLeft() == 0
        cout << *current << endl;
            
        // then check the right
        while (current->getRight() != 0)
        {
            current = current->getRight();
            
            if (current->getRight() == 0)
            {
                cout << *current << endl;
                stack.pop(current); 
                //cout << "left: " << *current->getLeft();
                //cout << endl;
                //cout << "right: " << *current->getRight();
                //cout << endl;
            }
        }
        
        cout << *current << endl;
        stack.pop(current);
        
        //cout << "Head is now: " << stack.getHead();
        //cout << endl;
    }
}
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.