数据库查询系统压缩-OJ测试

Question

数据库查询系统压缩

时间限制: 1000 ms
内存限制: 4096 KB
问题描述
某数据库为提升搜索效率，对某一整型字段构建二叉搜索树(BST)。每个结点包含两个数据信息：1）结点的数据；2）该结点子树的元素数目。为了压缩搜索树规模，该数据库为每个结点增加一个字段，该字段用于存储中序遍历时在访问该结点之前访问的结点数据。在该改进下，被存储的结点如果为叶子结点，该结点在新树中将被删除，以提高存储效率。如果一个叶子结点无中序后继，则无需删除。
 
给定该BST的先序遍历（第二个字段未给出），请编写程序，输出经过压缩后新BST的先序遍历结果。  

输入格式
输入共两行：
第一行为一个int数据n，表示该BST的总结点个数。1<=n<=100000；
第二行为n个int数据，为该BST的先序遍历结果（保证顺序是正确的，并保证数据两两不同）。 每个数据的范围：0<=x<=1*107。
输出格式
输出共一行：
第一行为新BST的先序遍历结果，依序输出结点数据以及保存的其他结点数据（若没有则输出字符-）
输入样例
7
6 4 2 5 9 7 8
输出样例
6 5 4 2 9 8 7 -
提示

1. 需要从先序遍历构建二叉树，并对二叉树进行压缩。  
2. 【具体存储规则】题目描述等价于如下表述：对任意结点v：(1) 如果其有左子树，则存储其左子树的最大值，保留该结点；（2）如果没有左子树但有右子树，则不存储任何值，保留该结点；（3）否则（为叶子结点时），如果有中序后继，则可以删除，反之则不存储任何值，保留该结点。
   【举例】一些结点可能并未被删除，但你仍需将其记录在中序遍历中下一个结点的第二个字段上（对应规则1）。下面的例子中，尽管左图中结点(3,1)没有被删除，但是为了充分利用已经开辟的存储空间，其父结点仍需存储该节点的值。  

 
 
3. 注意不要输出多余空格。
 
4. 个别输入样例需要在压缩二叉树时具有O(1)的空间复杂度，请搜索相关算法实现

Answer 1

引自强大而免费的微信小程序：皆我工具箱。
​

思路：
根据题目提供的存储规则，对于每个结点，如果有左子树，则存储其左子树的最大值；如果没有左子树但有右子树，则不存储任何值；否则为叶子结点时，如果有中序后继，则可以删除，反之不存储任何值。

首先构建二叉搜索树，根据给定的先序遍历结果。
然后对每个结点进行压缩处理，处理规则见上述。

具体步骤如下：

1. 读取输入，得到BST的总结点个数n和先序遍历结果preorder。
2. 创建一个结点类Node，包含数据value、子树元素数目count、中序遍历前驱predecessor，以及左右子结点left和right。
3. 定义一个递归函数buildBST，构建二叉搜索树。在buildBST中，如果preorder为空，则返回空结点；否则，创建一个新的结点，将第一个元素作为结点的数据。根据上述存储规则，如果preorder的第二个元素pre大于当前节点的value，则preorder的第一个元素是当前节点的左子树的最大值，否则没有左子树。递归地构建左子树和右子树。
4. 构建完毕后，根据题目要求输出经过压缩后新BST的先序遍历结果。可以采用先序遍历的方式遍历树，在访问每个结点时输出其数据value和前驱结点的数据predecessor。注意，如果一个结点既没有左子树也没有右子树（即叶子结点），并且没有中序后继，则前驱结点的数据predecessor为"-"，否则为左子树的最大值。

具体实现见下面的代码：

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int value;
    int count;
    int predecessor;
    Node* left;
    Node* right;
    Node(int v): value(v), count(0), predecessor(-1), left(nullptr), right(nullptr) {}
};

Node* buildBST(vector<int>& preorder, int& idx) {
    if (idx >= preorder.size()) {
        return nullptr;
    }
    int value = preorder[idx];
    Node* node = new Node(value);
    idx++;
    if (idx < preorder.size() && preorder[idx] > value) {
        node->predecessor = preorder[idx];
        node->left = buildBST(preorder, idx);  
    } else {
        node->left = nullptr;
    }
    node->right = buildBST(preorder, idx);
    return node;
}

void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->value;
    if (root->predecessor != -1) {
        cout << " " << root->predecessor;
    } else if (root->left == nullptr && root->right == nullptr) {
        cout << " -";
    }
    cout << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    int n;
    cin >> n;
    vector<int> preorder(n);
    for (int i = 0; i < n; i++) {
        cin >> preorder[i];
    }
    int idx = 0;
    Node* root = buildBST(preorder, idx);
    preorderTraversal(root);
    return 0;
}