【说明】
设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’);
参考答案：(1)(NODE*)malloc(sizeof(NODE))
(2)makeTree()
(3)*str
(4)putchar(t-＞val)
(5)walkTree(t-＞subTree[i])
解析：
[分析]：
本题考查在C语言中实现用列表表示M叉树。
题目要求程序根据输入的列表生成一棵M叉树，并由M叉树再输出列表。题目中给出了列表与树的对应关系，从这种对应关系中我们可以看出，每个结点后紧跟的那层括号下结点的个数就是这个根结点的孩子个数，用列表表示得到的序列有点像树的先序遍历，因此，根据列表来生成M叉树时，应该是首先生成左子树，然后才依次往右的生成过程。下面来具体
[分析]：代码。
第(1)空很明显是给变量s赋一个初值，从程序中可以知道，变量s是一个指向NODE型结点的指针变量，但程序中并没有给出这样的结点，那么此空应该是动态创建一个这样的结点。在C语言中，动态分配空间要用函数malloc()，因此，此空答案为(NODE*)malloc(sizeof(NODE))。
第(2)空在循环体中，从程序中不难推断出此循环体的作用是由列表生成M叉树，此空是给s-＞subTree[k]这个指针数组赋值，这个数组中存放的是当前结点的孩子结点的指针，在树的生成过程中是根据列表来递归生成其对应的三叉树的，此空应该是递归调用生成结点的函数makeTree()。因此，此空答案为makeTree()。
第(3)空是循环结束的判断条件，而这个循环的作用是根据列表来生成三叉树，只有列表的所有元素都被考虑了循环才结束。从程序中可以知道列表的元素存放在数组中，指针变量s廿指向这个数组，且在程序中对列表的操作都是通过指针变量str来实现的，因此，此空答案为*str。
第(4)空在条件判断语句下面，此条件判断语句结果为真，说明当前取到的是结点，接下来应该把该结点的值写入列表中，从后面的程序我们很容易知道实现此功能的函数，因此，此空答案为putchar(t-＞val)。
第(5)空在一个循环体下面，根据循环的条件，可以推断出这是对一个结点的所有孩子结点进行循环搜索。由M叉树生成列表可以说是由列表生成M叉树的逆过程，需要对树中的每个结点进行检索来生成列表，这里也要用到递归调用，而这个函数的当前检索的结点指针为t-＞subTree[i]。因此，此空答案为walkTree(t-＞subTree[i])。