【程序5说明】
设M叉树采用列表法表示，即每棵子树对应一个列表，列表的结构为：子树根结点的值部分(设为一个字符)和用“()”括起来的各子树的列表(如有子树的话)，各子列表间用“，”分隔。例如下面的三叉树可用列表a(b(c，d)，e，f(g，h，i))表示。
本程序输入列表，生成一棵M叉树，并由M叉树输出列表。假定输入无错误。
【程序5】
#include＜Stdio.h＞
#include＜Stdlib.h＞
#define M 3
typedef struct nodechar 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；
dostr++；
s-＞sub Tree[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])
解析： (1)该句分配一块内存，大小为sizeof(NODE)，并使定义的 NODE型指针S指向这块内存。(2)使用递归思想，建立子树。上层函数中的str指针首先被保存，然后，在该maketree函数内部，str指向了上层函数中括号内的第一个字符。(3)*Str==’，’判断是否还有子树。(4)对树根元素进行存储。(5)也是利用递归，对子树分别输入到列表中。