您的位置: 首页  >  IT文章  >  1365：FBI树(fbi)

1365：FBI树(fbi)

分类: IT文章 • 2022-08-29 23:45:18

【题目描述】

我们可以把由“F串。

FBI树是一种二叉树，它的结点类型也包括T，递归的构造方法如下：

S的类型相同；

若串T2。

现在给定一个长度为01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。

【输入】

第一行是一个整数01”串。

【输出】

一行，这一行只包含一个字符串，即FBI树的后序遍历序列。

【输入样例】

3
10001011

【输出样例】

IBFBBBFIBFIIIFF

【提示】

1365：FBI树(fbi)

对于40%的数据，N≤2；

对于100%的数据，N≤10。

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char value;
    Node *left, *right;
};

char GetValue(const string &s, int index, int limit)
{
    int zero = 0, one = 0;
    for (int i = index; i < limit; i++) {
        if (s[i] == '0') {
            zero += 1;
        } else if (s[i] == '1') {
            one += 1;
        }
    }
    if (zero > 0 && one > 0) {
        return 'F'; // 01
    } else if (zero > 0) {
        return 'B'; // 0
    } else if (one > 0) {
        return 'I'; // 1
    } else {
        return 'E'; // error
    }
}

Node *CreateTree(const string &s, int left, int right)
{
    if (left < 0 || left >= right) {
        return NULL;
    } else {
        Node *root = new Node;
        root->value = GetValue(s, left, right);
        // cout << left << "," << right << "=" << root->value << endl;
        root->left = root->right = NULL;
        if (right - left > 1) { // 多于1个
            int mid = (left + right) / 2;
            root->left = CreateTree(s, left, mid);
            root->right = CreateTree(s, mid, right);
        }
        return root;
    }
}

string PreOrder(Node *root)
{
    string s;
    if (root != NULL) {
        s.push_back(root->value);
        s += PreOrder(root->left);
        s += PreOrder(root->right);
    }
    return s;
}

string InOrder(Node *root)
{
    string s;
    if (root != NULL) {
        s += InOrder(root->left);
        s.push_back(root->value);
        s += InOrder(root->right);
    }
    return s;
}

string PostOrder(Node *root)
{
    string s;
    if (root != NULL) {
        s += PostOrder(root->left);
        s += PostOrder(root->right);
        s.push_back(root->value);
    }
    return s;
}

int main()
{
    // freopen("1.txt", "r", stdin);
    int n = 3;
    string s = "10001011";
    cin >> n >> s;
    Node *root = CreateTree(s, 0, s.size());
    // cout << PreOrder(root) << endl;
    // cout << InOrder(root) << endl;
    cout << PostOrder(root) << endl;
    return 0;
}

相关推荐