for(p=fc;c==',';p->nextsib=nc,p=nc) //建兄弟链 if(!CreateCSTree_GList(nc)) return ERROR; p->nextsib=NULL;
if((c=getchar())!=')') return ERROR; //括号不配对 }
else T->firtchild=NULL; //叶子结点 return OK;
}//CreateBiTree_GList
分析:书后给出了两个间接递归的算法,事实上合成一个算法在形式上可能更好一些.本算法另一个改进之处在于加入了广义表格式是否合法的判断. 6.74
void PrintGlist_CSTree(CSTree T)//按广义表形式输出孩子兄弟链表表示的树 {
printf(\
if(T->firstchild) //非叶结点 {
printf(\
for(p=T->firstchild;p;p=p->nextsib) {
PrintGlist_CSTree(p);
if(p->nextsib) printf(\最后一个孩子后面不需要加逗号 } printf(\ }//if
}//PrintGlist_CSTree 6.75
char c;
int pos=0; //pos是全局变量,指示已经分配到了哪个结点
Status CreateCTree_GList(CTree &T,int &i)//由广义表形式的输入建立孩子链表 {
c=getchar();
T.nodes[pos].data=c;
i=pos++; //i是局部变量,指示当前正在处理的子树根 if((c=getchar())=='(') //非叶结点 {
CreateCTree_GList();
p=(CTBox*)malloc(sizeof(CTBox));
T.nodes[i].firstchild=p;
p->child=pos; //建立孩子链的头 for(;c==',';p=p->next) //建立孩子链
{
CreateCTree_GList(T,j); //用j返回分配得到的子树根位置 p->child=j;
p->next=(CTBox*)malloc(sizeof(CTBox)); }
p->next=NULL;
if((c=getchar())!=')') return ERROR; //括号不配对 }//if
else T.nodes[i].firtchild=NULL; //叶子结点 return OK;
}//CreateBiTree_GList
分析:该算法中,pos变量起着\分配\结点在表中的位置的作用,是按先序序列从上向下分配,因此树根T.r一定等于0,而最终的pos值就是结点数T.n. 6.76
void PrintGList_CTree(CTree T,int i)//按广义表形式输出孩子链表表示的树 {
printf(\
if(T.nodes[i].firstchild) //非叶结点 {
printf(\
for(p=T->firstchild;p;p=p->nextsib) {
PrintGlist_CSTree(T,p->child);
if(p->nextsib) printf(\最后一个孩子后面不需要加逗号 } printf(\ }//if
}//PrintGlist_CTree
数据结构课后习题解答第六章 树和二叉树
