数据结构实验之二叉树五：层序遍历

数据结构实验之二叉树五：层序遍历

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

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

Input

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

Output

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

Sample Input

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

Sample Output

abcdefg xnuli

Hint

 

Source

xam

这个题的要点在于如何进行层序的遍历，前面学过先序遍历，中序遍历和后序遍历，现如今的层序遍历就是将一颗二叉树从上到下从左到右依次输出一遍即可。本题的难点就在层序遍历的代码实现上。代码的实现可以从简单的顺序遍历考虑。也可以用栈和队列进行遍历。层序遍历中的顺序遍历，就是定义两个变量，让它们同时从1或者任意数开始遍历，遇到结点就输出，然后判断此结点下是否还有左右结点，如果有结点，那么就让数组里的变量加一，并且把值赋值到数组元素里面，这样就可以实现层序遍历。想不明白的在纸上画一画层序遍历的代码流程，看着很复杂的 代码在纸上模拟一遍或者直接在代码上进行调试就可以清楚的看到每一步的过程，从而很好的理解代码的含义。

AC代码：

#include<bits/stdc++.h> using namespace std; char a[1000]; int x; typedef struct node { int data; struct node*lchild,*rchild; }tree; struct node*creat()//建立二叉树函数 { struct node*root; char c; c=a[x++]; if(c==',') { return NULL; } else { root=new tree; root->data=c; root->lchild=creat(); root->rchild=creat(); } return root; } void levelorder(struct node*root)//层序遍历函数 { struct node*b[88];//建立一个结构体数组 int front,base;//定义两个变量 front=base=0;//初始化变量 struct node*t1;//定义一个结构体结点（二叉树之外的结点） if(root)//root！=NULL的时候让数组元素等于结点 { b[++base]=root; } while(front!=base)//防止越界 { t1=b[++front];//循环里面每一个结点都等于t1，然后输出 printf("%c",t1->data); if(t1->lchild!=NULL)//如果有左孩子或者又孩子就遍历变量 { b[++base]=t1->lchild; } if(t1->rchild!=NULL) { b[++base]=t1->rchild; } } } int main()//主函数 { int t; struct node*root; scanf("%d",&t); while(t--) { x=0; memset(a,0,sizeof(a)); scanf("%s",a); root=creat(); levelorder(root); printf("\n"); } return 0; }