leveltotree.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

#include <stdio.h>
# define m 3              /* 树的度数*/
# define MAXSIZE 20       /* 数组元素个数的最大值*/
typedef char datatype;    /* 树中结点值的类型*/
typedef struct node {     /*树的扩充孩子表示法中结点的类型*/
    datatype  data;
      int  child[m];
      int parent;
 } treenode;
typedef struct {          /*层号表示法结点的类型*/
    datatype data;
    int lev;
  } levelnode;
treenode tree[MAXSIZE];   /*树的扩充孩子表示法的存储数组*/
   int  root ;            /*根结点的下标*/      
   int  length;           /*树中实际所含结点的个数*/
levelnode ltree[MAXSIZE]; /*树层号表示法的数组*/
void leveltotree(int length,levelnode ltree[],int *root,treenode tree[])
{        /*将树的层号表示转换成树的扩充孩子表示法的表示*/
  int i,j,k;
  for (i=0;i<length;++i)
     for (j=0;j<m;++j)
       tree[i].child[j]=-1;
  *root=0;  /*第一个元素为根结点*/
  tree[0].data=ltree[0].data;
  tree[0].parent=-1;  /*根结点的双亲为空*/
  for (i=1;i<length;++i)
  {
    tree[i].data=ltree[i].data;
    j=i-1;
    if (ltree[i].lev>ltree[j].lev)/*结点i为其前一个元素的第一个子女*/
       {
         tree[i].parent=j;
         tree[j].child[0]=i;
        }
     else {
            while (ltree[i].lev<ltree[j].lev)/*寻找结点i的双亲*/
                j=tree[j].parent;
            tree[i].parent=tree[j].parent; /*结点i和结点j的双亲相同*/
            j=tree[j].parent;
            k=0;  /*将结点i挂到双亲结点上*/
            while (tree[j].child[k]!=-1)
                ++k;
            tree[j].child[k]=i;
           }
   }
}
void preorder(treenode tree[],int root)
{  int i;
   if (root!=-1)
     {
       printf("%c",tree[root].data);
       for (i=0;i<m;++i)
          preorder(tree,tree[root].child[i]);
      }
 }
main()
{  int i,x;  char ch;
   printf("input the length:");
   scanf("%d",&length);
   for (i=0;i<length;++i)
     { 
        scanf("%d",&x);
        ltree[i].lev=x;ch=getchar();
        ltree[i].data=ch; getchar();
       }
   leveltotree(length,ltree,&root,tree);root=0;
   preorder(tree,root);
}