1064 Complete Binary Search Tree(30分)-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 (≤1000). 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 0

Sample Output:

6 3 8 1 5 7 9 0 2 4

 题目大意：给定一串CBT的结点的值序列（值不相同），要求求出该树的层次遍历

 思路：1、完全二叉搜索树的中序序列是递增的，因此我们可以对题目给出的序列进行递增排序，就得到了中序序列

2、结点只有最后一层不满，但是最后一层的结点是从左往右连续分布的，因此我们可以利用层次遍历的下标进行中序遍历，求出中序遍历中层次遍历下标对应的值，即可求出该树的层次遍历

AC代码

#include 
#include 
using namespace std;
int inorder[1000]; // 中序序列
int levelorder[1000]; // 层次序列
int n;
int k = 0; // 遍历赋值时实现下标移动
// 中序遍历
void inTraveral(int index) {
	if (index >= n) { // 递归出口
		return;
	}
	inTraveral(2 * index + 1); // 遍历左子树
	levelorder[index] = inorder[k++]; // 由于层次遍历和中序遍历值的对应关系，直接赋值即可
	inTraveral(2 * index + 2); // 遍历右子树
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> inorder[i];
	}
    // 得到中序序列
	sort(inorder, inorder + n);
	inTraveral(0); // 进行中序遍历
	for (int i = 0; i < n; i++) { // 输出层次遍历
		if (i != 0) {
			cout << " ";
		}
		cout << levelorder[i];
	} 
	return 0;
}

 更多PAT甲级题目：请访问PAT甲级刷题之路--题目索引+知识点分析（正在进行），感谢支持！