counting leafs

This is a discussion on counting leafs within the C Programming forums, part of the General Programming Boards category; is there an algorithm for counting leafs and nonleaves in a binary tree, I could find somewhere?...

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    88

    counting leafs

    is there an algorithm for counting leafs and nonleaves in a binary tree, I could find somewhere?

  2. #2
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    is there an algorithm for counting leafs and nonleaves in a binary tree, I could find somewhere?
    Just do a depth first search on the tree returning the number of leaves and nonleaves.

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    how would I do that?

  4. #4
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    Well, before you can program it, you have to define it-- tie the idea down to something.

    Question: What makes a leaf?
    Question: What makes a non-leaf?

    In any given binary tree, you can only have two (2) types of nodes-- either a parent node, or a child (leaf) node. The difference between the two (2) is simple:

    parents have either a left-child, a right-child, or both. Leaf (child) nodes have no children hanging off of them.

    Use recursion to start at the root (first parent node) and walk the left children until there are not, then try a right child and start trying for more left children. Eventually it will traverse all children in the tree and return when it's back to the root node.

    Here's some pseudo-code:

    Code:
    /* Structures */
    typedef struct nodeStrucPtr                         /* makeup of a node */
       {
       struct nodeStrucPtr *leftChild;
       struct nodeStrucPtr *rightChild;
       }leafNodeRec,*leafNodePtr;
    
    /* Prototypes */
    int main(void);                                              /* entry/exit point */
    void treewalk(leafNodePtr);                         /* recursive part */
    
    /* Global variables */
    leafNodePtr  rootNodeP;                              /* root of b-tree */
    int                 leaf_counter = 0;                    /* counters */
    int                 nonleaf_counter = 0;
    
    
    /* Functions & Procedures */
    
    int main(void)
       {
       /* we assume the tree is already allocated  & populated */
       /* if not, do that here                                                       */
    
       treewalk(rootNodeP);                           /* go count nodes */
       
       return(0);
       }
    
    
    void treewalk(leafNodePtr leafP)
       {
       if(!leafP)                                                    /* pointer valid? */
          return;                                                   /* ... no, bail */
    
       if(leafP->leftChild)
          treewalk(leafP->leftChild);                     /* down left child */
       if(leafP->rightChild)
          treewalk(leafP->rightChild);                  /* down right child */
    
       if(leafP->leftChild || leafP->rightChild)     /* leaf or parent? */
          nonleaf_counter++;
       else
          leaf_counter++;
       }
    Rather than going out for effeciency, I used more code so it would be more understandable.
    It is not the spoon that bends, it is you who bends around the spoon.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Counting up(and down) using recursive function. Please help.
    By MarkSquall in forum C++ Programming
    Replies: 6
    Last Post: 06-06-2008, 04:26 AM
  2. How to implement reference counting with 'Smart_ptr'?
    By meili100 in forum C++ Programming
    Replies: 3
    Last Post: 06-10-2007, 05:28 AM
  3. Counting Numbers in Array, not counting last number!
    By metaljester in forum C++ Programming
    Replies: 11
    Last Post: 10-18-2006, 11:25 AM
  4. counting and output, with arrays and functions
    By Wraithan in forum C++ Programming
    Replies: 7
    Last Post: 12-04-2005, 11:46 PM
  5. Counting using Lib Cstring
    By niroopan in forum C++ Programming
    Replies: 4
    Last Post: 12-13-2002, 04:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21