浙大数据结构慕课课后题(04-树6 Complete Binary Search Tree)
题目要求:
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.
输入规格:
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.
输出规格:
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 0
样例输出:
6 3 8 1 5 7 9 0 2 4
题解:
思路如注释所示,可通过所有测试点。
#include<bits/stdc++.h>
using namespace std;
int num[1005] = {0} ,ans[1005] = {0};int compare(const void*a,const void*b){ //qsort函数的比较规则 return *(int*)a - *(int*)b;
}int GetLeftLength(int N){ //计算左子树数目int H,X,L;H = log2(N+1);X = N - pow(2, H) + 1;X < pow(2, H-1) ? X = X : X = pow(2, H-1);L = pow(2, H-1) -1 + X;return L;
}void solve(int Left, int Right, int TRoot){int n,L,LeftTRoot,RightTRoot;n = Right - Left + 1;if(n == 0) return; //处理长度为0,则说明已经处理完了L = GetLeftLength(n);ans[TRoot] = num[Left + L];LeftTRoot = TRoot * 2 + 1;RightTRoot = LeftTRoot + 1;solve(Left, Left + L - 1, LeftTRoot); //递归处理左子树 solve(Left + L + 1, Right, RightTRoot); //递归处理右子树
}int main(){int N;cin>>N;for(int i = 0; i < N; i++){cin>>num[i]; }qsort(num, N, sizeof(int), compare);solve(0, N-1, 0);for(int i = 0;i < N; i++){cout<<ans[i];if(i != N-1)cout<<" ";}}