-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I have following structs:

typedef struct item
{
    char ItemName[NAME_SIZE];

typedef struct node
{
    Item item;
    struct node *left;
    struct node *right;

typedef struct tree
{
    Node *root;
    int size;

What I'm trying to do is write a function to count nodes with 0
children, 1 child, 2 children.  In my program, I use a variable of
type Tree to create a binary tree of names.  But my function to count
the nodes doesn't work.  My idea was to use another struct to hold the
numbers:

typedef struct count{
    int NoChild;
    int OneChild;
    int TwoChild;

And then do this:

void CountNodes(Tree * root, Count NodeCount)
{
    if(root->left != NULL){
        if(root->right == NULL){
            NodeCount.OneChild++;
        }
        else{
            NodeCount.TwoChild++;
        }
        CountNodes(root->left, NodeCount);
    }
    else if(root->right != NULL){
        if(root->left == NULL){
            NodeCount.OneChild++;
        }
        else{
            NodeCount.TwoChild++;
        }
        CountNodes(root->right, NodeCount);
    }

What I get is an error that

main.c:204: structure has no member named `left'
main.c:205: structure has no member named `right'

That actually seems to make sense, after I think about it -- but I
don't understand how to access the left/right pointers.  The program
works fine otherwise.

Any clues would be appreciated.  Thanks.

mp

- ------------------------------------------------------------------

Portland, Oregon USA                       http://www.*-*-*.com/
- --
Amount of all stock owned by the least wealthy 90% of America: 18%
Amount of all stock owned by the most wealthy 1% of America: 41%
                     [Economic Policy Institute]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v0.9.8 (GNU/Linux)
Comment: Encrypted with Mailcrypt 3.5.3 and GNU Privacy Guard

iD8DBQE3lrJ6755rgEMD+T8RAk2/AKCyCDXoUSFjoA2SnQ30owvLpAK0aQCeJWzT
MQovgFN5czoNBuDOk98OFN4=
=K9cU
-----END PGP SIGNATURE-----

You have fallen into a very typical problem -- too many conflicting names
and possible overuse of typedef.

You have declared a type called "Tree." "Tree" has a member called "root" of
type "Node." "root" has members "left" and "right."

To access "left" from "tree," you must say:

tree->root->left.

Unfortunately for the comprehensibility of your program, you then declare a
Tree pointer variable called "root" for your function. This was already
confusing, now it is more so. Thus, within your function, you must say:

root->root->left.

Solution -- try renaming everything in a more understandable way.
--

Paul Lutus
www.arachnoid.com

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

    Paul> You have fallen into a very typical problem -- too many
    Paul> conflicting names and possible overuse of typedef.

    Paul> You have declared a type called "Tree." "Tree" has a member
    Paul> called "root" of type "Node." "root" has members "left" and
    Paul> "right."

    Paul> To access "left" from "tree," you must say:

    tree-> root->left.

    Paul> Unfortunately for the comprehensibility of your program, you
    Paul> then declare a Tree pointer variable called "root" for your
    Paul> function. This was already confusing, now it is more
    Paul> so. Thus, within your function, you must say:

    root-> root->left.

    Paul> Solution -- try renaming everything in a more understandable
    Paul> way.  --

Thanks, you're right about the naming, it's crap.  I'm planning on
fixing that.  I thought I'd tried the double-arrow routine but I see
I hadn't -- or, I'd done something else wrong, as well.  Here's a
simpler example of the problem I'm having.  It gives incorrect results
(actually, it gives no results at all, the node count variables are
simply filled with random numbers).

8<------------------------------------------->8
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct TreeNode
{
  int data;
  struct TreeNode *LeftPtr;
  struct TreeNode *RightPtr;

typedef struct TreeNode TREENODE;
typedef TREENODE *TREENODEPTR;

typedef struct count{
    int NoChild;
    int OneChild;
    int TwoChild;

void InsertNode(TREENODEPTR *, int);

void InOrder(TREENODEPTR);

void CountNodes(TREENODEPTR TreePtr, Count NodeCount);

int main(void)
{

    Count NodeCount;

  int i = 0, item = 0;
  TREENODEPTR RootNode = NULL;

  srand(time(NULL));
  printf("The items placed in the tree are:\n");

  for(i = 0; i <=10; i++){
    item = rand() % 15;
    printf("%3d", item);
    InsertNode(&RootNode, item);
  } /* end for */

  printf("\n\nThe InOrder transversal is: ");
  InOrder(RootNode);

  putchar('\n');

  CountNodes(RootNode, NodeCount);

  printf("the count is 0)%d, 1)%d, 2)%d\n", NodeCount.NoChild,
         NodeCount.OneChild, NodeCount.TwoChild);

  return 0;

void InsertNode(TREENODEPTR *TreePtr, int value)
{
  if(*TreePtr == NULL){
    *TreePtr = malloc(sizeof(TREENODE));

    if(*TreePtr != NULL){
      (*TreePtr)->data = value;
      (*TreePtr)->LeftPtr = NULL;
      (*TreePtr)->RightPtr = NULL;
    } /* end if */
    else{
      printf("%d not inserted.  No memory available.\n", value);
    }
  } /* end if */
  else{
    if(value < (*TreePtr)->data){
      InsertNode(&((*TreePtr)->LeftPtr), value);
    }
    else{
      if(value > (*TreePtr)->data){
        InsertNode(&((*TreePtr)->RightPtr), value);
      }
      else{
        printf("dup");
      }
    }
  }

void InOrder(TREENODEPTR TreePtr)
{
  if(TreePtr != NULL){
    InOrder(TreePtr->LeftPtr);
    printf("%3d", TreePtr->data);
    InOrder(TreePtr->RightPtr);
  }

void CountNodes(TREENODEPTR TreePtr, Count NodeCount)
{

    if(TreePtr->LeftPtr != NULL){
        if(TreePtr->RightPtr == NULL){
            NodeCount.OneChild++;
        }
        else{
            NodeCount.TwoChild++;
        }
        CountNodes(TreePtr->LeftPtr, NodeCount);

    } /* end if */
    else if(TreePtr->RightPtr != NULL){
        if(TreePtr->LeftPtr == NULL){
            NodeCount.OneChild++;
        }
        else{
            NodeCount.TwoChild++;
        }
        CountNodes(TreePtr->RightPtr, NodeCount);
    }
    else{
        NodeCount.NoChild++;
    }

8<------------------------------------------->8

mp

- ------------------------------------------------------------------

Portland, Oregon USA                       http://www.trollope.org
- --
Amount of all stock owned by the least wealthy 90% of America: 18%
Amount of all stock owned by the most wealthy 1% of America: 41%
                     [Economic Policy Institute]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v0.9.8 (GNU/Linux)
Comment: Encrypted with Mailcrypt 3.5.3 and GNU Privacy Guard

iD8DBQE3l18V755rgEMD+T8RAmzOAJ971pzoDznx79D+QGvBtmeqfQM4uQCeKnWo
FK39FVRk5FQPprRw4QHuukw=
=DGY9
-----END PGP SIGNATURE-----

I appear not to be getting through to you. Please remove every use of
typedef from your program. Write out each designator fully and explicitly.
Fix the errors. Then, if you want, or for job security reasons more than
anything, put the typedefs back in.

All the mental translation required to read your code is making it too hard
to interpret it correctly -- for both of us.

--

Paul Lutus
www.arachnoid.com

You naming is the problem, you have to write

   root->root->left
   root->root->right

which looks absurd, but your "tree" has the
same name "root" as its main component...

If you write
   void CountNodes(Tree *ptree, Count NodeCount)  
   ...
   ptree->root->left
   ...
   ptree->root->right
everything looks (almost) perfect.

Typ of the day: don't use separate types for pointers.
Don't use
   typedef TREE *TREEPTR;
   typedef TREE **TREEPTRPTR;
   TREE tree;
   TREEPTR tree;
   TREEPTRPTR tree;
Use
   TREE tree;
   TREE *ptree;
   TREE **pptree;
The level of reference is a much to important information
to be hidden or obscured.

--

Graz, Austria   www.hls-software.com

22 Jul 1999 11:13:15 -0700,

[much resonably good code, cut to only the relevant bits]
...
Personally I wouldn't use all-caps for longish named types
like these, but that's only a style issue.  
...
On many implementations this may not give "good" random
results.  See FAQ 13.18, 13.16. (For your simple test
program here, good randomness isn't really important.)  
...
traversal (no n)
...
Here's most of your problem.  You pass an uninitialized auto
variable NodeCount (hence containing garbage to start with)
by value to CountNodes() which then has no way to pass back
the result.  Initialize it to zeros, most easily by:
    Count /* = struct count */ NodeCount = { 0,0,0 };
      /* or just { 0 }, compiler will add remaining zeros */
and then pass it by "reference" (address) to a pointer
parameter in CountNodes().  Or have it be the return value
instead of a parameter and just assign it, but that makes
the recursion less efficient and accumulation nontransparent.  

In one case you print a full error message, in the other case
you assume the caller has printed something to which you can
just tack on a notation.  Probably better to be consistent.  

To be readable, this depends on the fact that the values
inserted are only two digits (in fact 0..14).
" %d" or "%d\n" would be more general.

Once you fix this to *NodeCount (and NodeCount->)
there are a few smaller problems:
If both left and right are nonnull, you recurse only on left.  
This test is unnecessary; if left is nonnull it took the
case above, so in here left is null and right is nonnull.

You could simplify this by using an array instead:  

typedef struct { int fanout[3]; } Count;
/* or just use a plain array, not in a struct,
   and it's automagically passed and accessed by address;
   FAQ section 6 */
...
void CountNodes (TREENODEPTR p, Count * count)
{
  int mychildren = 0;
  if( p->LeftPtr ) mychildren++, CountNodes(p->LeftPtr);
  if( p->RightPtr ) mychildren++, CountNodes(p->RightPtr);
  count->fanout[mychildren]++; /* mychildren is 0, 1, or 2 */

And this can also extend easily to non-binary trees.  

(CCed?) david.thompson at but not for trintech.com

As Paul Lutus already noted, you have ...

        A confusing profusion of similar-sounding,
        Conflicting, colliding, amazing, abounding,
        Growing in leaps of the heaps of astounding,
        Needlessly-nuisancy names!

(Sorry, I had a bad case of Dr Seuss for a moment :-) )

Seriously, though, in addition to the problem he noted ("root"
is not a "Node" but a "Tree"), this function has two or three
other major problems (depending on how you count):

 - If it takes a "Tree", it needs an auxiliary function, because
   a tree has a root "Node"; but if it takes a "Node", it does not.
   (In order to count the nodes recursively, you need to apply the
   counting task to the various nodes.)
 - The variable "NodeCount" is an ordinary type (a typedef for a
   struct -- i.e., not an array, and hence not subject to The Rule).
   Thus, it is passed by value, so whenever CountNodes changes
   an instance of that variable in any recursive call, and then
   returns from that call, the changes vanish.
 - You have to do something with the counts!

Given the same data structures, I would probably rewrite this as:

        void CountAux(struct node *p, struct count *c) {

                if (p->left != NULL) {
                        CountAux(p->left, c);
                        if (p->right != NULL) {
                                c->TwoChild++;
                                CountAux(p->right, c);
                        } else
                                c->OneChild++;
                } else if (p->right != NULL) {
                        c->OneChild++;
                        CountAux(p->right, c);
                } else
                        c->NoChild++;
        }

        struct count CountNodes(struct tree *tree) {
                struct count c;

                c.NoChild = 0;
                c.OneChild = 0;
                c.TwoChild = 0;
                if (tree->root)
                        CountAux(tree->root, &c);
                return c;
        }

Given the chance to change them, though, I would at the least
replace the "count" structure with one containing a simple array,
and rewrite the auxiliary function as something more like this:

        void CountAux(struct node *p, struct count *c) {
                int n;

                if (p != NULL) {
                        n = 0;
                        if (p->left != NULL)
                                n++;
                        if (p->right != NULL)
                                n++;
                        c->count[n]++;
                        CountAux(p->left, c);
                        CountAux(p->right, c);
                }
        }

At this point one could drop the struct entirely, making use of
The Rule to have CountNodes pass "&count[0]", but if you want to
return the value, it is nice to have a user-defined abstract type
(which, in C, is spelled "struct" rather than "type") for that.
--
In-Real-Life: Chris Torek, Berkeley Software Design Inc

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

    >> ...  typedef struct node { Item item; struct node *left; struct
    >> node *right; } Node;
    >>
    >> typedef struct tree { Node *root; int size; } Tree;
    >>
    >> ...  void CountNodes(Tree * root, Count NodeCount) ...
    >> CountNodes(root->left, NodeCount); ...  CountNodes(root->right,
    >> NodeCount);
    >>
    >> What I get is an error that
    >>
    >> main.c:204: structure has no member named `left' main.c:205:
    >> structure has no member named `right'

    Helmut> You naming is the problem, you have to write

    root-> root->left root->right

    Helmut> which looks absurd, but your "tree" has the same name
    Helmut> "root" as its main component...

    Helmut> If you write void CountNodes(Tree *ptree, Count NodeCount)
    Helmut> ...
    ptree-> root->left
    Helmut>    ...
    ptree-> root->right
    Helmut> everything looks (almost) perfect.

    Helmut> Typ of the day: don't use separate types for pointers.
    Helmut> Don't use typedef TREE *TREEPTR; typedef TREE
    Helmut> **TREEPTRPTR; TREE tree; TREEPTR tree; TREEPTRPTR tree;
    Helmut> Use TREE tree; TREE *ptree; TREE **pptree; The level of
    Helmut> reference is a much to important information to be hidden
    Helmut> or obscured.

Thanks, Helmut.  The obsession with typedef is not mine, actually.  It
seems every C/C++ book I've opened goes on and on about the
"importance" of using typedefs -- with numerous examples.  I
frequently confuse myself!  ;-)

mp

- ------------------------------------------------------------------

Portland, Oregon USA                       http://www.trollope.org
- --
Amount of all stock owned by the least wealthy 90% of America: 18%
Amount of all stock owned by the most wealthy 1% of America: 41%
                     [Economic Policy Institute]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v0.9.8 (GNU/Linux)
Comment: Encrypted with Mailcrypt 3.5.3 and GNU Privacy Guard

iD8DBQE3msTz755rgEMD+T8RAgGQAJ95GIisfp803glU2SqpXu3p0ADLaACgo78z
XFR+kYy31seCGJpyLKj6utI=
=es2i
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

    Chris> long):

    >> typedef struct node { Item item; struct node *left; struct node
    >> *right; } Node;
    >>
    >> typedef struct tree { Node *root; int size; } Tree;
    >>
    >> typedef struct count { int NoChild; int OneChild; int TwoChild;
    >> } Count;

    >> void CountNodes(Tree * root, Count NodeCount) { if(root->left
    >> != NULL){ if(root->right == NULL){ NodeCount.OneChild++; }
    >> else{ NodeCount.TwoChild++; } CountNodes(root->left,
    >> NodeCount); } else if(root->right != NULL){ if(root->left ==
    >> NULL){ NodeCount.OneChild++; } else{ NodeCount.TwoChild++; }
    >> CountNodes(root->right, NodeCount); } } /* end count nodes */

    Chris> As Paul Lutus already noted, you have ...

    Chris>   A confusing profusion of similar-sounding,
    Chris> Conflicting, colliding, amazing, abounding, Growing in
    Chris> leaps of the heaps of astounding, Needlessly-nuisancy
    Chris> names!

    Chris> (Sorry, I had a bad case of Dr Seuss for a moment :-) )

That's okay, it made me grin.  ;-)

    Chris> Seriously, though, in addition to the problem he noted
    Chris> ("root" is not a "Node" but a "Tree"), this function has
    Chris> two or three other major problems (depending on how you
    Chris> count):

The major problem being ... I'm clueless!  Stumbling around, trying to
get a glimpse of some sanity here.

    Chris>  - If it takes a "Tree", it needs an auxiliary function,
    Chris> because a tree has a root "Node"; but if it takes a "Node",
    Chris> it does not.  (In order to count the nodes recursively, you
    Chris> need to apply the counting task to the various nodes.)  -
    Chris> The variable "NodeCount" is an ordinary type (a typedef for
    Chris> a struct -- i.e., not an array, and hence not subject to
    Chris> The Rule).  Thus, it is passed by value, so whenever
    Chris> CountNodes changes an instance of that variable in any
    Chris> recursive call, and then returns from that call, the
    Chris> changes vanish.  - You have to do something with the
    Chris> counts!

Right, I had it right -- sort of -- before I made the structure; I was
passing pointers to three ints; then I got the bright idea of putting
the ints into a struct to make it more compact & forgot about the
pointer.

    Chris> Given the same data structures, I would probably rewrite
    Chris> this as:

void CountAux(struct node *p, struct count *c) {

if (p->left != NULL) {
        CountAux(p->left, c);
        if (p->right != NULL) {
        TwoChild++;
        CountAux(p->right, c);
        }
        else
        OneChild++;

else if (p->right != NULL) {
        OneChild++;
        CountAux(p->right, c);
else
        NoChild++;

struct count CountNodes(struct tree *tree) {
struct count c;

c.NoChild = 0;
c.OneChild = 0;
c.TwoChild = 0;
if (tree->root) CountAux(tree->root, &c);
return c;

    Chris> Given the chance to change them, though, I would at the
    Chris> least replace the "count" structure with one containing a
    Chris> simple array, and rewrite the auxiliary function as
    Chris> something more like this:

void CountAux(struct node *p, struct count *c) {
int n;

        if (p != NULL) {
                n = 0;
        if (p->left != NULL)
                n++;
        if (p->right != NULL)
                n++;
        count[n]++;
        CountAux(p->left, c);
        CountAux(p->right, c);
        }

    Chris> At this point one could drop the struct entirely, making
    Chris> use of The Rule to have CountNodes pass "&count[0]", but if
    Chris> you want to return the value, it is nice to have a
    Chris> user-defined abstract type (which, in C, is spelled
    Chris> "struct" rather than "type") for that.

Thanks for the help, Chris.  It's back to the struct-mines for me.

mp

- ------------------------------------------------------------------

Portland, Oregon USA                       http://www.trollope.org
- --
Amount of all stock owned by the least wealthy 90% of America: 18%
Amount of all stock owned by the most wealthy 1% of America: 41%
                     [Economic Policy Institute]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v0.9.8 (GNU/Linux)
Comment: Encrypted with Mailcrypt 3.5.3 and GNU Privacy Guard

iD8DBQE3msk5755rgEMD+T8RAnHyAJ9grH4FAuQ7AzUtyKLxBHulQaArpgCgklyv
B9ceQl7PSRAg0Za90YuPgBk=
=NkPc
-----END PGP SIGNATURE-----