How To Draw A Tree Recursively In Java Sou

#one

D.I.C Head

Reputation: one

Posts: 64
Joined: 25-Jan xvi

Drawing a binary tree using recursion

Posted 03 March 2016 - 10:28 AM

I am self studying using Robert Lafore'due south information structure book.

One of problems from the recursion section is to draw a binary tree on the screen with characters using recursion.

Draw this tree using a recursive makeBranches() method with arguments left and right, which are the endpoints of a horizontal range. when you outset enter the rotuine, left is 0 and right is the number of characters(including dashes) in all the lines, minus ane. You depict an Ten in the center of this range. And so the method calls itself twice: in one case for the left half of the range and once for the right half. Return when the range gets besides small. Y'all might desire a display() method.

Expected output for 16

-------10--------
----10-------X---
--X---X---10---X-
-Ten-Ten-X-10-X-X-X-Ten
XXXXXXXXXXXXXXXX

Well, I haven't fabricated much of a progress on this one because I'm non sure if I have fully understood writing a method with two recursions in it. I'd assume for this problem, I would have to use an approach similar to writing a binary search with recursion.

Below is what I wrote with the information that I've gathered from the question.

public class TreeApp { public static char[][] tree;   public static void makeBranches(int left, int right){     if(left==right)         return;      int mid = (left+correct)/2;       makeBranches(left,mid);      makeBranches(mid+i,right);  }   public static void chief(String[] args) {       }  }

I think the beginning recursion will take care of the left one-half of the range and 2nd, the other half. The biggest trouble is that I can not visualize/pic how the stacks are gona exist divided and what values each of them will hold.

Any suggestions or help will be greatly appreciated.

Is This A Good Question/Topic? 0

#two newlyfe

D.I.C Head

Reputation: 1

Posts: 64
Joined: 25-January sixteen

Re: Drawing a binary tree using recursion

Posted 03 March 2016 - 10:41 AM

And just mostly speaking, when people exercise employ two recursions in their code. Exercise they visualize everything to the lesser level of stacks? Is it only me who's having trouble picturing how the stacks are existence divided/made?

#3 Piet Souris

D.I.C Caput

Reputation: 44

Posts: 207
Joined: 01-Dec xv

Re: Cartoon a binary tree using recursion

Posted 03 March 2016 - 03:29 PM

how-do-you-do newlyfe,

well, information technology is always a good matter to start with a concrete example, simply to get an idea of what's going on.

And so, say we offset with makeBranches(0, 39).

Now, these are the endpoints of a segment (closed interval), and so the number of elements is 40.
Then, imagine nosotros draw 20 dashes, an 'X', and again xx dashes.
And then, nosotros divide the twoscore points into 2 equal halves, i.e. [0, 19] and [20, 39].
Nosotros at present call 'makeBranches(0, 19)' followed by 'makeBranches(20, 39)'.

Two things to accept into account:

one) when to stop using recursion? Well, say the segment is [0,ane]. We have ii elements, and we tin can even so draw a dash, an '10' and another nuance. What virtually the segment [1,1]? Can we draw an 'X', and/or can we go deeper into the recursion?

2) the most difficult part is: if we have divided [0,39] into the segments [0, 19] and [20, 39], how exercise nosotros get, with all the recursion, these ii segments to be fatigued on the aforementioned line? I see no immediate solution, and then possibly we need this 'makeBranches' render a string, containing 'firstrow\nseconderow\north...'. Not piece of cake, merely elegant and very much worth the effort.

Does your textbook take anything to say about this?

And anyway: recursion is often elegant, but as with all things: it takes practice.

#four newlyfe

D.I.C Head

Reputation: i

Posts: 64
Joined: 25-January 16

Re: Drawing a binary tree using recursion

Posted 03 March 2016 - 09:08 PM

View Post Piet Souris, on 03 March 2016 - 03:29 PM, said:

hi newlyfe,

2) the near difficult part is: if we have divided [0,39] into the segments [0, 19] and [20, 39], how do we get, with all the recursion, these 2 segments to be drawn on the same line? I encounter no immediate solution, so maybe we need this 'makeBranches' return a string, containing 'firstrow\nseconderow\n...'. Non like shooting fish in a barrel, but elegant and very much worth the effort.

This exactly!. I hateful I guess I tin somehow get the recursion working merely incorporating print statements to get the desired output is so difficult. And I think the inputs should be squares of 2. And the textbook doesn't say much more than other than what I posted. This is the residual.

Write a master() program to draw the tree past calling makeBrnaches() and brandish(). Permit main() to determine the line length of the brandish(32,64,or w/e)Ensure that the array that holds the characters for display is no longer than it needs to exist. what is the human relationship of the number of lines to the line width?

#5 newlyfe

D.I.C Head

Reputation: ane

Posts: 64
Joined: 25-January xvi

Re: Cartoon a binary tree using recursion

Posted 03 March 2016 - 09:29 PM

I've made some improvements(more like finished bones set ups).

public form TreeApp { 	public static char[][] tree; 	  	  	 		 	public static void principal(Cord[] args) { 		col = 16; 		numRows = (int)(Math.log(col)/Math.log(two)) + 1; 		tree = new char[numRows][col]; 		for(int i=0; i<numRows;i++){ 			for(int j=0;j<col;j++){ 				if(j==0) 					tree[i][j] = '-'; 				else 					tree[i][j] += '-'; 				 			} 		} 		brandish(numRows,col); 		 		 		  	} 	public static void makeBranches(int left, int right){ 		if(left==right) 			return; 		 		int mid = (left+right)/2; 		 		 		makeBranches(left,mid); 		 		makeBranches(mid+1,right); 		 		 	} 	public static void display(int numRows, int col){ 		for(int i=0; i<numRows;i++){ 			for(int j=0;j<col;j++){ 				System.out.print(tree[i][j]); 				 			} 			Organization.out.println(); 		} 	}  }

This mail service has been edited by newlyfe: 03 March 2016 - 09:32 PM

#6 newlyfe

D.I.C Head

Reputation: 1

Posts: 64
Joined: 25-January 16

Re: Drawing a binary tree using recursion

Posted 03 March 2016 - 11:18 PM

Double recursion really is a nightmare. It'southward like making a wish to a fairy godmother of java to make it work.

#vii macosxnerd101

Reputation: 12800

Posts: 45,992
Joined: 27-Dec 08

Re: Drawing a binary tree using recursion

Posted 03 March 2016 - 11:nineteen PM

Please avert needlessly bumping your thread.

#8 Piet Souris

D.I.C Head

Reputation: 44

Posts: 207
Joined: 01-December 15

Re: Drawing a binary tree using recursion

Posted 06 March 2016 - 03:08 AM

hi newlyfe,

I have been a flake busy lately, had a expect at your problem yesterday.
I must say, I plant information technology much more hard than I expected.
Too, I did not understand quite the consignment. Therefore, I decided
to follow my own idea, with my own parameters.

I make utilise of a helper method, with parameters linelength, level and
a List<List<Cord>>, not according to the specs I admit, only quite
elegant I promise. I gave up any effort to format the generated substrings
while existence in the recursion, That turned out to be likewise complicated.
Therefore, I decided to allow the formatting be part of the 'makeBranches'
method itself, by applying a nice method from Java 8, concerning the joining
of elements of a list.

So, I diverged from the assignment that I did not understand well enough.
I hope nevertheless that my code serves as some other example of recursion.

If you have any comment (even if you exercise not like information technology at all!), I similar to hear.

Greetings,
Piet

(btw: I left the check of a correct linelength (of the class 2^n) up to y'all!)

/**  *  * @writer Piet  */  public class BinaryTreeDrawing {          public static void main(String... args) {         BinaryTreeDrawing btd = new BinaryTreeDrawing();         System.out.println(btd.makeBranches(32));     }          private Cord makeBranches(int linelength) {         // linelength must be of the course two^north, i.east. 4, 8, xvi, et cetera         if (!isLengthCorrect(linelength)) {             throw new IllegalArgumentException("parameter must exist of course 2^n");         }         List<List<String>> listing = new ArrayList<>();         makeBranchesHelp(linelength - 1, 0, listing);         return addDashes(listing);     }          private boolean isLengthCorrect(int length) {         return true;     }          private void makeBranchesHelp(int length, int level, List<List<String>> list) {         // // if at that place is no Listing<Cord> nonetheless at the required level, create ane         if (list.size() == level) {             list.add(new ArrayList<>());         }         String temp = makeDashesStringWithX(length);         listing.go(level).add(temp);         if (length == ane) return;         makeBranchesHelp(length / two, level + 1, list);         makeBranchesHelp(length / 2, level + 1, list);     }          private String makeDashesStringWithX(int length) {         StringBuilder sb = new StringBuilder();         for (int i = i; i <= length; i++) sb.append('-');         sb.setCharAt(length / 2, 'X');         return sb.toString();     }          private String addDashes(Listing<Listing<String>> list) {         Listing<String> templist = list.stream().map(eastward -> joinList(e, "|")).collect(Collectors.toList());         render joinList(templist, "\n");     }          private Cord joinList(List<String> list, String joiner) {         return listing.stream().collect(Collectors.joining(joiner));     } }