• Post Reply Bookmark Topic Watch Topic
  • New Topic

Displaying All Paths in a Tree  RSS feed

 
Jimmy Howard
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey again,

This time I'm completely lost. I know what the tree data structure is, how it works, etc., but I need to design a method that will sequentially print out all the paths in the tree (i.e. for each node).

The method as provided is



Now the string that must be returned needs to be of the format:

root.getData() + " " + path + "\n"
root.getData()[1] + " " + path[1] + "\n"
etc.

The pseudocode I was thinking of doing was something along the lines of:



Problems:

(1) I don't know how to determine "path" before the left and right children check (the root node's path is "", the first left node's path is "0", the first right node's path is "1", pattern continues with left being "0" and right being "1").
(2) I don't know where to put newlines precisely.
(3) I'm not sure how to get the print layout precisely as it is supposed to be. At most I've been able to just get the last number in the sequence (i.e. if it was supposed to be "1000", I could get "0".

Honestly I really just need help with the pseudocode formulation, especially in regards to the logic and formatting. I think once I have an understanding of what is going on, I can solve it. And yes, I've gone through a couple pseudocode rewrites (a few hours worth) and haven't gotten anywhere which is slightly unnerving. Thanks so much and please let me know ASAP if more info is needed!!
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jimmy Howard wrote:(1) I don't know how to determine "path" before the left and right children check (the root node's path is "", the first left node's path is "0", the first right node's path is "1", pattern continues with left being "0" and right being "1").
(2) I don't know where to put newlines precisely.
(3) I'm not sure how to get the print layout precisely as it is supposed to be. At most I've been able to just get the last number in the sequence (i.e. if it was supposed to be "1000", I could get "0".

Do you notice that all your questions have to to with the display? Also: you haven't described to us what the print layout IS supposed to be.

My question: Forget about printing for the moment. Do you know how to write a method to "walk" the tree recursively? Because that will almost certainly be a good point to start from.

One little tip (although I don't know whether it fits with your "required format"): It's often easier to print out trees on a line-formatted medium if you rotate them 90° - ie, have the paths go across the page and the connectors down (or just use indenting). This is rather like the form you see in Windows Explorer when it displays a directory structure.

HIH

Winston
 
Carey Brown
Saloon Keeper
Posts: 3309
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is BinaryNodeInterface and where does Character play a role?
 
Jimmy Howard
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
BinaryNodeInterface is an interface for a class BinaryNode, which creates a binary tree with the following available methods:



As for the format, the nodes contain data as characters ('A', 'a', etc.), with a data structure like:

A
/ \
b d
/\ /\
t v Q W

Should print:

A
b 0
t 00
v 01
d 1
Q 10
W 11

For simply traversing the tree I was using a variation of:



Which seemed to work fine...printing in the correct format on the other hand...still no clue...although it was suggested to me that I use a Stack I'm not sure even where to start with that? (Hopefully that answers your questions!)
 
Carey Brown
Saloon Keeper
Posts: 3309
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator



Returning a String doesn't seem to serve any purpose seeing as the prints may happen at any level of recursion.

I'd pass in a String of the currentPath that you'll be adding '0' or '1' to as you descend the tree. This will be used in the prints.

At line 3 I'd suggest printing the root node.

 
Jimmy Howard
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is totally my fault, but essentially there shouldn't be any print statements and the returned String should be:

"A\n
b 0\n
t 00\n
v 01\n
d 1\n
Q 10\n
W 11\n"

 
Jimmy Howard
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also I can't modify what is being passed into the method...
 
Carey Brown
Saloon Keeper
Posts: 3309
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jimmy Howard wrote:Also I can't modify what is being passed into the method...

Then getAllPaths() should not be the recursive method but the one calling the recursive method and the recursive method should be modified as I suggested but a StringBuilder parameter should also be passed down so that instead of printing you are appending to the StringBuilder.
 
Jimmy Howard
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't think the getAllPaths() should be the recursive method either and I also think there should be allowed to be multiple parameters, but neither of those things are allowed per the assignment.
 
Carey Brown
Saloon Keeper
Posts: 3309
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jimmy Howard wrote:I don't think the getAllPaths() should be the recursive method either and I also think there should be allowed to be multiple parameters, but neither of those things are allowed per the assignment.

I think it might be better if you gave us the requirements exactly as they were specified to you, rather than us having to work out what is and isn't allowed at each stage. I suspect most of us have an idea how we'd do it, but you've clearly been given artificial constraints that might not allow it; and we need to know them ALL.

Winston
 
Jimmy Howard
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That is completely my fault; I'm so sorry.

Basically here are the requirements:

- The method cannot be modified (no new parameters, no changing of return type etc.)
- No new methods can be added
- The method must return as a string:
The root data, then a space, then the root path, then a newline; for the entire tree; with left branches represented as "0" and right branches represented as "1"; i.e.

A
/ \
b R
/ \ / \
W q t P

Would return:

"A
b 0
W 00
q 01
R 1
t 10
P 11"

- A traversal must be used (can be any type, although preorder is suggested)
- No imports may be used

...and I think that's it?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!