学步园

 树的建立与基本操作(10分)
成绩: 10 / 折扣: 0.8
在本实验中，程序的输入是一个表示树结构的广义表。假设树的根为 root ，其子树森林 F ＝ （ T1 ， T2 ， … ， Tn ），设与该树对应的广义表为 L ，则 L ＝（原子，子表 1 ，子表 2 ， … ，子表 n ），其中原子对应 root ，子表 i （ 1<i<=n ）对应 Ti 。例如：广义表 (a,(b,(c),(d)),(f,(g),(h ),(i))) 表示的树如图所示：

程序的输出为树的层次结构、树的度以及各种度的结点个数。
在输出树的层次结构时，先输出根结点，然后依次输出各个子树，每个子树向里缩进 4 个空格，如：针对上图表示的树，输出的内容应为：
a
b
c
d
f
g
h
i
Degree of tree: 3
Number of nodes of degree 0: 5
Number of nodes of degree 1: 0
Number of nodes of degree 2: 2
Number of nodes of degree 3: 1
例： （下面的黑体为输入）
(a,(b),(c,(d),(e,(g),(h )),(f)))
a
b
c
d
e
g
h
f
Degree of tree: 3
Number of nodes of degree 0: 5
Number of nodes of degree 1: 0
Number of nodes of degree 2: 2
Number of nodes of degree 3: 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct treenode
{
        char data;
        int parents;
        int degree;
};

int CreateTree(char in[100],struct treenode tree[100],int list[100])
{
        int i,j,k=1,len,kuo=0;
        len = strlen(in);
        tree[0].data = in[1];
        tree[0].parents = -1;
        list[0]=1;

        for (i = 0;i < len;i++)
        {
                tree[i].data = in[i];
                tree[i].parents = -1;
                tree[i].degree = 0;
        }

        for (i = 2;i < len-1;i++)
        {
                if (in[i] == ',' || in[i] == '(' || in[i] == ')')
                {
                        continue;
                }
                else
                {
                        for (j = i , kuo = 0;j >= 0 && kuo != 2;j--)
                        {
                                if (in[j] == '(')
                                {
                                        kuo++;
                                        if (kuo == 2)
                                        {
                                                break;
                                        }
                                }
                                else if (in[j] == ')')
                                {
                                        kuo--;
                                }
                        }
                        tree[i].data = in[i];
                        tree[i].parents = j+1;
                        tree[j+1].degree++;
                        list[k++] = i;
                }
        }
        return k;
}

PrintTree(struct treenode tree[100],int list[100],int i)
{
        int space = 0 , j = i;
        if (i == 0)
        {
                printf("%c\n",tree[list[i]].data);
                return;
        }
        i=list[i];
        while (tree[i].parents != -1)
        {
                space+=4;
                i=tree[i].parents;
        }
        for (i=0;i<space;i++)
        {
                printf(" ");
        }
        printf("%c\n",tree[list[j]].data);
}

void main()
{
        int i,j,k,n,max,degree[100],list[100];
        char in[100];
        struct treenode tree[100];

        gets(in);
        n = CreateTree(in,tree,list);
        for (i=0,max=0;i<n;i++)
        {
                PrintTree(tree,list,i);
                if (tree[list[i]].degree > max)
                {
                        max = tree[list[i]].degree;
                }
        }
        for (i = 0;i <= max;i++)
        {
                degree[i] = 0;
        }
        for (i = 0;i <n;i++)
        {
                degree[tree[list[i]].degree]++;
        }
        printf("Degree of tree: %d\n",max);
        for (i = 0;i<=max;i++)
        {
                printf("Number of nodes of degree %d: %d\n",i,degree[i]);
        }
}