1064 Complete Binary Search Tree (30 分)
今天PAT遇到了一个题目
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
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.
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.
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.
10
1 2 3 4 5 6 7 8 9 06 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) }
学到了！！！
原文：https://www.cnblogs.com/yyyxu/p/14979450.html