1 /* 2 森林轉換成二叉樹 3 思路：u的孩子節點為v1, v2, v3....（v1,v2,....互為兄弟節點） 4 那么將u的一個孩子節點（v1）連在u的左子樹上，那么其他的孩子節點都連在v1的右子樹上！ 5 */ 6 #include<iostream> 7 #include<cstring> 8 #include<cstdio> 9 #include<algorithm> 10 using namespace std; 11 int g[15][15]; 12 int par[15];//如果該節點有父親節點說明該節點不是一個獨立的點！ 13 int vis[15]; 14 15 struct Tree{ 16 int d; 17 Tree *lchild, *rchild; 18 Tree(){ 19 lchild=rchild=NULL; 20 } 21 22 Tree(int x){ 23 lchild=rchild=NULL; 24 d=x; 25 } 26 }; 27 int n, m; 28 29 void buildT(Tree* &T, int u){ 30 bool flag=false; 31 T=new Tree(u); 32 Tree *cur=T; 33 vis[u]=1; 34 for(int v=1; v<=n; ++v) 35 if(g[u][v]){ 36 if(!flag){ 37 buildT(cur->lchild, v); 38 cur=cur->lchild; 39 flag=true; 40 } 41 else{ 42 buildT(cur->rchild, v); 43 cur=cur->rchild; 44 } 45 } 46 } 47 48 49 void prePrint(Tree *T){ 50 if(!T) return ; 51 cout<<T->d<<" "; 52 prePrint(T->lchild); 53 prePrint(T->rchild); 54 } 55 56 57 int main(){ 58 Tree *T=NULL; 59 while(cin>>n>>m){ 60 memset(g, 0, sizeof(g)); 61 memset(vis, 0, sizeof(vis)); 62 while(m--){ 63 int u, v; 64 cin>>u>>v; 65 g[u][v]=1; 66 par[v]=u; 67 } 68 bool flag=false; 69 Tree *cur; 70 for(int i=1; i<=n; ++i) 71 if(!vis[i]){ 72 if(!flag){ 73 flag=true; 74 buildT(T, i); 75 cur=T; 76 } 77 else if(!par[i]){//也就是找入度為0的節點！ 78 buildT(cur->rchild, i); 79 cur=cur->rchild; 80 } 81 } 82 prePrint(T); 83 } 84 return 0; 85 } 86
?
//數組實現....森林轉成二叉樹以及二叉樹還原成森林 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define N 100 using namespace std;int mp[N][N]; int pp[N][N]; int n, m; int ld[N], rd[N], par[N];void printT(int u){if(u==0) return;printT(ld[u]);printT(rd[u]); printf("%d ", u); }void rebuildMap(int u, int fa){if(u==0) return ;if(fa!=-1) pp[fa][u]=1;rebuildMap(ld[u], u);rebuildMap(rd[u], fa);//u節點以及其兄弟節點的父親節點都是u的父親節點 } void buildT(int u){int v, cur;bool flag=false; for(v=1; v<=n; ++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, &v);mp[u][v]=1;par[v]=u;} int root=-1, cur;for(int i=1; i<=n; ++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<=n; ++i)for(int j=1; j<=n; ++j)if(pp[i][j])printf("%d %d\n", i, j);printf("KO!\n"); }return 0; } /* 測試數據..... 11 8 2 1 2 3 2 4 5 6 6 9 5 7 5 8 11 10 */
?
)
,怎么處理?)
)
的區別)
)
)
)
)
