}
LS=LS->link; }
return max+1; }
P96 广义表的建立creat(LS) void creat(struct node1 *LS) {
char ch;
scanf(\ if(ch=='#') LS=NULL; else if(ch=='(')
{LS=(struct node*)malloc(sizeof(struct node)); LS->atom=0;
creat(LS->ds.slink); } else
{ LS=(struct node*)malloc(sizeof(struct node)); LS->atom=1; LS->ds.data=ch; }
scanf(\ if(LS==NULL); else if(ch==',')
creat(LS->link); else if((ch==')')||(ch==';')) LS->link=NULL; }
P97 输出广义表print(LS) void print(struct node1 *LS) {
if(LS->atom==0) {
printf(\
if(LS->ds.slink==NULL) printf(\ else
print(LS->ds.slink); } else
printf(\
if(LS->atom==0) printf(\ if(LS->link!=NULL) {
printf(\
print(LS->link); } }
P98 该算法的时间复杂度为O(n)。整个完整程序如下： #include
struct node1 *link; union {
struct node1 *slink; elemtype data; } ds; };
void creat(struct node1 LS) /*建立广义表的单链表*/ {
char ch;
scanf(\ if(ch=='#') LS=NULL; else if(ch=='(')
{LS=(struct node1*)malloc(sizeof(struct node1)); LS->atom=0; creat(LS->ds.slink); } else
{ LS=(struct node1*)malloc(sizeof(struct node1)); LS->atom=1; LS->ds.data=ch; }
scanf(\ if(LS==NULL); else if(ch==',')
creat(LS->link); else if((ch==')')||(ch==';')) LS->link=NULL;
}
void print(struct node1 LS) /*输出广义单链表*/ {
if(LS->atom==0) {
printf(\
if(LS->ds.slink==NULL) printf(\ else
print(LS->ds.slink); } else
printf(\ if(LS->atom==0) printf(\ if(LS->link!=NULL) {
printf(\
print(LS->link); } }
int depth(struct node1 LS) /*求广义表的深度*/ {
int max=0;
while(LS!=NULL) { if(LS->atom==0)
{ int dep=depth(LS->ds.slink); if(dep>max) max=dep; }
LS=LS->link; }
return max+1; }
main() { int dep;
struct node1 *p=NULL;
creat(p); /*建立广义表的单链表*/ print(p); /*输出广义单链表*/ dep=depth(p); /*求广义表的深度*/ printf(\}
第六章 树
P109 二叉链表的结点类型定义如下： typedef struct btnode { anytype data;
struct btnode *Lch,*Rch; }tnodetype;
P109 三叉链表的结点类型定义如下： typedef struct btnode3 { anytype data;
struct btnode *Lch,*Rch，*Parent ; }tnodetype3;
P112 C语言的先序遍历算法： void preorder (tnodetype *t)
/*先序遍历二叉树算法，t为指向根结点的指针*/ { if (t!=NULL)
{printf(\ preorder(t->lch); preorder(t->rch); } }
P113 C语言的中序遍历算法： void inorder(tnodetype *t)
/*中序遍历二叉树算法，t为指向根结点的指针*/ {
if(t!=NULL) {inorder(t->lch);
printf(\ inorder(t->rch); } }
P113 C语言的后序遍历算法： void postorder(tnodetype *t)
/*后序遍历二叉树算法，t为指向根结点的指针*/ {
if(t!=NULL)
{ postorder(t->lch); postorder(t->rch); printf(\ } }
P114 如果引入队列作为辅助存储工具，按层次遍历二叉树的算法可描述如下： void levelorder(tnodetype *t)
/*按层次遍历二叉树算法，t为指向根结点的指针*/ {tnodetype q[20]; /*辅助队列*/ front=0;
rear=0; /*置空队列*/ if (t!=NULL) { rear++;
q[rear]=t; /*根结点入队*/ }
while (front!=rear) { front++; t=q [front];
printf (\
if (t->lch!=NULL) /*t的左孩子不空，则入队*/ { rear++;
q [rear]=t->lch; }
if (t->rch!=NULL) /*t的右孩子不空，则入队*/ { rear++;
q [rear]=t->rch; } } }
P115 以中序遍历的方法统计二叉树中的结点数和叶子结点数，算法描述为： void inordercount (tnodetype *t)
/*中序遍历二叉树，统计树中的结点数和叶子结点数*/ { if (t!=NULL)
{ inordercount (t->lch); /*中序遍历左子树*/ printf (\ /*访问根结点*/ countnode++; /*结点计数*/ if ((t->lch==NULL)&&(t->rch==NULL)) countleaf++; /*叶子结点计数*/
inordercount (t->rch); /*中序遍历右子树*/ } }
P115 可按如下方法计算一棵二叉树的深度： void preorderdeep (tnodetype *t,int j)
/*先序遍历二叉树，并计算二叉树的深度*/ { if (t!=NULL)
{ printf (\ /*访问根结点*/ j++;