PTA甲级 1064 Complete Binary Search Tree (30分)

强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬

本文由参考于柳神博客写成

柳神的CSDN博客,这个可以搜索文章

柳神的个人博客,这个没有广告,但是不能搜索

还有就是非常非常有用的 算法笔记 全名是

算法笔记  上级训练实战指南		//这本都是PTA的题解
算法笔记

PS 今天也要加油鸭

题目原文

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

生词如下:

没有,都看懂了.

PS:我自己把自己气的脑溢血了.

二叉树的性质都没有用上.

题目大意:

给你一个序列.要你求CBT的二叉树

CBT就是完全二叉树

思路如下:

二叉树的性质是.中序遍历的结果一定是有序的.

我们只有把序列.排序一下.再中序遍历一遍.得到的二叉树就是完全二叉树了

代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int Data[1010], CBT[1010],index=0,n=0;
void inOrder(int root) {
	if (root > n)	return;
	inOrder(root * 2);
	CBT[root] = Data[index++];
	inOrder(root * 2 + 1);
}
int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)	scanf("%d", &Data[i]);
	sort(Data, Data+n);				//进行排序
	inOrder(1);
	for (int i = 1; i < n; ++i) {
		printf("%d ", CBT[i]);
	}
	printf("%d", CBT[n]);
	return 0;
}

我真的太菜了

如果这篇文章对你有张帮助的话,可以用你高贵的小手给我点一个免费的赞吗

相信我，你也能变成光.

如果你有任何建议,或者是发现了我的错误,欢迎评论留言指出.