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.
