7-58 是否完全二叉搜索树 (30 分)
将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。
输入格式:
输入第一行给出一个不超过20的正整数N;第二行给出N个互不相同的正整数,其间以空格分隔。
输出格式:
将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果,数字间以1个空格分隔,行的首尾不得有多余空格。第二行输出YES,如果该树是完全二叉树;否则输出NO。
输入样例1:
1. 9 2. 38 45 42 24 58 30 67 12 51
输出样例1:
1. 38 45 24 58 42 30 12 67 51 2. YES
输入样例2:
1. 8 2. 38 24 12 45 58 67 42 51
输出样例2:
1. 38 45 24 58 42 12 67 51 2. NO
#include<bits/stdc++.h> using namespace std; const int N = 110; int a[N], maxn; void build(int idx, int x) { if (!a[idx]) { a[idx] = x; maxn = max(maxn, idx); return; } if (x > a[idx]) add(2 * idx, x); else add(2 * idx + 1, x); } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { int x; cin >> x; build(1, x); } int f = 0; for (int i = 1; i <= maxn; i++) { if (a[i]) { if (f++) cout << ' '; cout << a[i]; } } cout << endl << (maxn == n ? "YES" : "NO") << endl; return 0; }