更多PAT甲級詳解--acking-you.github.io

題目

OJ平臺

題目大意

文章文字那么長，主要就掌握三點：

1. 輸入給到二叉搜索樹的樹形結(jié)構(gòu)。
2. 給出一堆數(shù)據(jù)填入這些結(jié)點中，使其滿足二叉搜索樹。
3. 按層序遍歷輸出二叉搜索樹的數(shù)據(jù)。

• 好了，我們清楚了這三點后，我們最關(guān)鍵的就在于怎么把這棵樹填充成二叉搜索樹？

由于二叉搜索樹的性質(zhì)，它的中序遍歷正好就是從小到大的序列，誒！這不正好可以利用這個性質(zhì)來賦值嗎？我們直接把給的數(shù)據(jù)排序，然后根據(jù)中序遍歷的順序進行賦值即可！

代碼詳解

輸入輸出前的準備

所需變量：

int N;
int* nums; //用于動態(tài)分配掌握全局
int tot = 0;//游標用于賦值
queue<int>Q;//用于層序遍歷輸出答案
struct node { //每個樹的結(jié)點(其實也可以設(shè)為動態(tài)
    int val, l, r;
    node(): val(0), l(-1), r(-1) {}
} Treenode[101];

輸入的處理

Input函數(shù)

//@輸入處理
void Input() {
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) { //由圖中可知，這個左右子樹編號正好是根據(jù)這個序號來給的
        cin >> Treenode[i].l >> Treenode[i].r;
    }
    nums = new int[N];//申請內(nèi)存存儲每個結(jié)點的值
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    sort(nums, nums + N); //由于我們已經(jīng)知道二叉搜索樹的樹形結(jié)構(gòu)，而它的值是遵循中序遍歷遞增的規(guī)律的
}

輸出的處理

//@中序賦值
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;
//利用二叉搜索樹的性質(zhì)--中序遍歷的序列是遞增序列
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++) {//由圖中可知，這個左右子樹編號正好是根據(jù)這個序號來給的
        cin >> Treenode[i].l >> Treenode[i].r;
    }
    nums = new int[N];//申請內(nèi)存存儲每個結(jié)點的值
    for (int i = 0; i < N; ++i) {
        cin >> nums[i];
    }
    sort(nums, nums + N);//由于我們已經(jīng)知道二叉搜索樹的樹形結(jié)構(gòu)，而它的值是遵循中序遍歷遞增的規(guī)律的
}

//@中序賦值
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;
}