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

时间：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
}


标签：

相关文章