二叉树的层次遍历 小根堆的判定和构造 图的深度和广度优先搜索 最小生成树

如果有需要解释的题目请大家评论，我会补上代码解释

问题 A: 任意二叉树的层次遍历

题目描述
有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的层次遍历序列。

#include<iostream>usingnamespace std;int n;int l[105],r[105];int queue[105];voidbfs(int root){int head=-1;int tail=1;
    queue[++head]= root;int cur;while(head< tail){
        cur= queue[head];// cout<<l[cur]<<" "<<r[cur]<<'\n';if(l[cur]!=-1){
            queue[tail++]= l[cur];}if(r[cur]!=-1){
            queue[tail++]= r[cur];}printf("%d ",cur);
        head++;}}intmain(){scanf("%d",&n);int x;for(int i=1;i<=n;i++){scanf("%d",&x);scanf("%d%d",&l[x],&r[x]);}int root=1;bool flag=true;while(flag){
        flag=false;for(int i=1;i<=n;i++){if(l[i]==root||r[i]==root){
                root=i;
                flag=true;}}}bfs(root);return0;}

问题 B: 小根堆的判定

题目描述
堆是以线性连续方式存储的完全二叉树，小根堆的每一个元素都不大于其左右孩子，现在给你n个完全二叉树数组存储序列，请编程判定相应完全二叉树数组存储序列是否为小根堆。

#include<iostream>#include<cstring>usingnamespace std;int a[1005];boolcheck(int x,int n){// cout<<a[x]<<a[x*2]<<a[x*2+1]<<'\n';if(x*2<=n&&a[x*2]<a[x])returnfalse;if(x*2+1<=n&&a[x*2+1]<a[x])returnfalse;returntrue;}intmain(){int T,x,cnt;
    cin>>T;bool flag;while(T--){memset(a,0,sizeof(a));
        cin>>a[1];
        cnt=2;
        flag=false;while(cin.get()!='\n'){
            cin>>a[cnt];
            cnt++;}for(int i=1;i<cnt;i++){if(!check(i,cnt-1)){
                flag=true;}}if(flag) cout<<"False";else cout<<"True";
        cout<<'\n';}return0;}

问题 C: 最小堆的形成

题目描述
现在给你n个结点的完全二叉树数组存储序列，请编程调整为最小堆，并输出相应最小堆的存储序列。

#include<cstdio>#include<algorithm>usingnamespace std;int a[1005];voidpercolateDown(int root,int n){int child,tmp= a[root];for(; root*2<= n; root= child){
        child= root*2;if(child!=n&& a[child+1]<a[child])
            child++;if(a[child]<tmp){
            a[root]=a[child];}elsebreak;}
    a[root]=tmp;}intmain(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=n/2;i>=1;i--){percolateDown(i, n);}for(int i=1;i<=n;i++){printf("%d ",a[i]);}return0;

问题 D: 无向图的深度优先搜索

题目描述
已知一个无向图G的顶点和边，顶点从0依次编号，现在需要深度优先搜索，访问任一邻接顶点时编号小的顶点优先，请编程输出图G的深度优先搜索序列。

#include<cstdio>usingnamespace std;int m,n;bool d[105][105];bool v[105];voiddfs(int x){if(x<0||x>=m)return;printf("%d ",x);for(int i=0;i<m;i++){if(!v[i]&&d[x][i]){
            v[i]=true;dfs(i);}}}intmain(){scanf("%d%d",&m,&n);int x,y;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);
        d[x][y]=d[y][x]=true;}
    v[0]=true;dfs(0);return0;}

问题 E: 无向图的广度优先搜索

题目描述
已知一个无向图G的顶点和边，顶点从0依次编号，现在需要广度优先搜索，访问任一邻接顶点时编号小的顶点优先，请编程输出图G的广度优先搜索序列。

#include<cstdio>usingnamespace std;int m,n;bool d[105][105];bool v[105];int queue[105];voidbfs(int x){int head=0,tail=1;
    queue[head]=x;
    v[x]=true;int top;while(head<tail){
        top= queue[head];for(int i=0;i<m;i++){if(!v[i]&&d[top][i]){
                v[i]=true;// printf("%d ",i);
                queue[tail++]= i;}}printf("%d ",top);
        head++;}}intmain(){scanf("%d%d",&m,&n);int x,y;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);
        d[x][y]=d[y][x]=true;}bfs(0);return0;}

问题 F: 最小生成树

题目描述
已知一个无向图G的顶点和边，顶点从0依次编号，请编程输出图G的最小生成树对应的边权之和。

#include<cstdio>#include<algorithm>usingnamespace std;structedge{int l,r,w;}e[205];boolcmp(edge x,edge y){return x.w<y.w;}int f[105];intfind(int x){return f[x]==x?x:f[x]=find(f[x]);}intmain(){int m,n;scanf("%d%d",&m,&n);int x,y,z;for(int i=1;i<=m;i++) f[i]=i;for(int i=1;i<=n;i++){scanf("%d%d%d",&x,&y,&z);
        e[i].l= x;
        e[i].r= y;
        e[i].w= z;}sort(e+1,e+n+1,cmp);int cnt=0,ans=0,cur=1;int lf,rf;while(cnt!=m-1){
        lf=find(e[cur].l);
        rf=find(e[cur].r);if(lf!=rf){
            ans+= e[cur].w;
            cnt++;
            f[rf]= lf;}
        cur++;}printf("%d",ans);return0;}