题目描述：
以二叉链表作为二叉树的存储结构，求二叉树的叶子结点个数。
输入格式:
输入二叉树的先序序列。
提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。
输出格式:
输出有两行：
第一行是二叉树的中序遍历序列；
第二行是二叉树的叶子结点个数。

输入样例:

ABC##DE#G##F###

输出样例:

CBEGDFA
3

1. 二叉树的链式存储结构：

typedef struct Node
{
    DataType data;
    struct Node *LChild;
    struct Node *RChild;
} BiTNode, *BiTree;/* *BiTree为指向根节点的指针 */

具有n个结点的二叉链表中，空链域的个数为n+1（2*n个域指向n-1个结点）

2. 先序遍历建立二叉树：

void CreatBinTree(BiTree *bt)/*先序遍历建立二叉树*/
{
    char ch;
    ch = getchar();/*读入每一个字符*/
    if(ch=='#')
        *bt=NULL;
    else
    {
        *bt=(BiTree)malloc(sizeof(BiTNode)); //开辟一个新结点
        (*bt)->data=ch;
        CreatBinTree(&((*bt)->LChild)); //生成左子树
        CreatBinTree(&((*bt)->RChild)); //生成右子树
    }
}

3. 统计叶子结点的数目

void leaf_a(BiTree root)/* LeafCount保存叶子结点的数目的全局变量,调用之前初始化值为0 */
{
    if(root!=NULL)
    {
        leaf_a(root->LChild);
        leaf_a(root->RChild);
        if (root ->LChild==NULL && root ->RChild==NULL)
            LeafCount++;
    }
}

int leaf_b(BiTree root)
{
    int LeafCount2;
    if(root==NULL)
        LeafCount2 =0;
    else if((root->LChild==NULL)&&(root->RChild==NULL))/*只有一个结点*/
        LeafCount2 =1;
    else
        LeafCount2 =leaf_b(root->LChild)+leaf_b(root->RChild);
    /* 叶子数为左右子树的叶子数目之和 */
    return LeafCount2;
}

完整代码：

#include <stdio.h>
#include <stdlib.h>
typedef char DataType;
typedef struct Node
{
    DataType data;
    struct Node *LChild;
    struct Node *RChild;
} BiTNode, *BiTree;
void CreatBinTree(BiTree *bt)/*先序遍历建立二叉树*/
{
    char ch;
    ch = getchar();
    if(ch=='#')
        *bt=NULL;
    else
    {
        *bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
        (*bt)->data=ch;
        CreatBinTree(&((*bt)->LChild)); //生成左子树
        CreatBinTree(&((*bt)->RChild)); //生成右子树
    }
}
int leaf_b(BiTree root)/*分而治之*/
{
    int LeafCount;
    if(root==NULL)
        LeafCount=0;
    else if((root->LChild==NULL)&&(root->RChild==NULL))
        LeafCount=1;
    else
        LeafCount=leaf_b(root->LChild)+leaf_b(root->RChild);
    return LeafCount;
}
void InOrder(BiTree root)
{
    if(root!=NULL)
    {
        InOrder(root->LChild);
        printf("%c",root->data);
        InOrder(root->RChild);
    }
}
int main()
{
    BiTree BT;
    CreatBinTree(&BT);
    InOrder(BT);
    printf("\n");
    printf("%d\n",leaf_b(BT));
    return 0;
}