• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

Recursion with multithreading  RSS feed

 
Ranch Hand
Posts: 52
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So I wrote a program in java which involved making a complete binary tree, now I wish to print this tree. Here lies the problem printing a tree is very complicated since while exploring all the nodes for the tree we do so recursively and every recursion must be completed before going to the next recursion. Consider this...

Suppose the Each node is linked with two of its children link this...



We call the method recursively some what like this


Now the problem is this..Supoose there are 7 nodes like this..

                                   Node1
                                /           \
                        Node2           Node3
                       /        \          /        \
                  Node4  Node5   Node6    Node7

Here after Node 2 is printed I don't want the recursion to print Node 4 instead I want its thread to wait while all other recursions in that level has been completed that is I want  Node 2's recursion to wait until Node 3 is printed this is because if I print Node 4 without printing node 3 I can never come back to the position of Node 3.

Now to implement this I have two variable "Lock" and "SubLock" these variables hold the value of the next node that should be printed for example after printing Node 2 Lock=2 and SubLock=2 that is print the 2nd Node in the 2nd level of the tree.
Other threads wait if its not there turn that is if Lock and SubLock don't specify that its there turn. I am not very used to multi threading and using wait() , notify() , sleep() ,etc.
Can someone suggest me how to apply inter thread communication to make the threads wait and execute correctly ?

Here's a part of my code which does all the important stuff..its still messed up but I am trying to make it right..

The SpacePrinter() method prints all the spaces correctly..



this gives a messed up output like this..

                                     Node1
                                /                 \
                                          Node3Node2
                     /                 \                     /                 \
               Node7                              Node4 Node5
 
Saloon Keeper
Posts: 9255
177
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So, if you want to process each node sequentially, why are you using multiple threads in the first place? You're just making the code more complex and you're losing efficiency due to synchronization overhead.

To do a breadth-first iteration of a tree, start by creating a queue of nodes and add the root node to it. Then, while the queue is not empty, remove a node from the front of the queue, process it, and add its children to the back of the queue.
 
Stephan van Hulst
Saloon Keeper
Posts: 9255
177
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your code will be much more easy to read and understand for others if you use common style conventions. Start variable and method names with a lowercase letter, and put each statement on a separate line.
 
Arpan Ghoshal
Ranch Hand
Posts: 52
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes a Breadth First Search would be great , thank you Stephan van Hulst. Threading really brings unnecessary complexity. Can you help me with one more thing ? Since I not only want to print the nodes in BFS order but I also want to make a tree out of it that is after each level there should be a line change to go to next level and continue the BFS traversal. This is okay for a Complete binary tree where at i th level we have 2^(i-1) nodes but if its not a complete binary tree how can I know that a level is complete  and I have to change the line ?

By the way sorry for the messy code writing style I am still trying to improve and use the conventions.
 
Arpan Ghoshal
Ranch Hand
Posts: 52
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks to Stephan van Hulst for suggesting Breadth First Search I managed to create a tree builder although it has one limitation it only works for correctly for complete binary trees.

For anyone interested to draw a complete binary tree on the console can use my code. There is one requirement, every node of the tree should implement the Drawable interface I have created in order to display the tree correctly.

The Drawable interface has some simple methods that you must override that's it then just call startBuild() and pass the root of the tree to display it.. it works some what correctly I managed to balance the spaces so that the tree is displayed correctly.

Here is the code with an example tree showing a Family hierarchy (where everyone has exactly two children  )...





Output of the above Family example :



If anyone has any suggestions or Ideas please reply...
 
Arpan Ghoshal
Ranch Hand
Posts: 52
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Seems like the link of the output is not working..
here is the link if you are interested : https://ibb.co/iMeO1J
Capture.JPG
[Thumbnail for Capture.JPG]
 
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Threads are great if some part of the processing is waiting on something external the thread that's waiting can continue to wait, while a thread that isn't waiting forges on ahead. For processing-intensive tasks, more threads than processors actually creates overhead.
 
Marshal
Posts: 60168
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

sonai kale wrote:Threads are great . . . .

Is that relevant to the current question?
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!