森林转换成二叉树以及二叉树还原为森林代码

思路：u的孩子节点为v1, v2, v3....（v1,v2,....互为兄弟节点） 那么将u的一个孩子节点（v1）连在u的左子树上，那么其他的孩子节点都连在v1的右子树上！ #include iostream #include cstring #include cstdio #include algorithm using namespace std; int g[15][15]; int par[15];//如果该节点有父亲节点说明该节点不是一个独立的点！ int vis[15]; struct Tree{ int d; Tree *lchild, *rchild; Tree(){ lchild=rchild=NULL; Tree(int x){ lchild=rchild=NULL; d=x; int n, m; void buildT(Tree* T, int u){ bool flag=false; T=new Tree(u); Tree *cur=T; vis[u]=1; for(int v=1; v ++v) if(g[u][v]){ if(!flag){ buildT(cur- lchild, v); cur=cur- lchild; flag=true; else{ buildT(cur- rchild, v); cur=cur- rchild;
rebuildMap(ld[u], u); rebuildMap(rd[u], fa);//u节点以及其兄弟节点的父亲节点都是u的父亲节点 void buildT(int u){ int v, cur; bool flag=false; for(v=1; v ++v) if(mp[u][v]){ if(!flag){ ld[u]=v; cur=v; flag=true; else{ rd[cur]=v;//将u的兄弟节点都链接在右子树上 cur=v; buildT(v); int main(){ while(scanf("%d%d", n, m)!=EOF){ memset(par, 0, sizeof(par)); memset(pp, 0, sizeof(pp)); memset(mp, 0, sizeof(mp)); while(m--){ int u, v; scanf("%d%d", u, mp[u][v]=1; par[v]=u; int root=-1, cur; for(int i=1; i ++i){ if(!par[i]){ if(root!=-1) rd[cur]=i; if(root==-1) root=i; buildT(i); cur=i; printf("打印树.....\n"); printT(root); printf("\n"); rebuildMap(root, -1); printf("\n\n还原树....\n"); for(int i=1; i ++i) for(int j=1; j ++j) if(pp[i][j]) printf("%d %d\n", i, j); printf("KO!\n"); return 0; 测试数据..... */