长沙网站建设哪家最好,php 企业网站模板,济南房产信息网官网,深圳网站设计招聘1 /*2 森林转换成二叉树3 思路#xff1a;u的孩子节点为v1, v2, v3....#xff08;v1,v2,....互为兄弟节点#xff09; 4 那么将u的一个孩子节点#xff08;v1#xff09;连在u的左子树上#xff0c;那么其他的孩子节点都连在v1的右子树上#xff01; 5 … 1 /*2 森林转换成二叉树3 思路u的孩子节点为v1, v2, v3....v1,v2,....互为兄弟节点 4 那么将u的一个孩子节点v1连在u的左子树上那么其他的孩子节点都连在v1的右子树上 5 */ 6 #includeiostream7 #includecstring8 #includecstdio9 #includealgorithm
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 lchildrchildNULL;
20 }
21
22 Tree(int x){
23 lchildrchildNULL;
24 dx;
25 }
26 };
27 int n, m;
28
29 void buildT(Tree* T, int u){
30 bool flagfalse;
31 Tnew Tree(u);
32 Tree *curT;
33 vis[u]1;
34 for(int v1; vn; v)
35 if(g[u][v]){
36 if(!flag){
37 buildT(cur-lchild, v);
38 curcur-lchild;
39 flagtrue;
40 }
41 else{
42 buildT(cur-rchild, v);
43 curcur-rchild;
44 }
45 }
46 }
47
48
49 void prePrint(Tree *T){
50 if(!T) return ;
51 coutT-d ;
52 prePrint(T-lchild);
53 prePrint(T-rchild);
54 }
55
56
57 int main(){
58 Tree *TNULL;
59 while(cinnm){
60 memset(g, 0, sizeof(g));
61 memset(vis, 0, sizeof(vis));
62 while(m--){
63 int u, v;
64 cinuv;
65 g[u][v]1;
66 par[v]u;
67 }
68 bool flagfalse;
69 Tree *cur;
70 for(int i1; in; i)
71 if(!vis[i]){
72 if(!flag){
73 flagtrue;
74 buildT(T, i);
75 curT;
76 }
77 else if(!par[i]){//也就是找入度为0的节点
78 buildT(cur-rchild, i);
79 curcur-rchild;
80 }
81 }
82 prePrint(T);
83 }
84 return 0;
85 }
86 //数组实现....森林转成二叉树以及二叉树还原成森林
#includeiostream
#includecstring
#includecstdio
#includealgorithm
#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(u0) return;printT(ld[u]);printT(rd[u]); printf(%d , u);
}void rebuildMap(int u, int fa){if(u0) 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 flagfalse; for(v1; vn; v)if(mp[u][v]){if(!flag){ld[u]v;curv;flagtrue;}else{rd[cur]v;//将u的兄弟节点都链接在右子树上curv;}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 i1; in; i){if(!par[i]){if(root!-1) rd[cur]i;if(root-1) rooti; buildT(i); curi;}}printf(打印树.....\n); printT(root);printf(\n);rebuildMap(root, -1);printf(\n\n还原树....\n); for(int i1; in; i)for(int j1; jn; 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
*/ 转载于:https://www.cnblogs.com/hujunzheng/p/3924955.html
