免费做网站报价苏华建设集团网站

免费做网站报价,苏华建设集团网站,app系统开发费用,辽宁建设工程信息网分数7-5 玩转二叉树给定一棵二叉树的中序遍历和前序遍历#xff0c;请你先将树做个镜面反转#xff0c;再输出反转后的层序遍历的序列。所谓镜面反转#xff0c;是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。输入格式#xff1a;输入第一行给出一个正…7-5 玩转二叉树给定一棵二叉树的中序遍历和前序遍历请你先将树做个镜面反转再输出反转后的层序遍历的序列。所谓镜面反转是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。输入格式输入第一行给出一个正整数N≤30是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。输出格式在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔行首尾不得有多余空格。输入样例7 1 2 3 4 5 6 7 4 1 3 2 6 5 7输出样例4 6 1 7 5 3 2代码实现#includebits/stdc.h using namespace std; int n,m; int pre[33],in[33],cnt[33]; struct node{ int data; struct node *lch,*rch; }; typedef struct node *tree; tree build(int pre[],int in[],int n){ if(n0) return NULL; node *tnew node; t-datapre[0]; t-lcht-rchNULL; int i; for(i0;in;i){ if(in[i]pre[0]) break; } t-lchbuild(pre1,in,i); t-rchbuild(pre1i,in1i,n-1-i); return t; } void trans(tree t){ if(tNULL) return; swap(t-lch,t-rch); trans(t-lch); trans(t-rch); } void order(tree t){ if(tNULL) return; queuetree q; tree p; q.push(t); while(q.size()){ pq.front(); q.pop(); cnt[m]p-data; if(p-lch) q.push(p-lch); if(p-rch) q.push(p-rch); } } int main(){ cinn; for(int i0;in;i) cinin[i]; for(int i0;in;i) cinpre[i]; tree tbuild(pre,in,n); trans(t); order(t); for(int i0;in;i){ coutcnt[i]; if(in-1) cout ; } return 0; }7-6 部落在一个社区里每个人都有自己的小圈子还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里于是要请你统计一下在一个给定社区中到底有多少个互不相交的部落并且检查任意两个人是否属于同一个部落。输入格式输入在第一行给出一个正整数N≤104是已知小圈子的个数。随后N行每行按下列格式给出一个小圈子里的人K P[1] P[2] ⋯ P[K]其中K是小圈子里的人数P[i]i1,⋯,K是小圈子里每个人的编号。这里所有人的编号从1开始连续编号最大编号不会超过104。之后一行给出一个非负整数Q≤104是查询次数。随后Q行每行给出一对被查询的人的编号。输出格式首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询如果他们属于同一个部落则在一行中输出Y否则输出N。输入样例4 3 10 1 2 2 3 4 4 1 5 7 8 3 9 6 4 2 10 5 3 7输出样例10 2 Y N代码实现#includebits/stdc.h using namespace std; int n; const int N1e410; int fa[N]; int find(int x){ if(fa[x]!x) fa[x]find(fa[x]); return fa[x]; } void un(int x,int y){ int dlfind(x); int drfind(y); if(dl!dr){ fa[dr]dl; } } int main(){ for(int i1;i1e410;i){ fa[i]i; } cinn; int maxn0,sum0; while(n--){ int t,x,y; cintx; maxnmax(x,maxn); for(int i1;it;i){ ciny; maxnmax(y,maxn); un(x,y); } } for(int i1;imaxn;i){ if(fa[i]i) sum; } coutmaxn sumendl; int m; cinm; while(m--){ int a,b; cinab; if(find(a)find(b)) coutYendl; else coutNendl; } return 0; }7-7 列出叶结点对于给定的二叉树本题要求你按从上到下、从左到右的顺序输出其所有叶结点。输入格式首先第一行给出一个正整数 n≤10为树中结点总数。树中的结点从 0 到 n−1 编号。随后 n 行每行给出一个对应结点左右孩子的编号。如果某个孩子不存在则在对应位置给出 -。编号间以 1 个空格分隔。输出格式在一行中按规定顺序输出叶结点的编号。编号间以 1 个空格分隔行首尾不得有多余空格。输入样例8 1 - - - 0 - 2 7 - - - - 5 - 4 6输出样例4 1 5代码实现#includebits/stdc.h using namespace std; struct node { char l,r; }; node tree[11]; queueint leaves; mapint,bool not_root; void find_leave(int r) { leaves.push(r); bool firsttrue; while(!leaves.empty()) { int tleaves.front(); leaves.pop(); if(tree[t].l!-)leaves.push(tree[t].l-0); if(tree[t].r!-)leaves.push(tree[t].r-0); if(tree[t].l-tree[t].r-){ if(first){coutt;firstfalse;} else cout t;} } } int main() { int N; cinN; for(int i0;iN;i) { cintree[i].ltree[i].r; if(tree[i].l!-)not_root[tree[i].l-0]true; if(tree[i].r!-)not_root[tree[i].r-0]true; } int root; for(int i0;iN;i) { if(!not_root[i]){ rooti; break; } } find_leave(root); }7-8 完全二叉树的层序遍历一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是完美二叉树。对于深度为 D 的有 N 个结点的二叉树若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点这样的树就是完全二叉树。给定一棵完全二叉树的后序遍历请你给出这棵树的层序遍历结果。输入格式输入在第一行中给出正整数 N≤30即树中结点个数。第二行给出后序遍历序列为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。输出格式在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔行首尾不得有多余空格。输入样例8 91 71 2 34 10 15 55 18输出样例18 34 55 71 2 10 15 91实现代码#includebits/stdc.h using namespace std; int n; int *tree; void dfs(int x){ if(xn){ dfs(2*x); dfs(2*x1); cintree[x]; } } int main(){ cinn; tree new int[n1]; dfs(1); for(int i1;in;i){ couttree[i]; if(in) cout ; } return 0; }7-9 交换二叉树中每个结点的左孩子和右孩子以二叉链表作为二叉树的存储结构交换二叉树中每个结点的左孩子和右孩子。输入格式:输入二叉树的先序序列。提示一棵二叉树的先序序列是一个字符串若字符是‘#’,表示该二叉树是空树否则该字符是相应结点的数据元素。输出格式:输出有两行第一行是原二叉树的中序遍历序列第二行是交换后的二叉树的中序遍历序列。输入样例:ABC##DE#G##F###输出样例:CBEGDFA AFDGEBC实现代码#includebits/stdc.h using namespace std; struct node{ char data; struct node *lch,*rch; }; typedef struct node *tree; tree build(){ node *tnew node; char a; cina; if(a#) return NULL; t-dataa; t-lchbuild(); t-rchbuild(); return t; } void order(tree t){ if(tNULL) return; order(t-lch); coutt-data; order(t-rch); } void trans(tree t){ if(tNULL) return; swap(t-lch,t-rch); trans(t-lch); trans(t-rch); } int main(){ tree tbuild(); order(t); coutendl; trans(t); order(t); return 0; }7-10 建立与遍历二叉树以字符串的形式定义一棵二叉树的先序序列若字符是‘#’, 表示该二叉树是空树否则该字符是相应结点的数据元素。读入相应先序序列建立二叉链式存储结构的二叉树然后中序遍历该二叉树并输出结点数据。输入格式:字符串形式的先序序列即结点的数据类型为单个字符输出格式:中序遍历结果输入样例:在这里给出一组输入。例如ABC##DE#G##F###输出样例:在这里给出相应的输出。例如CBEGDFA实现代码#includebits/stdc.h using namespace std; struct node{ char data; struct node *lch,*rch; }; typedef struct node *tree; tree build(){ node *tnew node; char a; cina; if(a#) return NULL; t-dataa; t-lchbuild(); t-rchbuild(); return t; } void order(tree t){ if(tNULL) return; order(t-lch); coutt-data; order(t-rch); } int main(){ tree tbuild(); order(t); return 0; }7-11 树的遍历给定一棵二叉树的后序遍历和中序遍历请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。输入格式输入第一行给出一个正整数N≤30是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。输出格式在一行中输出该树的层序遍历的序列。数字间以1个空格分隔行首尾不得有多余空格。输入样例7 2 3 1 5 7 6 4 1 2 3 4 5 6 7输出样例4 1 6 3 5 7 2实现代码#includebits/stdc.h using namespace std; int n,m; int post[33],in[33],cnt[33]; struct node{ int data; struct node *lch,*rch; }; typedef struct node *tree; tree build(int post[],int in[],int root,int start,int end){ if(root0||startend) return NULL; node *tnew node; t-datapost[root]; t-lcht-rchNULL; int i; for(i0;in;i){ if(in[i]post[root]) break; } t-lchbuild(post,in,root-endi,start,i); t-rchbuild(post,in,root-1,i1,end); return t; } void order(tree t){ if(tNULL) return; queuetree q; tree p; q.push(t); while(q.size()){ pq.front(); q.pop(); cnt[m]p-data; if(p-lch) q.push(p-lch); if(p-rch) q.push(p-rch); } } int main(){ cinn; for(int i0;in;i) cinpost[i]; for(int i0;in;i) cinin[i]; tree tbuild(post,in,n-1,0,n); order(t); for(int i0;in;i){ coutcnt[i]; if(in-1) cout ; } return 0; }7-12 哈夫曼树哈夫曼树第一行输入一个数n表示叶结点的个数。需要用这些叶结点生成哈夫曼树根据哈夫曼树的概念这些结点有权值即weight题目需要输出哈夫曼树的带权路径长度WPL。输入格式:第一行输入一个数n第二行输入n个叶结点叶结点权值不超过10002n1000。输出格式:在一行中输出WPL值。输入样例:5 1 2 2 5 9输出样例:37实现代码#includebits/stdc.h using namespace std; int n; priority_queueint,vectorint,greaterint q; int main(){ cinn; while(n--){ int a; cina; q.push(a); } int sum0; while(q.size()){ int xq.top(); q.pop(); if(q.empty()) break; int yq.top(); q.pop(); sumxy; q.push(xy); } coutsum; return 0; }7-13 树层次遍历我们已知二叉树与其自然对应的树相比二叉树中结点的左孩子对应树中结点的左孩子二叉树中结点的右孩子对应树中结点的右兄弟。进而我们可以利用“基于带空指针信息的先根序列构建二叉树”的方法来构建其对应的树的左孩子-右兄弟存储结构。如8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0对应图1(a)所示的树1 2 0 3 0 4 0 0 0对应如图1(b)所示的树。请编写程序用上述方法构建树并给出树的层次遍历序列。输入格式:输入为一组用空格间隔的整数个数不超过100个表示带空指针信息的二叉树先根序列。其中空指针信息用0表示输出格式:输入为一组整数每个整数后一个空格表示该树的层次遍历序列。输入样例:1 2 0 3 0 4 0 0 0输出样例:1 2 3 4实现代码#includebits/stdc.h using namespace std; int a[111]; stackint st; vectorvectorint v(111); void dj(){ st.push(a[0]); int i1; while(st.size()){ if(a[i]!0){ st.push(a[i]); i; } else{ int mst.size(); int nst.top(); st.pop(); i; v[m].push_back(n); } } } int main(){ int i0; int n; while(cinn){ a[i]n; } dj(); for(int i0;iv.size();i){ for(int j0;jv[i].size();j){ coutv[i][j] ; } } return 0; }