#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    6
    Rep Power
    0

    Threaded Tree Traversal


    Hello,

    As an assignment we have to write a method for a Threaded Binary Tree that traverses the tree in post-order. However, we aren't allowed to use recursion or stacks

    This is what I have so far (after doing some Googling):

    java Code:
    public void postOrder() {
    	ThreadedTreeNode<T> temp = new ThreadedTreeNode<T>(null);
    	String action = "left";
    	ArrayList<ThreadedTreeNode<T>> visited = new ArrayList<ThreadedTreeNode<T>>();
     
    	temp.left = root;
     
    	while (temp != null) {
    		if (action == "left") {
    			if (temp.left != null && !visited.contains(temp.left))
    				temp = temp.left;
    			else
    				action = "right";
    		}
    		else if (action == "right") {
    			if (temp.left != null && !visited.contains(temp.left))
    				action = "left";
    			else
    				action = "visit";
    		}
    		else if (action == "visit") {
    			visit(temp);
    			visited.add(temp);
     
    			if (temp.right.left == temp) {
    				action = "right";
    				temp = temp.right;	
    			}
     
    			if (temp.right == null)
    				return;
    		}
    	}
    }


    Any ideas on what's wrong? It just goes into an infinite loop when visiting the root.

    Thanks,

    Mr_Bean
  2. #2
  3. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    One problem is the use of == to compare Strings. The code should use the equals() method.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    6
    Rep Power
    0
    Thanks, but that didn't solve the problem.
  6. #4
  7. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    Try debugging the code by adding some println statements that will print out the values of variables as the code executes and show you why it goes into an infinite loop.
    It should show how the value of temp changes as the code executes.
  8. #5
  9. Daniel Schildsky
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Mar 2004
    Location
    KL, Malaysia.
    Posts
    1,542
    Rep Power
    1621

    infinite loop


    Just by looking at the codes, there are 2 exit criteria to escape the while loop:
    a) temp is null.
    b) temp.right is null.

    You have to find out why either of these 2 conditions are not reached.
    When the programming world turns decent, the real world will turn upside down.

IMN logo majestic logo threadwatch logo seochat tools logo