• Post Reply Bookmark Topic Watch Topic
  • New Topic

how far does the apple fall - BinaryTrees  RSS feed

 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a big problem with these nonlinear thinking Binary trees, and expecially when one is required to display the contents of a proper BinaryTree for ones Easter Assignment Does anyone have a good starting point.
The only way of doing this i think is recursivley, but when you get down into either left or right subtrees, the process becomes very confusing! Should i be considering the heights\depth of the nodes in each subtree?
Any help would be smashing.

DobSun
 
Ranch Hand
Posts: 221
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you describe your problem more specifically?

It sounds like you need to write an algorithm to 'visit' every node in a binary tree, according to some criteria. What are those criteria? What have you tried?

When you say 'things get confusing', what problems have you encountered? If you are more specific, I'm sure someone will be more than happy to guide you.
 
Robert Quigley
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay here we go

I have tried this method, the main
idea is to print the nodes of the
tree as they appear from root to
leaves.
(key is the nodes element i need to print)
public void displayTree(BTNode start){

System.out.println(start.key());
if(start.getParent()!= null)
{
//ie: start is the root node
if(start.getLeft()!= null)
{
displayTree(start.getLeft());
}
else
{
System.out.println("Finished");
}

}
else
{
if(start.getParent().getRight()!=null)
{
displayTree(start.getRight());
}
else
{
System.out.println("Finished");
}
}
}
 
Ranch Hand
Posts: 48
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


I am not sure if your code will work. For instance, and I assume, you start with the root and the root's parent is null. In that case the "if" condition returns false and you fall into the else clause. In the else clause you call start.getParent().getRight(). We already know start.getParent() returns null, so wouldn't you get a NullPointerException?
 
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Learning trees & lists & such I found it very helpful to draw the tree on paper and imagine that I'm walking around on it. When you're standing on the anchor node, what do you want to display first? Next? How do you get there? When you hit the end of a branch, how do you get back?

The good news is the solution is simpler than you think. As a hint, it will have fewer if tests than you do now.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!