is there an algorithm for counting leafs and nonleaves in a binary tree, I could find somewhere?
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?...
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.is there an algorithm for counting leafs and nonleaves in a binary tree, I could find somewhere?
how would I do that?
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:
Rather than going out for effeciency, I used more code so it would be more understandable.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++; }
It is not the spoon that bends, it is you who bends around the spoon.