已知二叉樹的一個按先序遍歷輸入的字符序列，如abc,,de,g,,f,,, (其中,表示空結(jié)點(diǎn))。請建立二叉樹并求二叉樹的葉子結(jié)點(diǎn)個數(shù)。 Input
連續(xù)輸入多組數(shù)據(jù)，每組數(shù)據(jù)輸入一個長度小于50個字符的字符串。 Output
輸出二叉樹的葉子結(jié)點(diǎn)個數(shù)。 Example Input
abc,,de,g,,f,,, Example Output
3 Hint
Author
xam
#include<stdio.h>#include<stdlib.h>#include<string.h>char a[55];int top;struct node{ int data; struct node *l, *r;};struct node *creat()//重建二叉樹{ struct node *root; top++; if(a[top] == ',') root = NULL; else { root = (struct node *) malloc (sizeof(struct node)); root -> data = a[top]; root -> l = creat(); root -> r = creat(); } return root;};int yezi(struct node *root){ if(root == NULL) return 0; if(root -> l == NULL && root -> r == NULL) return 1; else return yezi(root -> l) + yezi(root -> r);//遞歸把左子樹的葉子數(shù)跟右子樹的葉子數(shù)加起來}int main(){ while(scanf("%s", a) != EOF) { top = -1; struct node *root; root = creat(); printf("%d/n", yezi(root)); } return 0;}新聞熱點(diǎn)
疑難解答
