home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / c / 12261 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  3.0 KB
  1. Path: sparky!uunet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: general tree
  5. Message-ID: <3222@dozo.and.nl>
  6. Date: 13 Aug 92 08:01:57 GMT
  7. References: <1992Aug11.200208.19716@infonode.ingr.com>
  8. Organization: AND Software BV Rotterdam
  9. Lines: 104
  10.  
  11. In article <1992Aug11.200208.19716@infonode.ingr.com> dpm@wizard.b29.ingr.com (David Mikesell) writes:
  12.  
  13. |I am beginning work on a C program that will manipulate a general tree, i.e.
  14. |a tree in which each node can have an arbitrary number of children.  An ex-
  15. |ample declaration of the structure follows:
  16.  
  17. [ data structure deleted ... ]
  18.  
  19. |problem
  20. |-------
  21. |
  22. |My problem is in initializing the structure.  Algorithms I have seen for 
  23. |building binary trees from a file or array do not appear to me to be easily
  24. |adaptible to the general case, so I am looking for some ideas on how to get
  25. |this accomplished.  Perhaps there is a better implementation of a general tree
  26. |that would make this easier...any ideas will be greatly appreciated.  Thanks,
  27.  
  28. You can easily adapt these binary tree algorithms to the general case,
  29. because every tree can be represented as a binary tree. As an example
  30. consider the following tree:
  31.  
  32.     R(A(E F G) B(H) C(I J K) D(L M))
  33.  
  34. It reads: R is the root with 4 children (A, B, C and D), A has three
  35. children (E, F and G) etc.
  36.  
  37. This tree can be converted as follows:
  38.  
  39. - the left pointer of a node points to a list containing the children
  40.   of the node.
  41.  
  42. - the right pointer points to the next node at the same level (siblings).
  43.  
  44. The tree would look something like this:
  45.  
  46.     R
  47.     |
  48.     A-----B-----C-----D
  49.     |     |     |     |
  50.     E-F-G H     I-J-K L-M
  51.  
  52. Well, at least it looks like a binary tree to me ;-)
  53.  
  54. Throwing in some grammar stuff might help implementing the initialization
  55. of such a tree:
  56.  
  57. Tree         -> Node Children
  58.  
  59. Children    -> ( Tree NextChild
  60.         -> /* nothing */
  61.  
  62. NextChild    -> Tree NextChild
  63.         -> )
  64.  
  65. Directly from this small grammar, the following (heavily recursive)
  66. functions can be derived:
  67.  
  68. ---------------------------------------------------------------------------
  69. NODE *Tree() {
  70.  
  71. NODE *Root= Node();            /* Read current node */
  72.  
  73. Root->Left=  Children();        /* Link the list of kids */
  74. Root->Right= NULL;            /* All alone at the top level */
  75.  
  76. return Root;
  77.  
  78. } /* Tree */
  79.  
  80. NODE *Children() {
  81.  
  82. NODE *Node= NULL;            /* Assume no kids */
  83.  
  84. if (has_children()) {            /* Some appropriate predicate */
  85.     Node= Tree();            /* Read the first child */
  86.     Node->Right= NextChild();    /* Link the siblings */
  87. }
  88.  
  89. return Node;
  90.  
  91. } /* Children */
  92.  
  93. NODE *NextChild() {
  94.  
  95. NODE *Node= NULL;            /* Assume no sibblings */
  96.  
  97. if (has_sibblings()) {            /* Some appropriate predicate */
  98.     Node= Tree();            /* Get first sibling */
  99.     Node->Right= NextChild();    /* Link the others */
  100. }
  101.  
  102. return Node;
  103.  
  104. } /* NextChild */
  105. ---------------------------------------------------------------------------
  106.  
  107. Note that a lot of tail recursion can be removed by using an iteration
  108. (a while loop) instead.
  109.  
  110. I hope this is of any help to you,
  111.  
  112. kind regards,
  113.  
  114. Jos aka jos@and.nl
  115.