Problem Description
在本实验中,程序的输入是一个表示树结构的广义表。假设树的根为 root ,其子树森林 F = ( T1 , T2 , ... , Tn ),设与该树对应的广义表为 L ,则 L =(原子,子表 1 ,子表 2 , ... ,子表 n ),其中原子对应 root ,子表 i ( 1<i<=n )对应 Ti 。例如:广义表 (a,(b,(c),(d)),(f,(g),(h ),(i))) 表示的树如图所示:
程序的输出为树的层次结构、树的度以及各种度的结点个数。
在输出树的层次结构时,先输出根结点,然后依次输出各个子树,每个子树向里缩进 4 个空格,如:针对上图表示的树,输出的内容应为:
a
b
c
d
f
g
h
i
Degree of tree: 3
Number of nodes of degree 0: 5
Number of nodes of degree 1: 0
Number of nodes of degree 2: 2
Number of nodes of degree 3: 1
**例: **(下面的黑体为输入)
(a,(b),(c,(d),(e,(g),(h )),(f)))
a
b
c
d
e
g
h
f
Degree of tree: 3
Number of nodes of degree 0: 5
Number of nodes of degree 1: 0
Number of nodes of degree 2: 2
Number of nodes of degree 3: 1
AcCode
//
// main.cpp
// 树的建立与基本操作
//
// Created by jetviper on 2017/3/26.
// Copyright © 2017年 jetviper. All rights reserved.
//
#include <stdio.h>
#include<string.h>
int main() {
char str[1000],strtab[5]=" ";
int degree = 0 ,deep = -1,tddgree[100]={0},res[100]={0};
scanf("%s",&str);
int len = strlen(str);
int lastleft = 0;
for(int i =0;i<len;i++){
if(str[i]==',')continue;
else if(str[i]=='('){
lastleft = 1;
continue;
}
else if(str[i]==')'){
if(deep>-1){
if(lastleft == 0)res[tddgree[deep]]++;
if(tddgree[deep]>degree)degree = tddgree[deep];
tddgree[deep]=0;
deep--;
}
else {
break;
}
continue;
}
else {
if(lastleft == 1){
if(deep!= -1)tddgree[deep]++;
deep++;
lastleft = 0;
}
for(int j=0;j<deep;j++){
printf("%s",strtab);
}
printf("%c\n",str[i]);
}
}
printf("Degree of tree: %d\n",degree);
for(int i=0;i<=degree;i++){
printf("Number of nodes of degree %d: %d\n",i,res[i]);
}
return 0;
}