今天PAT遇到了一个题目
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node‘s key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node‘s key.
- Both the left and right subtrees must also be binary search trees.
A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input:
10
1 2 3 4 5 6 7 8 9 0Sample Output:
6 3 8 1 5 7 9 0 2 4
这是关于完全二叉排序树的，我还在苦苦思考怎么转化，最后推导公式，得到每个子树根节点的编号，最后还没有AC，唔。。。太菜了
#include <iostream> #include <algorithm> #include <math.h> #define LEFT(i) i*2+1 #define RIGHT(i) i*2+2 using namespace std; const int maxn = 110; int n; int node[maxn]; int newnode[maxn]; void midPrint(int i) { midPrint(LEFT(i)); cout << newnode[i]; midPrint(RIGHT(i)); } void buildTree(int index, int l, int r) { if (index>n) { return; } int mid = (r+l+1) / 2; newnode[index] = node[mid]; buildTree(LEFT(index), l, mid - 1); buildTree(RIGHT(index), mid + 1, r); } int main() { cin >> n; //层数 int levelnum = sqrt(n+1); //左子树结点个数 int leftnum = (pow(2, levelnum) - 1)/2; for (int i = 0; i < n; i++) { cin >> node[i]; } for (int i = 1; i < n; i++) { for (int j = 0; j <n-i; j++) { if (node[j] > node[j+1]) { swap(node[j+1], node[j]); } } } int mid = n - leftnum-1; newnode[0] = node[mid]; buildTree(LEFT(0), 0, mid-1); buildTree(RIGHT(0), mid+1,n-1); printf("%d",newnode[0]); for (int i = 1; i < n; i++) { pritnf(" %d",newnode[i]); } }
记得如果答案不对一定要把printf换成cout，或者相反。
再看看这种AC代码，简洁明了。巧妙运用了中序输出。
#include<stdio.h> #include<stdlib.h> #include <algorithm> #include<math.h> #define MAX 1005 int N, n[MAX], ins[MAX], k = 0; void inorder(int); int main() { int i; scanf("%d", &N); for (i = 0; i < N; i++) scanf("%d", &n[i]); std::sort(n, n + N); inorder(0); //output printf("%d", ins[0]); for (i = 1; i < N; i++) printf(" %d", ins[i]); } void inorder(int root) { if (root >= N) return; inorder(2 * root + 1);//left child is 2*i+1 ins[root] = n[k++]; inorder(2 * root + 2);//right child is 2*(i+1) }
学到了！！！