每日编程中遇到任何疑问、意见、建议请公众号留言或加入每日编程群聊739635399
已知一棵树以存储以上形式，请编写函数GetLeavesCount，计算叶子结点数目。
GetLeavesCount的函数原型为：int GetLeavesCount（PTree T）
其中，形参T中保存了树中的结点数目以及图b所示的结点数组，函数返回叶子结点的数目。
比如：对图b的树调用函数GetLeavesCount（T），返回结果为6
输入的第一个数n表示树中的结点数，此后有n行输入，每行表示一个节点的信息，第一个信息为结点的数据，第二个信息为结点的双亲结点在数组中的位置。
如输入：
10
a -1
b 0
c 0
d 0
e 1
f 1
g 1
h 2
i 3
则创建图b所对应的树。
对此树调用函数GetLeavesCount（T）,返回结果为6
如输入：
8
a -1
b 0
e 1
h 2
c 0
d 0
f 5
g 5
对此树调用函数GetLeavesCount（T）,返回结果为4
输入格式：
结点个数
结点信息
输出格式：
叶子结点的个数输入样例：
10
a -1
b 0
c 0
d 0
e 1
f 1
g 1
h 2
i 3
h 3
输出样例：
6
（1）代码实现：
#include <iostream>
using namespace std;
#define MAX_TREE_SIZE 100
typedef struct
{
char data; //结点数据域
int parent; //结点双亲在数组中的位置
} PTNode;
typedef struct
{
PTNode nodes[MAX_TREE_SIZE]; //存储树中所有的结点
int n; //树中的结点数，n不超过100
} PTree;
/*
算法思想：遍历结点数组，当该结点的序号有另外一个节点指向时，那么该结点为非叶节点，当遍历完结点时，没有一个结点的指针指向该序号的话，那么该结点即是叶结点。
*/
//返回树中叶结点的个数
int GetLeavesCount(PTree T)
{
int count = 0; //统计非叶结点的个数，转换一下思考方式，否则很难直接统计叶结点个数
for (int i = 0; i < T.n; i++)
for (int j = 0; j < T.n; j++)
{
if (i == j) //自己指向自己不算
continue;
else if (T.nodes[j].parent == i)
{
count++;
break;
}
}
return T.n - count;
}
int main()
{
cout << "请输入树的结点的个数";
int n = 0;
cin >> n;
PTree pt;
pt.n = n;
cout << "请输入每个结点的信息：" << endl;
for (int i = 0; i < n; i++)
{ //输入结点的数据域和结点双亲在数组中的位置
cin >> pt.nodes[i].data;
cin >> pt.nodes[i].parent;
}
int leaves = GetLeavesCount(pt);
cout << leaves << endl;
system("pause");
return 0;
}
输入格式：
数组元素的个数
数组
区间
输出格式：
给定区间数值之和
输入样例：
5
1 2 3 4 5
1 3
输出样例：
9
