数据结构实验之二叉树三：统计叶子数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并求二叉树的叶子结点个数。

Input

连续输入多组数据，每组数据输入一个长度小于50个字符的字符串。

Output

输出二叉树的叶子结点个数。

Sample Input

abc,,de,g,,f,,,

Sample Output

3

Hint

 

Source

xam

这个题跟上一个树的遍历相差不大，就是在遍历的时候记录一下叶子结点的个数即可，如果树的建立和遍历不熟练的同学可以参考我的上一篇博客，写的比较详细希望能帮到。

链接：二叉树的建立与遍历

具体见代码注释。

AC代码：

#include<bits/stdc++.h>
using namespace std;
char a[100];
int x,y;//这个y是用来记录最后输出的结果的，因为定义了遍历函数，所以要在宏观上进行定义
//但是y在while循环中要记得定义上y=0，以防多次输入数据的累加而造成输出错误 
typedef struct node
{
	int data;
	struct node*lchild,*rchild;
}tree;
struct node*creat(tree*root)//建立树的函数 
{
	char c;
	c=a[x++];
	if(c==',')
	{
		root=NULL;
	}
	else
	{
		root=new tree;
		root->data=c;
		root->lchild=creat(root->lchild);
		root->rchild=creat(root->rchild);
	}
	return root;//记得返回树的根节点 
}
void  bianli(struct node*root)//遍历函数 
{
	if(root)
	{
		if(root->lchild==NULL&&root->rchild==NULL)//如果在一个结点的左右孩子都是空，那么y+1 
		{
			y++;
		}
		bianli(root->lchild);
		bianli(root->rchild);
	}
}
int main()
{
	struct node*root;
	while(~scanf("%s",a))
	{
		x=0;
		y=0;
		root=new tree;
		root=creat(root);
		bianli(root);
		printf("%d\n",y);
	}
	return 0;
}