首页 > 代码库 > SDUT 3344 数据结构实验之二叉树五:层序遍历
SDUT 3344 数据结构实验之二叉树五:层序遍历
数据结构实验之二叉树五:层序遍历
Time Limit: 1000MS Memory Limit: 65536KB
Submit Statistic
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
DQE:
先序序列建立二叉树后层序遍历,用到队列,可以使用数组简化代替,定义数组尺寸时注意假溢出即可,水题+1.
附代码:
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 struct Tree 7 { 8 char c; 9 Tree *lt,*rt; 10 }; 11 12 Tree *creat(char *&xx) 13 { 14 if(*xx==‘\0‘) 15 return NULL; 16 if(*xx==‘,‘) 17 { 18 xx++; 19 return NULL; 20 } 21 Tree *r=new Tree; 22 r->c=*xx++; 23 r->lt=creat(xx); 24 r->rt=creat(xx); 25 return r; 26 } 27 28 void cxvisit(Tree *r) 29 { 30 Tree *que[100]; 31 int i=0,j=0; 32 que[j++]=r; 33 while(i<j) 34 { 35 if(que[i]) 36 { 37 que[j++]=que[i]->lt; 38 que[j++]=que[i]->rt; 39 printf("%c",que[i]->c); 40 } 41 i++; 42 } 43 } 44 45 int main() 46 { 47 Tree *root; 48 int n; 49 scanf("%d",&n); 50 char xx[55],*p; 51 while(n--) 52 { 53 p=xx; 54 scanf("%s",xx); 55 root=creat(p); 56 cxvisit(root); 57 printf("\n"); 58 } 59 return 0; 60 } 61 62 /*************************************************** 63 User name: *** 64 Result: Accepted 65 Take time: 0ms 66 Take Memory: 156KB 67 Submit time: 2016-11-03 18:35:52 68 ****************************************************/
SDUT 3344 数据结构实验之二叉树五:层序遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。