Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

[Help] Recursive method

 
ling qin
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi, i'm writing a recursive method that returns a string containing a binary tree "printed" sideways,with the right subtree above the root node and the left subtree below the root node. Each subtree is indented by three spaces more than its root.

for example, the input binary tree is:

A
/ \
B C
/ \
D E

the returned string shoud be(note the child nodes have 5 spaces idented away from the root):

------D
---B
------E
A
---C

(note that "-" means a space)

This is the method I wrote, the order of the string is correct but the spaces idented is messed up

public String printTree(BinaryTree b) {
if(b.isEmpty)
{ return "";
}else if(b.leftSubtree().isEmpty()&&b.rightSubtree().isEmpty())
{return (String)b.getRoot()+"\n";
}else
{return " "+printTree(b.leftSubtree())+b.getRoot()+" "
+printTree(b.rightSubtree());
}
}

for that input binary tree, the result is like this, which is wrong:

------D
B
---E
A
---C


how can i solve this?thanks
[ November 20, 2006: Message edited by: ling qin ]
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey, welcome to the ranch!

I've done lots of these passing the current indent depth or the indent blanks themselves as a parameter. I think you can make it this simple:

See if that works for you.
[ November 20, 2006: Message edited by: Stan James ]
 
ling qin
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Stan,

I'm a bit confused with your code,can you write it again to include more details?
why do you put print(root, "") at the first place?
where is the if statement opend and closed?

the method should return a String, not printout
thanks a lot!!

[ November 20, 2006: Message edited by: ling qin ]
[ November 20, 2006: Message edited by: ling qin ]
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The print(root,"") is outside the recursive method, the initial call that starts everything going.

Building up a string of the whole thing is only slightly trickier. It has the risk that a tree with millions of nodes will run out of memory but not on a small exercise.

Draw your tree on paper and "play computer" to see if this walks through the nodes in the order you want and builds a tree-like picture. Then fix it up a bit to be compilable Java and see what it makes.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic