编写递归算法，计算二叉树中叶子结点的数目

1

#include<iostream>
using namespace std;

typedef struct TNode//二叉树结构
{
  char nodeValue;//结点的值
  TNode* left;//左子树 
  TNode* right;//右子树 
}*BiTree;
void CreateBiTree(BiTree &T)//先序遍历方式创建二叉树 ,输入.代表该结点为空 
{
  char nodeValue;
  cin>> nodeValue; 
  if(nodeValue!='.')//结点非空
  {
    T=new TNode;
    T->nodeValue=nodeValue;
    CreateBiTree(T->left); 
    CreateBiTree(T->right);                    
  }
  else T=NULL; 

}
int CountLeaf(BiTree T)
{
  static int LeafNum=0;//叶子初始数目为0，使用静态变量//静态局部变量，防止下一次被初始化
/*
1.static全局变量与普通的全局变量有什么区别： 
static全局变量只初使化一次，防止在其他文件单元中被引用。

2.static局部变量和普通局部变量有什么区别： 
static局部变量只被初始化一次，下一次依据上一次结果值。

3.static函数与普通函数有什么区别： 
static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝。
https://blog.csdn.net/u011617097/article/details/50100533
*/
  if(T)//树非空
  {
     if(T->left==NULL&&T->right==NULL)//为叶子结点
       LeafNum++;//叶子数目加1
    // else//不为叶子结点
   //  {
      CountLeaf(T->left);//递归统计左子树叶子数目
      CountLeaf(T->right);//递归统计右子树叶子数目
   //  }
   }
    return LeafNum;
}

int main()
{
    BiTree T;
    int leafNum;
    cout<<"请输入先序遍历的二叉树："<<endl;
    CreateBiTree(T); 
    leafNum=CountLeaf(T);
    cout<<"叶子结点数为："<<leafNum<<endl;
    return 0;
}

2

#include<stdio.h>
#include<malloc.h>
struct node{
	char info;
	struct node *llink,*rlink;
	};
typedef struct node NODE;//没必要
NODE *creat()//指针
{
	char x;
	NODE *p;
      scanf("%c",&x);
	//printf("%c",x);检验
	if(x!='.')
    {
		p=(NODE *)malloc(sizeof(NODE));//先序创建树
		p->info=x;
		p->llink=creat();
		p->rlink=creat();
	 }
	else
		p=NULL;
	return p;
}

int leafnum=0;//不能放置在函数里，要不然每次创建树都会初始化一次//全局变量在子函数和主函数里面有效，在子函数里运行，在主函数里输出
void run(NODE *t){
	if(t)
	{
	    if(t->llink==NULL&&t->rlink==NULL)
       		leafnum++;
		run(t->llink);
		run(t->rlink);	
	  }
}
main()
{
	NODE *T;

	printf("PLease input a tree:\n");
	T=creat();

	printf("\n");

	if(!T)
		printf("This is a empty binary tree.");
	else
	    { printf("the leaves number is:\n ");
		run(T);
		printf("%d",leafnum);//输出结果
		}
       
}

同2

#include<stdio.h>
#include<malloc.h>
struct node{
	char info;
	struct node *llink,*rlink;
	};
typedef struct node NODE;
NODE *creat(){
	char x;
	NODE *p;
      	scanf("%c",&x);
		printf("%c",x);
		if(x!='.'){
		p=(NODE *)malloc(sizeof(NODE));
		p->info=x;
		p->llink=creat();
		p->rlink=creat();
	 }
	else
		p=NULL;
	return p;
}
//2
int run(NODE *t){
	static int leafnum=0;//静态局部变量
	if(t)
	{
	    if(t->llink==NULL&&t->rlink==NULL)
       		leafnum++;
		run(t->llink);
		run(t->rlink);	
	  }
	return leafnum;//1
}
main()
{
	NODE *T;
	printf("PLease input a tree:\n");
	T=creat();
	printf("\n");
	if(!T)
		printf("This is a empty binary tree.");
	else
	    { printf("the leaves number is:%d\n ",run(T));//3
		
		//printf("%d",leafnum);
		}
       printf("\n");
}