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

2/10/2017来源:ASP.NET技巧人气:247

sdut原题链接

数据结构实验之二叉树三:统计叶子数 Time Limit: 1000MS Memory Limit: 65536KB

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

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

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

Example Input abc,,de,g,,f,,,

Example Output 3

Hint

Author xam

以下为accepted代码

#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct node { char date; struct node *left; struct node *right; }BinTree; char s[104]; int flag, y1; BinTree *root; BinTree * creat()//建树 { BinTree * root; if(s[flag++] == ','){ root = NULL; } else { root = (BinTree *)malloc(sizeof(BinTree)); root->date = s[flag-1]; root->left = creat(); root->right = creat(); } return root; } void leave(BinTree *root)//计算叶子数目 { if(root)///判断root是否为NULL { if(root->left == NULL && root->right == NULL) { y1++; } leave(root->left); leave(root->right); } } int main() { while(scanf("%s", s) != EOF) { flag = y1 = 0; root = creat();//调用建树函数 leave(root);//调用计算叶子数目函数 printf("%d\n", y1); } return 0; } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 112KB Submit time: 2017-02-07 11:46:51 ****************************************************/

以下为runtime error代码

#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct node { char date; struct node *left; struct node *right; }BinTree; char s[54]; int flag, y1; BinTree *root; BinTree * creat()//建树 { BinTree * root; if(s[flag++] == ','){ root = NULL; } else { root = (BinTree *)malloc(sizeof(BinTree)); root->date = s[flag-1]; root->left = creat(); root->right = creat(); } return root; } void leave(BinTree *root)//计算叶子数目 { if(!root->left && !root->right){ y1++; } } int main() { while(scanf("%s", s) != EOF) { flag = y1 = 0; root = creat();//调用建树函数 leave(root);//调用计算叶子数目函数 printf("%d\n", y1); } return 0; } /*************************************************** User name: LEO Result: Runtime Error Take time: 0ms Take Memory: 0KB Submit time: 2017-02-07 11:31:15 ****************************************************/

runtime error cause: 1 在计算叶子数目函数中没有判断root是否为NULL;