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;
}