0

I'm trying to implement the non recursive traversal in a binary tree. I am having trouble getting started with my stack, and have no idea where to begin here. I have written a stack to hold int's before, but never to hold nodes(or whatever it needs to hold...pointers?) Here is the structure I need to stack:

struct TNode {
 int datum;
TNode* leftPtr;
 TNode* rightPtr;
 }; // TNode
 // ===========

Here is my inorder code:

void BinaryTree::inOrderNonRec(TNode* nodePtr)
 {
	 while((nodePtr != NULL)||(!stack.IsEmpty( )))
		 if(nodePtr != NULL)
		 {
			 stack.push(nodePtr);
			 nodePtr = nodePtr->leftPtr;
		 }
		 else
		 {
			 nodePtr = stack.top( );
			 stack.pop( );
			 cout << nodePtr->datum << " ";
			 nodePtr = nodePtr->rightPtr;
		 }
		 cout << endl;
 }

Any help would be appreciated.

2
Contributors
1
Reply
2
Views
6 Years
Discussion Span
Last Post by Narue
0

I have written a stack to hold int's before, but never to hold nodes(or whatever it needs to hold...pointers?)

You'd be holding pointers, and it's really no different from integers in how you use the stack:

TNode *stack[64];
int top = 0;

I assume you're implementing an iterator-based traversal or the tree is balanced, because basic binary trees typically don't need to use a stack for any of the operations. However, you can find some sample code (in C) amongst the tree tutorials on this site.

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.