天梯赛/PAT 二叉树总结 L2-006. 树的遍历（后序中序建树+层序输出） L3-010. 是否完全二叉搜索树（搜索建树+层序输出+完全判断） PS：根据BST性质，一个先序序列也可建树，方法一样。 1147 Heaps (30 分)（层序建树+大小堆判断+后序输出） 链表按一叉树处理
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数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; }
二叉树的遍历（前序中序建树+后续输出）
给出一棵二叉树的中序和前序遍历，输出它的后序遍历。
Input
本题有多组数据，输入处理到文件结束。
每组数据的第一行包括一个整数n，表示这棵二叉树一共有n个节点。
接下来的一行每行包括n个整数，表示这棵树的中序遍历。
接下来的一行每行包括n个整数，表示这棵树的前序遍历。
3<= n <= 100
Output
每组输出包括一行，表示这棵树的后序遍历。
Sample Input
7
4 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(" "); } return 0; }
L3-010. 是否完全二叉搜索树（搜索建树+层序输出+完全判断）
将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。
输入格式：
输入第一行给出一个不超过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
PS：根据BST性质，一个先序序列也可建树，方法一样。
#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(" "); if(f==1) printf("NO "); else printf("YES "); return 0; }
1147 Heaps (30 分)（层序建树+大小堆判断+后序输出）
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))
Your job is to tell if a given complete binary tree is a heap.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: M (≤ 100), the number of trees to be tested; and N (1 < N ≤ 1,000), the number of keys in each tree, respectively. Then M lines follow, each contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.
Output Specification:
For each given tree, print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all. Then in the next line print the tree's postorder traversal sequence. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line.
Sample Input:
3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56
Sample Output:
Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct Node{ int x,l,r; }tree[4005]; vector<int> v; void dfs(int i){ if(i==-1) return; dfs(tree[i].l); dfs(tree[i].r); v.push_back(tree[i].x); } int main() { int n,m,x,i,j,k; scanf("%d%d",&m,&n); while(m--){ memset(tree,-1,sizeof(tree)); for(i=1;i<=n;i++){ scanf("%d",&x); tree[i].x=x; } for(i=1;i<=n;i++){ if(2*i<=n) tree[i].l=2*i; if(2*i+1<=n) tree[i].r=2*i+1; } int da=0,xiao=0; for(i=1;i<=n;i++){ if(2*i<=n){ if(tree[i].x>tree[2*i].x){ da=1; } if(tree[i].x<tree[2*i].x){ xiao=1; } } if(2*i+1<=n){ if(tree[i].x>tree[2*i+1].x){ da=1; } if(tree[i].x<tree[2*i+1].x){ xiao=1; } } } if(da&&xiao){ printf("Not Heap "); } else if(da){ printf("Max Heap "); } else{ printf("Min Heap "); } v.clear(); dfs(1); for(i=0;i<v.size();i++){ if(i>0) printf(" "); printf("%d",v[i]); } printf(" "); } return 0; }