Skip to content

L3-010 是否完全二叉搜索树

Statement

Metadata

  • 作者: 陈越
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

输入格式

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

输出格式

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。

输入样例1 

9
38 45 42 24 58 30 67 12 51

输出样例1 

38 45 24 58 42 30 12 67 51
YES

输入样例2 

8
38 24 12 45 58 67 42 51

输出样例2 

38 45 24 58 42 12 67 51
NO

Tutorial

思路：

  • 因为是完全二叉搜索树
  • 可以用数字建树的方式, 然后遍历一遍这个数字, 就是层序遍历
  • 遍历的过程中, 需要判断一个中间的位置, 是否有一个位置是没有结点的
  • 如果有就不是完全二叉搜索树
  • 要注意这个树的定义是左子树键值比右子树键值大

Solution

#include <ctype.h>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define CLR(a) memset(a, 0, sizeof(a))
#define pb push_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;

const double PI = 3.14159265358979323846264338327;
const double E = exp(1);
const double eps = 1e-30;

const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int MOD = 1e9 + 7;

int arr[maxn];

int n, l;

int flag;

vector<int> ans;

void Build() {
    string temp = "";
    CLR(arr);
    int num;
    scanf("%d", &arr[1]);
    int len = 1;
    for (int i = 1; i < n; i++) {
        scanf("%d", &num);
        for (int j = 1;;) {
            if (arr[j] != 0) {
                if (num < arr[j])
                    j = j * 2 + 1;
                else
                    j *= 2;
            } else {
                arr[j] = num;
                if (j > len)
                    len = j;
                break;
            }
        }
    }
    for (int i = 1; i <= len; i++) {
        if (arr[i])
            ans.pb(arr[i]);
        else
            flag = 0;
    }
}

int main() {
    scanf("%d", &n);
    flag = 1;
    Build();
    vector<int>::iterator it;
    for (it = ans.begin(); it != ans.end(); it++) {
        if (it != ans.begin())
            printf(" ");
        printf("%d", (*it));
    }
    printf("\n");
    if (flag)
        printf("YES\n");
    else
        printf("NO\n");
}
Last update: May 4, 2022
Back to top