数据结构实验之二叉树五:层序遍历(二叉树+队列)

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

sdut原题链接

数据结构实验之二叉树五:层序遍历 Time Limit: 1000MS Memory Limit: 65536KB

PRoblem Description 已知一个按先序输入的字符序列,如abd,,eg,,,cf,,,(其中,表示空结点)。请建立二叉树并求二叉树的层次遍历序列。

Input 输入数据有多行,第一行是一个整数t (t<1000),代表有t行测试数据。每行是一个长度小于50个字符的字符串。

Output 输出二叉树的层次遍历序列。

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

Example Output abcdefg xnuli

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, *link[54]; char s[54]; int flag; 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 ans(BinTree *root)//二叉树的层序遍历函数 { if(root) { int i = 0, j = 0; link[j++] = root; while(i < j) { if(link[i]) { link[j++] = link[i]->left; link[j++] = link[i]->right; printf("%c", link[i]->date); } i++; } } } int main() { int T; scanf("%d", &T); while(T--) { flag = 0; scanf("%s", s); root = creat();//调用建立二叉树函数 ans(root);//调用二叉树的层序遍历函数 printf("\n"); } return 0; } /*************************************************** User name: jk160630 Result: Accepted Take time: 0ms Take Memory: 120KB Submit time: 2017-02-07 21:36:35 ****************************************************/