更多PAT甲级详解--acking-you.github.io

题目


OJ平台

题目大意

文章文字那么长，主要就掌握三点：

  1. 输入给到二叉搜索树的树形结构。
  2. 给出一堆数据填入这些结点中，使其满足二叉搜索树。
  3. 按层序遍历输出二叉搜索树的数据。
  • 好了，我们清楚了这三点后，我们最关键的就在于怎么把这棵树填充成二叉搜索树？

由于二叉搜索树的性质，它的中序遍历正好就是从小到大的序列，诶！这不正好可以利用这个性质来赋值吗？我们直接把给的数据排序，然后根据中序遍历的顺序进行赋值即可！

代码详解

输入输出前的准备

所需变量：

int N;
int* nums; //用于动态分配掌握全局
int tot = 0;//游标用于赋值
queue<int>Q;//用于层序遍历输出答案
struct node { //每个树的结点(其实也可以设为动态
    int val, l, r;
    node(): val(0), l(-1), r(-1) {}
} Treenode[101];

输入的处理

Input函数

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) { //由图中可知，这个左右子树编号正好是根据这个序号来给的
        cin >> Treenode[i].l >> Treenode[i].r;
    }
    nums = new int[N];//申请内存存储每个结点的值
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    sort(nums, nums + N); //由于我们已经知道二叉搜索树的树形结构，而它的值是遵循中序遍历递增的规律的
}

输出的处理

//@中序赋值
void Inorder(int node) {
    if (node == -1)
        return;
    Inorder(Treenode[node].l);//左子树
    Treenode[node].val = nums[tot++];
    Inorder(Treenode[node].r);//右子树
}

//@BFS打印
void print() {
    Q.push(0);
    while (!Q.empty()) {
        int node = Q.front(); Q.pop();
        if (Treenode[node].l != -1)
            Q.push(Treenode[node].l);
        if (Treenode[node].r != -1)
            Q.push(Treenode[node].r);
        cout << Treenode[node].val;
        if (!Q.empty())
            cout << ' ';
    }
}

整合代码提交

效率还行！

#include <bits/stdc++.h>
using namespace std;
//利用二叉搜索树的性质--中序遍历的序列是递增序列
int N;
int *nums;
int tot = 0;//游标用于赋值
queue<int> Q;//用于最后层序遍历输出答案
struct node {
    int val, l, r;
    node() : val(0), l(-1), r(-1) {}
} Treenode[101];

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) {//由图中可知，这个左右子树编号正好是根据这个序号来给的
        cin >> Treenode[i].l >> Treenode[i].r;
    }
    nums = new int[N];//申请内存存储每个结点的值
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    sort(nums, nums + N);//由于我们已经知道二叉搜索树的树形结构，而它的值是遵循中序遍历递增的规律的
}

//@中序赋值
void Inorder(int node) {
    if (node == -1)
        return;
    Inorder(Treenode[node].l);//左子树
    Treenode[node].val = nums[tot++];
    Inorder(Treenode[node].r);//右子树
}

//@BFS打印
void print() {
    Q.push(0);
    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();
        if (Treenode[node].l != -1)
            Q.push(Treenode[node].l);
        if (Treenode[node].r != -1)
            Q.push(Treenode[node].r);
        cout << Treenode[node].val;
        if (!Q.empty())
            cout << ' ';
    }
}

int main() {
    Input();
    Inorder(0);
    print();
    return 0;
}