题目来源：北航14级6系数据结构作业
问题描述】
给定一颗二叉树，要求从下至上按层遍历二叉树，每层的访问顺序是从左到右，每一层单独输出一行。
【输入形式】
广义表表示的二叉树，结点元素类型为整型，且都大于0，例如：1( 2( 3 ( 4, 5 ) ), 6( 7, 8( 9, 10 ) ) )
【输出形式】
从下至上，打印每一层的结点元素值，元素间以空格隔开。每层的访问顺序是从左到右，每一层单独输出一行。
【样例输入】
1(2(3(4,5)),6(7,8(9,10)))，字符串内没有空格
【样例输出】
4 5 9 10
3 7 8
2 6
1
【样例说明】
【评分标准】
本题目主要考察两个知识点：
1.创建二叉树存储结构
2.按层次遍历二叉树的算法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXNUM 50
typedef struct BTNode {
int data;
struct BTnode *lchild, *rchild;
} BTNode, *BTree;
struct depthTree {
BTree bt;
int depth;
};
int main() {
int element[MAXNUM] = {0};
int eNum = 0;
int i = 0, j,k;
int temp = 0;
char inputElement[MAXNUM*2] = {0};
BTree stack0[MAXNUM];
BTree t, t1, BTroot=NULL;
int top0 = -1;
struct depthTree queue[MAXNUM];
int a[MAXNUM/2][10];
int len[MAXNUM/2] = {0}, lenNum;
struct depthTree p;
int front = -1;
int rear = 0;
gets(inputElement);
//输入数据
while( inputElement[i] != '\0') {
if( inputElement[i] == '(') {
temp = 0;
element[eNum++] = -1;
}
else if ( inputElement[i] == ')') {
temp = 0;
element[eNum++] = -2;
}
else if ( inputElement[i] == ',') {
temp = 0;
element[eNum++] = -3;
}
else if ( inputElement[i] >= '0' && inputElement[i] <= '9') {
for(j=i;inputElement[j] >= '0' && inputElement[j] <= '9';j++)
temp = temp*10 + (inputElement[j] - '0');
element[eNum++] = temp;
i = j-1;
}
i++;
}
//建立二叉树
for( i = 0; i < eNum; i++) {
switch(element[i]) {
case -1: {
stack0[++top0] = t;
k = 1;
break;
}
case -2: {
top0--;
break;
}
case -3: {
k = 2;
break;
}
default: {
t = (BTree)malloc(sizeof(BTNode));
t->data = element[i];
t->lchild = NULL;
t->rchild = NULL;
if( BTroot == NULL )
BTroot = t;
else {
switch(k) {
case 1: stack0[top0]->lchild = t;
break;
case 2: stack0[top0]->rchild = t;
break;
}
}
}
}
}
queue[0].bt = BTroot;
queue[0].depth = 0;
while( front < rear ) {
p = queue[++front];
temp = len[p.depth]++;
a[p.depth][temp] = p.bt->data;
lenNum = p.depth;
if( p.bt->lchild != NULL ) {
queue[++rear].bt = p.bt->lchild;
queue[rear].depth = p.depth + 1;
}
if( p.bt->rchild != NULL ) {
queue[++rear].bt = p.bt->rchild;
queue[rear].depth = p.depth + 1;
}
}
for(i = lenNum; i >= 0; i--) {
for( j = 0; j < len[i]; j++)
printf("%d ", a[i][j]);
printf("\n");
}
destoryBTree( BTroot );
BTroot = NULL;
}
//二叉树的销毁
void destoryBTree ( BTree t ) {
if( t != NULL ) {
destoryBTree(t->lchild);
destoryBTree(t->rchild);
free(t);
}
}