从下至上按层遍历由广义表(节点为数字)构造的二叉树

时间:2022-09-17 19:08:07

【问题描述】
 给定一颗二叉树,要求从下至上按层遍历二叉树,每层的访问顺序是从左到右,每一层单独输出一行。

【输入形式】
 广义表表示的二叉树,结点元素类型为整型,且都大于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.按层次遍历二叉树的算法

/*
由于是倒着从最后一层开始从左至右按层遍历
所以面临以下问题:
1.如何根据广义表构造树(注意节点不是字母,而是数字(可能是多位数)!!!!!)
2.如何从最后一层依次向上面的层遍历
3.如何输出一层之后换行再输出另一行

针对问题2,只要在按层遍历的时候从右至左遍历,最后输出到数组里,再将数组逆序输出就好
针对问题3,就是设置一个东西来记录节点的层数。这里用到了二维数组,int a[][2],
其中a[][0]用来记录节点的数字,a[][1]用来记录层数
针对问题1,解决办法是先用gets将广义表读入字符串s[],然后依次从开头往后读,
发现‘0’~‘9’之间的字符,就放到字符数组num[]中,直到不再是‘0’~‘9’之间的字符,
然后将num[]转换成数字(可以用sscanf)
*/
#include<stdio.h>
#include<stdlib.h>// malloc()
#include<string.h>// strlen(), memset()

#define MAXSIZE 100

typedef struct node
{
int data;
int depth;//记录深度,同一深度输出到同一行
struct node *lchild, *rchild;
}BTNode, *BTREE;

int a[MAXSIZE][2];//二维数组,分别记录节点值和深度

BTREE create_BT();
int layer(BTREE T);

int main()
{
BTREE T;
int i = 0, dep;

T = create_BT();//根据广义表构建树
i = layer(T);//按层遍历,从右至左

dep = a[i][1];
for(; i>=0; i--)//遍历所有的节点以输出
{
if(dep!=a[i][1])//如果发现深度跟之前的不同,就换行
{
printf("\n");
dep = a[i][1];
}
printf("%d ", a[i][0]);
}
return 0;
}

BTREE create_BT()
{
BTREE stack[MAXSIZE], p, T = NULL;
char ch, s[MAXSIZE] = {0}, num[10] = {0};
int flag, top = -1, len, i = 0, j = 0, sum = 0;

fgets(s, MAXSIZE-1, stdin);//先读到数组中,这样做,数据就可以重复读了!
len = strlen(s);

while(1)
{
memset(num, '\0', 10);//每次别忘了对num清零!
ch = s[i];

if(s[i] >= '0' && s[i] <= '9') //发现一个字符是'0'~'9',可能是多位数
{
j = 0;
while(s[i] >= '0' && s[i] <= '9')
{
num[j++] = s[i++];
}
sscanf(num, "%d", &sum); //sscanf字符串转数字
}
else
i++;//如果不是数字,要i++,下次就可以读下一个字符

if( ch == '\n' || i >= len) //发现'\n'或者是s[]到头了就返回
return T;
else
{
switch(ch)
{
case '(' : stack[++top] = p;
flag = 1;
break;
case ')' : top--;
break;
case ',' : flag = 2;
break;
default : p = (BTREE)malloc(sizeof(BTNode));
p -> data = sum;
p -> depth = 0xfffffff;
p -> lchild = NULL;
p -> rchild = NULL;
if(T == NULL)
{
T = p;
p -> depth = 1;//记录深度
}
else if(flag == 1)
{
stack[top] -> lchild = p;
p -> depth = top+2;//记录深度
}
else
{
stack[top] -> rchild = p;
p -> depth = top+2;//记录深度
}
}
}
}
}

int layer(BTREE T)
{
BTREE queue[MAXSIZE], p;
int front, rear, i = 0;
if(T != NULL)
{
queue[0] = T;
front = -1;
rear = 0;
while(front < rear)
{
p = queue[++front];
a[i][0] = p -> data;
a[i++][1] = p -> depth;//将遍历的节点记录到a[][]
if(p->rchild != NULL)//先右,便是从右至左遍历
queue[++rear] = p -> rchild;
if(p->lchild != NULL)
queue[++rear] = p -> lchild;
}
}

return --i;//返回节点个数!别忘了是--i
}