数据结构实验之二叉树七：叶子问题
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
已知一个按先序输入的字符序列，如abd,,eg,,,cf,,,(其中,表示空结点)。请建立该二叉树并按从上到下从左到右的顺序输出该二叉树的所有叶子结点。
Input
输入数据有多行，每一行是一个长度小于50个字符的字符串。
Output
按从上到下从左到右的顺序输出二叉树的叶子结点。
Sample Input
abd,,eg,,,cf,,,
xnl,,i,,u,,
Sample Output
dfg
uli
Hint
Source
xam
#include <stdio.h> #include <stdlib.h> #include <string.h> char a[101]; int l; struct node//二叉树的定义 { char data; struct node *lc; struct node *rc; }; struct node *creat() { struct node *root; char c; c = a[l++]; if(c == ',') { return NULL; } else { root = (struct node *)malloc(sizeof(struct node)); root->data = c; root->lc = creat(); root->rc = creat(); } return root; } void cengci(struct node *root) { int out = 0, in = 0; struct node *q[100]; q[in++] = root; while(in > out) { if(q[out] != 0) { if(q[out]->lc == NULL && q[out]->rc == NULL) printf("%c", q[out]->data); q[in++] = q[out]->lc; q[in++] = q[out]->rc; } out++; } } int main() { struct node *root; int i, j, m, n, k, t; while(scanf("%s", a) != EOF) { root = (struct node *)malloc(sizeof(struct node)); l = 0; root = creat(); cengci(root); printf("\n"); } return 0; }
