3

Any idea how to print a tree like this?

       2               
      / \       
     /   \      
    /     \     
   /       \    
   7       5       
  / \       \   
 /   \       \  
 2   6       9   
    / \     /   
    5 8     4
JASON
  • 7,371
  • 9
  • 27
  • 40
  • The problem is that you need to know the depth of your tree to identify the correct horizontal position of the first and any oncoming element, so the algorithm might differ from the horizontal one and will be less effective – HamoriZ Aug 01 '14 at 08:11
  • 6
    "Anyone could provide elegant code..." It is not the purpose of stackoverflow to get other people do the coding for you. You should do the coding yourself, and if you have a specific problem, ask a specific question. In other words: show what you have tried so far and where you are stuck. Having others dump the code for you will not help you, you will not learn from it and if questions like this were tolerated, SO would soon be flooded with code-dump requests from people who dont even want to learn. – Arne Mertz Aug 01 '14 at 08:19
  • One way is to first compute recursively for each node the size of its bounding box and the positions of the node and its two children in the box. Then, initialize a 2d array of characters of the size of the root's bounding box, and fill it in with characters recursively. Finally, print out the array on the screen. – iavr Aug 01 '14 at 08:21
  • possible duplicate of [How to print binary tree diagram?](http://stackoverflow.com/questions/4965335/how-to-print-binary-tree-diagram) – Jiří Pospíšil Aug 01 '14 at 08:35
  • 3
    @JASON then *show* your code, say where you see problems and ask how to fix them. From what you posted this is just another "please provide code for my problem" question. Maybe you have put some effort into it, but the question does not show that. – Arne Mertz Aug 01 '14 at 08:39
  • The output requires a prior traversal of the tree to retrieve the names of the nodes to be printed at each level. The offset of the root is then calculated from the longest list of node names. Then a second traversal prints node names and left or right diagonals based on whether the node has left or right children or not. Not too complicated, I think. Why don't you try and write it, and we'll see if we think it's elegant. – david.pfx Aug 01 '14 at 08:57

1 Answers1

1

The horizontal solution works well as you can use a pre-order depth-first search (as you've shown) to construct the tree from each subtree, which aligns nicely with the way the console outputs one row at a time.

The vertical solution is more difficult, because you need to know all of the nodes at the end of the tree to calculate the full width. Therefore, you need to analyse the tree, store the data and then begin plotting.

The other option, while maybe not so "elegant" (definition dependent), would be to use something like a curses library, in which the concepts of display columns and rows are interchangeable.

learnvst
  • 15,455
  • 16
  • 74
  • 121
  • The vertical solution isn't that hard; all it involves is a breadth first visit for output, after a first visit to determine the topology. – James Kanze Aug 01 '14 at 08:49