数据结构课后习题解答第六章 树和二叉树

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