#include<iostream>
using namespace std;
#define m 3                        //树的度数
#define maxsize 50                 //数组元素个数最大值
typedef char datatype;           
typedef struct node                //树的扩充孩子表示（数组方式）法中结点类型 多了 双亲
{
 datatype data;
 int child[m];
 int parent;
}treenode;

typedef struct                     //层号表示法中结点的类型
{
 int lev;
 datatype data;
}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为其前一个元素j的第一个子女，注意是：  第一个！
  {
   tree[i].parent=j;
   tree[j].child[0]=i;          //直接写 child[0]   第一个子女嘛
  }
  else
  {
   while(ltree[i].lev <ltree[j].lev)  //寻找结点i的兄弟(结点i必与结点j的某个前件是兄弟）
    j=tree[j].parent;
   tree[i].parent = tree[j].parent;   // 结点i和结点j的双亲相同
   
   j=tree[j].parent;                  //注意j的变化
   k=0;                               //将结点i挂到双亲结点上
   
   while(tree[j].child[k]!=-1)        //此时 tree[i]就不一定是tree[j] 第一个孩子了     
    k++;
   tree[j].child[k]=i;
  }
 }
}

int main()
{
 int i=-1;
 cout<<"请输入树结点(层号表示)"<<endl;
 int level;          //暂时性存放层号,
 datatype dat;       //暂时性存放结点数据
 while(1)   
 {
  cin>>level;
 // if(level==' '||level==',')  // 便于格式输入，结点之间可以用 ，或 空格 隔开??/怎么实现 ，因为这里 level 是int型所以不能输入字符型。            
 //  continue;               //当然可以先输入dat，但输入就反了，变成先输入数据，在输入层号。
  if(level==0)             //直到输入为换行符结束??  注意level 不是字符型，而是int型
   break;                 
  cin>>dat;
  ++i;
  ltree[i].lev=level;        
  ltree[i].data=dat;
  
 }
 length=i;         

// levelnode ltree[]={{1,'a'},{2,'b'},{2,'c'},{5,'f'},{5,'g'},{5,'h'},{2,'d'},{2,'e'},{3,'j'},{3,'i'}};
// length=10;        //当初就是因为上面那一直出错，才这样直接复值。
 leveltotree(length,ltree,&root,tree);
 cout<<"输出结点(孩子(数组方式)表示法):"<<endl;
 for(i=0;i<length;i++)
 {
  cout<<tree[i].data<<"  ";            //输出根结点
  for(int j=0;j<m;j++)                 //输出孩子
   cout<<tree[i].child[j]<<"  ";
  cout<<tree[i].parent;                //输出双亲
  cout<<endl;
 }
}

评论