L2-006. 树的遍历

时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数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

 

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<vector> #include<algorithm> #define MAX 125 using namespace std; struct Node{ int x,l,r; }tree[MAX]; int h[MAX],z[MAX]; int c; int build(int h[],int z[],int len){ int k,i; if(len<=0) return -1; for(i=0;i<len;i++){ if(z[i]==h[len-1]){ k=i; break; } } c++; int root=c; tree[root].x=z[k]; tree[root].l=build(h,z,k); tree[root].r=build(h+k,z+k+1,len-k-1); return root; } void bfs(int x){ int f=0,i; queue<int> q; q.push(x); while(q.size()){ if(f==0){ printf("%d",tree[q.front()].x); f=1; } else printf(" %d",tree[q.front()].x); if(tree[q.front()].l>-1) q.push(tree[q.front()].l); if(tree[q.front()].r>-1) q.push(tree[q.front()].r); q.pop(); } } int main() { int n,i,j; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&h[i]); } for(i=0;i<n;i++){ scanf("%d",&z[i]); } c=0; build(h,z,n); bfs(1); return 0; }

 

二叉树的遍历

 HRBUST - 2040 

给出一棵二叉树的中序和前序遍历，输出它的后序遍历。

Input

本题有多组数据，输入处理到文件结束。

每组数据的第一行包括一个整数n，表示这棵二叉树一共有n个节点。

接下来的一行每行包括n个整数，表示这棵树的中序遍历。

接下来的一行每行包括n个整数，表示这棵树的前序遍历。

3<= n <= 100

Output

每组输出包括一行，表示这棵树的后序遍历。

Sample Input

74 2 5 1 6 3 7

1 2 4 5 3 6 7

 

Sample Output

4 5 2 6 7 3 1 

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<vector> #include<algorithm> #define MAX 405 using namespace std; struct Node{ int x,l,r; }tree[MAX]; int q[MAX],z[MAX]; int c; int build(int q[],int z[],int len){ int k,i; if(len<=0) return -1; for(i=0;i<len;i++){ if(z[i]==q[0]){ k=i; break; } } c++; int root=c; tree[root].x=z[k]; tree[root].l=build(q+1,z,k); tree[root].r=build(q+k+1,z+k+1,len-k-1); return root; } void dfs(int x){ int i; if(x==-1) return; dfs(tree[x].l); dfs(tree[x].r); printf("%d ",tree[x].x); } int main() { int n,i,j; while(~scanf("%d",&n)){ memset(tree,0,sizeof(tree)); for(i=0;i<n;i++){ scanf("%d",&z[i]); } for(i=0;i<n;i++){ scanf("%d",&q[i]); } c=0; build(q,z,n); dfs(1); printf("\n"); } return 0; }

 

L3-010. 是否完全二叉搜索树

时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

输入格式：

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

输出格式：

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出“YES”，如果该树是完全二叉树；否则输出“NO”。

输入样例1： 9 38 45 42 24 58 30 67 12 51 输出样例1： 38 45 24 58 42 30 12 67 51 YES 输入样例2： 8 38 24 12 45 58 67 42 51 输出样例2： 38 45 24 58 42 12 67 51 NO #include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<vector> #include<algorithm> #define MAX 105 using namespace std; struct Node{ int x,l,r; }tree[MAX]; int n,c,f,cc; int dfs(int y,int x){ if(y==-1){ c++; tree[c].x=x; return c; } if(x>tree[y].x) tree[y].l=dfs(tree[y].l,x); else tree[y].r=dfs(tree[y].r,x); return y; } queue<int> qq; void bfs(int x){ queue<int> q; q.push(x); cc=1; while(q.size()){ qq.push(tree[q.front()].x); if(tree[q.front()].l>-1){ cc++; q.push(tree[q.front()].l); } else if(cc<n) f=1; if(tree[q.front()].r>-1){ cc++; q.push(tree[q.front()].r); } else if(cc<n) f=1; q.pop(); } } int main() { int x,i,j; scanf("%d",&n); memset(tree,-1,sizeof(tree)); scanf("%d",&tree[1].x); c=1; for(i=1;i<n;i++){ scanf("%d",&x); dfs(1,x); } f=0; bfs(1); int ff=0; while(qq.size()){ if(ff==0){ printf("%d",qq.front()); ff=1; } else printf(" %d",qq.front()); qq.pop(); } printf("\n"); if(f==1) printf("NO\n"); else printf("YES\n"); return 0; }

 

转载于:https://www.cnblogs.com/yzm10/p/8640974.html