#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; }}
评论