*
The moose likes Beginning Java and the fly likes [Help] Recursive method Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "[Help] Recursive method" Watch "[Help] Recursive method" New topic
Author

[Help] Recursive method

ling qin
Greenhorn

Joined: Nov 20, 2006
Posts: 2
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 ]

<a href="http://www.anythingwewant.com" target="_blank" rel="nofollow">http://www.anythingwewant.com</a>
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
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 ]

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
ling qin
Greenhorn

Joined: Nov 20, 2006
Posts: 2
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

Joined: Jan 29, 2003
Posts: 8791
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: [Help] Recursive method
 
Similar Threads
BST problem (Online waiting)
A continuation of my previous post, if I may...
cannot be applied to
getting stackOverFlowError
Draw binary tree structure