计算二叉树中叶子节点数目

int leaf(bitree t)
{
  if(!t)       
   return 0;      //空树,无叶子 
  else if(!t->lch && !t->rch)
           return 1;
        else 
           return (leaf(t->lch) + leaf(t->rch));
}

算法分析:

首先要明白其本质还是二叉树的遍历.只不过是带额外有条件的输出.即找出叶子结点并

进行计数.

1. 提到计数的话,一开始的反应就是建立一个int型变量(如count),然后找到一个符合条件

的就进行count ++; 但在这里就不是那么合适了.因为若是要遍历,选择递归遍历,则每次

调用一次递归函数都会创建一个count,各个count都不相同.而且都会被初始化为0,这样就

没什么意义了.

2.所以采取的方法就是利用函数返回值.把函数定义为返回值为int型的函数.

3.然后进行判断:

if(!t->lch && !t->rch)如果左右结点都为NULL,则返回1(也就是计数+1).

否则就调用递归函数,先左子树,后右子树.这个算法真正精髓的一句就是:

return (leaf(t->lch) + leaf(t->rch));

在调用递归的同时把各个递归函数的返回值都加了起来.而最终返回到主函数的值

就是叶子节点的个数!