Question

编写递归算法，计算二叉树中叶子结点的数目。(C++)急！！！

Answer 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，使用静态变量
if(T)//树非空
{
if(T->left==NULL&&T->right==NULL)//为叶子结点
LeafNum++;//叶子数目加1
else//不为叶子结点
{
CountLeaf(T->left);//递归统计左子树叶子数目
CountLeaf(T->right);//递归统计右子树叶子数目
}
}
return LeafNum;
}
//用来测试的main函数，
int main()
{
BiTree T;
int leafNum;
cout<<"请输入中序遍历的二叉树序列(#号代表该结点为空)：如(ABC##DE#G##F###)"<<endl;
CreateBiTree(T);
leafNum=CountLeaf(T);
cout<<"该二叉树中叶子结点数为："<<leafNum<<endl;
return 0;
}

Answer 2

Leaf_Num(BTnode *BT)
{
if(BT==NULL) return 0;
if(BT->left==NULL && BT->right==NULL) return 1;
else return Leaf_Num(BT->left)+Leaf_Num(BT->right);
}