[程序说明]
对于刚进支付宝的新人,公司会给每位新人指导一位师傅。师傅要求是支付宝公司内的“又红又专”的那些人。为了保证师傅带徒弟的质量,公司规定每位师傅最多只能带M位徒弟。随着公司业务的不断发展,员工数量每年都井喷式的增长,公司的师傅也越来越多,而今天的徒弟如果表现出色,也会变成未来的师傅。公司HR希望能够有一张树形结构图能够清晰地描述这些师傅和徒弟的关系。这个任务交给了技术部的小周GG,聪明的小周很快意识到这其实就是一颗M叉树。
假定HR只能提供用列表法表示的数据:即每棵子树对应一个列表,列表的结构为:子树根结点的值部分(设为一个字符)和用“()”括起来的各子树的列表(如有子树的话),各子列表间用“,”,分隔。例如下面的三叉树可用列表a(b(c,d),e,f(g,h,i))表示。
下面的程序是小周GG在10分钟里写出的,该程序输入列表,生成一棵M叉树,并由M叉树输出列表。
# include<stdio.h> # include<stdlib.h> #define M3 typedef struct node{ char val; struct node *subTree[M]; }NODE; char buf[255],*str=buf; NODE *d=NULL; NODE *mackTree()/*由列表生成M叉树*/ { int k; NODE*s; s=(NODE*)malloc(sizeof(NODE)); s->val=*str++; for(k=0;k<M;k++) s->subTree[k]=NULL; if(*str=='('){ k=0; do{ str++; s->subTree[k]=(______) if(*str == ')') { str++; break; } k=k+1; }while(_______); } return s; } void walkTree(NODE *t)/*由M叉树输出列表*/ { int i; if(t!=NULL){ (________) if(t->subTree[0]==NULL) return; putchar('0'); for(i=0;i<M;i++) { (________) if((i!=M-1)&&(t->subTree[i+1]!=NULL)) putchar(’,’); } putchar(')'); } } void main( ) { printf("Enter exp: "); scanf("%S",str); d=makeTree(); walkTree(d); putchar('\n'); }