home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / c / 16243 < prev    next >
Encoding:
Text File  |  1992-11-09  |  1.9 KB  |  54 lines
  1. Organization: Applications Software, Carnegie Mellon, Pittsburgh, PA
  2. Path: sparky!uunet!ferkel.ucsb.edu!taco!gatech!swrinde!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!news.sei.cmu.edu!fs7.ece.cmu.edu!crabapple.srv.cs.cmu.edu!andrew.cmu.edu!rr2p+
  3. Newsgroups: comp.lang.c
  4. Message-ID: <UezhlN_00VQs4rjqFN@andrew.cmu.edu>
  5. Date: Mon,  9 Nov 1992 16:47:05 -0500 
  6. From: Richard Dale Romero <rickr+@CMU.EDU>
  7. Subject: Re: Printing out trees
  8. In-Reply-To: <BxG3py.LoA@cck.coventry.ac.uk>
  9. References: <gezTJc_00VQsAo9Vpl@andrew.cmu.edu>
  10.     <BxG3py.LoA@cck.coventry.ac.uk>
  11. Lines: 41
  12.  
  13. No, that's not really what I meant--I meant in a formatted way
  14. so that I could tell what the child-parent relations were...
  15.  
  16. I did think of an acceptable way, if anyone cares to know.
  17. You need to have a queue implementation also, which
  18. isn't hard to do, though, and if you try to queue a null
  19. node, it just doesn't queue anything.
  20.  
  21. Step 1)  Assign every node it's in-order numbering,
  22.     node->number, and a depth variable, node->depth
  23.     This is the one where you number your left
  24.     children, number yourself, then number
  25.     your right children (at least I think this
  26.     is the in-order traversal :-)
  27.  
  28. Step 2) Queue the root of the tree
  29.  
  30. Step 3) Start while loop that stops when queue is empty
  31.  
  32. Step 4) De-queue top element, and if this element is at a
  33.     different depth than the previous one, print
  34.     newline, and set cur_x = 0
  35.  
  36. Step 5) Queue it's left child, then right child
  37.  
  38. Step 6) Space over (cur_node->number - cur_x) "blocks"
  39.  
  40. Step 7) Print current node value, then set
  41.     cur_x = cur_node->number + 1
  42.  
  43. Step 8) End of while loop.
  44.  
  45. At least, I think that's what my code does....
  46.  
  47. Regardless it will print out a node such that its direct children
  48. are on the line directly below it, *every* item in the left
  49. sub-tree appears to the left of the current node, and *every* item
  50. in the right sub-tree appears to the right of the current node.
  51.  
  52. -rick
  53.  
  54.