在本实验中，程序的输入是一个表示树结构的广义表。假设树的根为 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
测试输入
(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 源代码
#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXSIZE 200 void PrintfTree(char str[]){ int i=1,j; int Lcount=0; for(i=1;i<strlen(str);i++){ if(str[i]=='(') Lcount++; if((str[i]==')')&&(Lcount!=0)) Lcount--; if('a'<=str[i]&&str[i]<='z') { for(j=1;j<=Lcount;j++) printf(" "); printf("%c\n",str[i]); } } } void PrintfDgree(int a[],int m,int n){ int i=0,j,k; int count[n]; for(k=0;k<=n;k++) count[k]=0; for(i=0;i<m;i++){ j=a[i]; count[j]++; } printf("Degree of tree: %d\n",n); for(k=0;k<=n;k++) printf("Number of nodes of degree %d: %d\n",k,count[k]); } void Calculate(char str[]){ int num[MAXSIZE]; int i=0,j,flag=0; int k=0,Lcount=0; num[0]=0; int max=0; while(i<strlen(str)){ for(;i<strlen(str);i++) if(str[i]=='(') { flag=i; Lcount=1; i++; break; } for(j=flag+1;j<strlen(str);j++){ if(str[j]=='(') Lcount++; if(Lcount==0) break; else if(str[j]==')') Lcount--; else if(str[j]==','&&Lcount==1) num[k]++; } if(num[k]>max) max=num[k]; k++; num[k]=0; } PrintfDgree(num,k-1,max); } int main(){ char str[MAXSIZE]; gets(str); if(!strcmp(str,"()")){ printf("Degree of tree: 0\n"); printf("Number of nodes of degree 0: 0\n"); } else{ PrintfTree(str); Calculate(str); } return 0; }
