1 Replies - 158 Views - Last Post: 29 November 2012 - 03:53 PM Rate Topic: -----

#1 supersonic528  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 28-November 12

PreOrder Error! Binary Tree Traversal.

Posted 29 November 2012 - 01:25 PM

Here is my code that supposed to do preOrder

private void preOrder(BSTNode<T> tree)
	  // Initializes preOrderQueue with tree elements in preOrder order.
	  {
		  
		  LinkedStack<BSTNode<T>> stack = new LinkedStack<BSTNode<T>>();
		  stack.push(root);
		  
		  while(!stack.isEmpty())
		  {
			  
			  BSTNode<T> parent = stack.top();
			  preOrderQueue.enqueue(parent.getInfo());
			  if(parent.getLeft() != null && parent.LeftVisited == false)
			  {
				  stack.push(parent.getLeft());
				  parent.LeftVisited = true;
			  }
			  else if(parent.getRight() != null && parent.RightVisited == false)
			  {
				  stack.push(parent.getRight());
				  parent.RightVisited = true;				  				  
			  }		
			  else
			  {   
				  stack.pop();
				  parent.resetVisitor();	 
			  }
			  
	       }
	  }



Why is the parent of the node printed twice? For example, I put F,G,A,D,I,C,E,H and the output is F,B,A,B,D,C,D,E,D.

Is This A Good Question/Topic? 0
  • +

Replies To: PreOrder Error! Binary Tree Traversal.

#2 Kakerergodt  Icon User is offline

  • D.I.C Head

Reputation: 87
  • View blog
  • Posts: 201
  • Joined: 01-May 12

Re: PreOrder Error! Binary Tree Traversal.

Posted 29 November 2012 - 03:53 PM

That seems unnecessarily complicated for a preorder traversal.

public void preorder()
{
    if root is null, return.

     create stack.
     Add root to stack 

     While stack isn't empty
     {
       Pop node from stack       
       do stuff with node;   

       if right child is not null push onto stack
       if left child is not null push onto stack
     }
}


Edit: This also can be easily made recursively, but I'm guessing that's not part of your assignment.

This post has been edited by Kakerergodt: 29 November 2012 - 04:05 PM

Was This Post Helpful? 2
  • +
  • -

Page 1 of 1