home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / c / 18763 < prev    next >
Encoding:
Text File  |  1992-12-22  |  3.9 KB  |  192 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!darwin.sura.net!spool.mu.edu!yale.edu!ira.uka.de!smurf.sub.org!easix!bc3!ktf
  3. From: ktf@bc3.GUN.de (Klaus ter Fehn)
  4. Subject: Re: What's wrong with the following code...?
  5. Organization: private
  6. Date: Mon, 21 Dec 1992 11:42:59 GMT
  7. Message-ID: <BzLxvp.1LM@bc3.GUN.de>
  8. References: <BzKnzo.Gt@cs.uiuc.edu>
  9. Lines: 181
  10.  
  11. In article <BzKnzo.Gt@cs.uiuc.edu> ctaylor@cs.uiuc.edu (Conrad Taylor) writes:
  12.  
  13. >         Could someone please assist me with the following code which it
  14. >to build a binary tree and print out the tree nodes?  Thanks in advance to
  15. >all that reply.
  16.  
  17. I think it's a common beginner's-problem, so I post it.
  18.  
  19. >#include <stdio.h>
  20. >#include <stdlib.h>
  21.  
  22. >struct node {
  23. >   int Info;
  24. >   struct node *LeftTree;
  25. >   struct node *RightTree;
  26. >};
  27.  
  28. >typedef struct node *NODEPTR;
  29.  
  30. >NODEPTR Root;
  31.  
  32. >void    TreeInsert(int Number, NODEPTR Root);
  33. >void    TreeBuild(NODEPTR Root);
  34. >void    TreePrint(NODEPTR Root);
  35.  
  36.  
  37.  
  38.  
  39. >void TreeBuild(NODEPTR Root)
  40. >{
  41. >    Root = NULL;
  42.  
  43. >    TreeInsert(6, Root);
  44. >    TreeInsert(4, Root);
  45. >    TreeInsert(8, Root);
  46. >    TreeInsert(7, Root);
  47. >    TreeInsert(9, Root);
  48. >    TreeInsert(5, Root);
  49. >    TreeInsert(3, Root);
  50. >} /* end TreeBuild */
  51.  
  52.  
  53. And now here's the problem: In Funktion TreeInsert You want to change the
  54. content of 'Root'. But You define here a local-var named 'Root'. You see,
  55. You're changing the COPY of this Pointer, not the Pointer itself.
  56. You got to give the Funktion the adress of this Pointer, if You want it 
  57. to change the Pointer. 
  58. I've added a working version at the end.
  59.  
  60.  
  61. >void TreeInsert(int Number, NODEPTR Root)
  62. >{
  63. >    if (Root == NULL)
  64. >      {
  65. >     Root = (NODEPTR)malloc(sizeof(struct node));
  66. >     Root->Info  = Number;
  67. >     Root->LeftTree = NULL;
  68. >     Root->RightTree = NULL;
  69. >      }
  70. >    else if (Number < Root->Info)
  71. >      TreeInsert(Number, Root->LeftTree);
  72. >    else if (Number > Root->Info)
  73. >      TreeInsert(Number, Root->RightTree);
  74. >    /* else if (Number = Root->Info) */
  75. >    /*   do nothing since Number is already in the tree. */
  76. >} /* end TreeInsert */
  77.  
  78.  
  79.  
  80.  
  81. >void TreePrint(NODEPTR Root)
  82. >{
  83. >   if (Root != NULL)
  84. >     {
  85. >    TreePrint(Root->LeftTree);
  86. >    printf("%2d\n", Root->Info);
  87. >    TreePrint(Root->RightTree);
  88. >     }
  89. >}
  90.  
  91.  
  92.  
  93.  
  94. >int main(void)
  95. >{
  96. >  printf("Start the program.\n"); 
  97. >  TreeBuild(Root);
  98. >  TreePrint(Root);
  99. >  printf("Finish the program.\n"); 
  100.  
  101. >  return 0;
  102. >}
  103.  
  104. And now here is a working Version:
  105.  
  106. #include <stdio.h>
  107. #include <stdlib.h>
  108.  
  109. struct node {
  110.    int Info;
  111.    struct node *LeftTree;
  112.    struct node *RightTree;
  113. };
  114.  
  115. typedef struct node *NODEPTR;
  116.  
  117. NODEPTR Root;
  118.  
  119. void    TreeInsert(int Number, NODEPTR *Root);
  120. void    TreeBuild();
  121. void    TreePrint(NODEPTR Root);
  122.  
  123.  
  124.  
  125.  
  126. /* void TreeBuild(NODEPTR Root) */
  127. void TreeBuild()
  128. {
  129.     Root = NULL;
  130.  
  131.     TreeInsert(6, &Root);
  132.     TreeInsert(4, &Root);
  133.     TreeInsert(8, &Root);
  134.     TreeInsert(7, &Root);
  135.     TreeInsert(9, &Root);
  136.     TreeInsert(5, &Root);
  137.     TreeInsert(3, &Root);
  138. } /* end TreeBuild */
  139.  
  140.  
  141.  
  142.  
  143. void TreeInsert(int Number, NODEPTR *Root)
  144. {
  145.     if (*Root == NULL)
  146.       {
  147.      *Root = (NODEPTR)malloc(sizeof(struct node));
  148.      (*Root)->Info  = Number;
  149.      (*Root)->LeftTree = NULL;
  150.      (*Root)->RightTree = NULL;
  151.       }
  152.     else if (Number < (*Root)->Info)
  153.       TreeInsert(Number, &(*Root)->LeftTree);
  154.     else if (Number > (*Root)->Info)
  155.       TreeInsert(Number, &(*Root)->RightTree);
  156.     /* else if (Number = (*Root)->Info) */
  157.     /*   do nothing since Number is already in the tree. */
  158. } /* end TreeInsert */
  159.  
  160.  
  161.  
  162.  
  163. void TreePrint(NODEPTR Root)
  164. {
  165.    if (Root != NULL)
  166.      {
  167.     TreePrint(Root->LeftTree);
  168.     printf("%2d\n", Root->Info);
  169.     TreePrint(Root->RightTree);
  170.      }
  171. }
  172.  
  173.  
  174.  
  175.  
  176. int main(void)
  177. {
  178.   printf("Start the program.\n"); 
  179.   TreeBuild(Root);
  180.   TreePrint(Root);
  181.   printf("Finish the program.\n"); 
  182.  
  183.   return 0;
  184. }
  185.  
  186. Greetings...
  187. -- 
  188. Klaus ter Fehn        <ktf@bc3.GUN.de>
  189. Neanderstr. 4        {mcshh,smurf,unido}!easix!bc3!ktf
  190. 4000 Duesseldorf 1
  191. FRG / Germany        Tel.: +49-211-676331
  192.