【说明】
设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值后跟用“()”括起来的各子树的列表(若有子树的话)，各子树的列表间用“，”分隔。例如，如下图所示的三叉树可用列表a(b(c,d),e,f(g,h,i))表示。
本程序根据输入的列表生成一棵M叉树，并由M叉树再输出列表。
【函数】
#include
#include
#define M 3 /*三叉树*/
typedef struct node{
int val;
struct node *subTree[M];
}NODE;
char buf[255], *str=buf;
NODE *d=NULL;
NODE *makeTree() /*由列表生成M叉树*/
{
int k; NODE *s;
s= (1) ;
s-＞val=*str++;
for(k=0;k＜M;k++)
s-＞subTree[k]=NULL;
if(*str==’(’)
{
k=0;
do{
str++;
s-＞subTree[k]= (2) ;
if(*str==’)’)
{
str++;
break;
}
k=k+1;
}while( (3) );
}
return s;
}
void walkTree(NODE *t) /*由M叉树输出列表*/
{
int i;
if(t !=NULL)
{
(4) ;
if(t-＞subTree[0]==NULL)
return;
putchar(’(’);
for(i=0;i＜M;i++)
{
(5) ;
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’);
}
