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
题意:给出n个节点,我们需要把它放在完全二叉树里面,并且保持二叉搜索树的性质,之后层次遍历输出这颗完全二叉搜索树的所有节点
思路:我们把给定的节点排好序放在一个数组里,因为我们要把这些书放在一颗完全二叉树里面,所以给我们n的节点,我们肯定可以求出左子树有多少个,这样就知道这个二叉树的根了,及数组里面前n个是左子树,n+1是根节点,因为它要满足搜索二叉树的性质,即左子树的节点小于跟节点,之后便是递归求根节点的下面的左子树的根节点和右子树的根节点,递归就可以完成,这一题花了我大约两个多小时,主要还是递归那个函数不会写,收获很多,这题我肯定要写个总结了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<iostream> #include<algorithm> #include<cmath> using namespace std; int tree[1001]; int value[1001]; int k=0;//k为tree的数组下标 //思路理一遍,我们先把读入的数据排好放在一个数组里,接着递归去找根节点。。。 int seekroot(int n) { //给二叉树的n个节点,返回其最大左子树的个数 int i; for ( i = 1; n >=pow(2, i) - 1; i++) { } if((n-(pow(2,i-1)-1))<=pow(2,i-2)) return (pow(2, i - 1) - 1) / 2 + (n - pow(2, i - 1) + 1); else return (pow(2, i - 1) - 1) / 2 + pow(2, i - 2); } void solve(int left ,int right ,int root) { int leftroot, rightroot; int n = right - left + 1; if (n == 0) return; int l = seekroot(n);//偏移量 tree[root] = value[left + l]; leftroot = root * 2 + 1; rightroot = leftroot + 1; solve(left, left + l - 1, leftroot); solve(left + l + 1, right, rightroot); } int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> value[i]; sort(value, value + n); solve(0, n - 1, 0); //太特么坑的我头破血流。。这个n变了,最后变成了0,找了老半天的bug,因为n我设为了全局变量 bool flag=0; for (int i = 0; i < n; i++) { if(flag) cout<<" "; cout << tree[i] ; flag=1; } } |