数据结构实验之二叉树七:叶子问题(二叉树+队列)

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

sdut原题链接

数据结构实验之二叉树七:叶子问题 Time Limit: 1000MS Memory Limit: 65536KB

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

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

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

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

Example Output dfg uli

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; BinTree *root; BinTree *link[54]; char s[54]; int flag, pu, po; 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 put_leave(BinTree *root) { if(root) { pu = po = 0; link[pu++] = root; while(pu > po) { if(!link[po]->left && !link[po]->right) { printf("%c", link[po]->date); } if(link[po]->left) { link[pu++] = link[po]->left; } if(link[po]->right) { link[pu++] = link[po]->right; } po++; } } } int main() { while(scanf("%s", s) != EOF) { flag = 0; root = creat(); put_leave(root); printf("\n"); } return 0; } /*************************************************** User name: Result: Accepted Take time: 0ms Take Memory: 116KB Submit time: 2017-02-07 16:09:24 ****************************************************/