数据结构实验之二叉树五：层序遍历*(层序遍历要学好

2019-11-08 20:04:20

字体：大中小

来源：转载

供稿：网友

数据结构实验之二叉树五：层序遍历 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 Hint

#include <stdio.h>#include <string.h>int i;typedef struct node{ char data; struct node *l,*r;}node;node *create(char *str)//老样子，先序植树{ node *root; if(str[i]==','){ i++; root = NULL; } else{ root = (node *)malloc(sizeof(struct node)); root->data = str[i++]; root->l = create(str); root->r = create(str); } return root;}void *level_tra(node *root)//这里层序遍历就有门道了{ node *temp[100];//用temp结点数组来临时存储根 int in = 0,out = 0; temp[in++] = root;//temp[0]存根 while(in>out){ if(temp[out]){ printf("%c",temp[out]->data);//输出根的时候，把这个跟的左节点和右节点先存一下，这样就达到层序遍历的目的啦 temp[in++] = temp[out]->l; temp[in++] = temp[out]->r; } out++; }}int main(){ int t; char str[100]; node *root; while(~scanf("%d",&t)){ while(t--){ i = 0; scanf("%s",str); root = create(str); level_tra(root); printf("/n"); } } return 0;}

上一篇：文章标题

下一篇：确认运行的jdk版本