数据结构实验之二叉树七:叶子问题

2/22/2017来源:ASP.NET技巧人气:1651

PRoblem Description

已知一个按先序输入的字符序列,如abd,,eg,,,cf,,,(其中,表示空结点)。请建立该二叉树并按从上到下从左到右的顺序输出该二叉树的所有叶子结点。 Input

输入数据有多行,每一行是一个长度小于50个字符的字符串。 Output

按从上到下从左到右的顺序输出二叉树的叶子结点。 Example Input

abd,,eg,,,cf,,, xnl,,i,,u,, Example Output

dfg uli Hint

Author

xam

这个题就是用层序遍历的方法到达最后一层输出

#include<stdio.h> #include<string.h> #include<stdlib.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; }; void yezi(struct node *root) { int in = 0, out = 0; struct node *p[100]; p[in++] = root; while(in > out) { if(p[out]) { if(p[out] -> l == NULL && p[out] -> r == NULL)//判断是不是叶子 printf("%c", p[out] -> data); p[in++] = p[out] -> l; p[in++] = p[out] -> r; } out++; } } int main() { while(scanf("%s", a) != EOF) { top = -1; struct node *root; root = creat(); yezi(root); printf("\n"); } return 0; }