Em estruturas de dados, as travessias em árvores são algoritmos para percorrer todos os nós de uma árvore. As travessias comuns incluem pré-ordem (raiz-esquerda-direita), em-ordem (esquerda-raiz-direita) e pós-ordem (esquerda-direita-raiz).

Um exemplo básico de travessia em pré-ordem usando busca em profundidade:

struct NoArvore {
    int esq, dir, ancestral;
} arvore[MAX];
void percorrer(int no) {
    cout << arvore[no].valor << ' ';
    if (arvore[no].esq)
        percorrer(arvore[no].esq);
    if (arvore[no].dir)
        percorrer(arvore[no].dir);
}

No problema da Árvore FBI do NOIP2004, a solução pode ser implementada recursivamente sem construir a árvore explicitamente. A abordagem envolve analisar sub-strings para determinar o tipo de cada subárvore.

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

char avaliarSubarvore(string str) {
    if (str.length() > 1) {
        cout << avaliarSubarvore(str.substr(0, str.length() / 2));
        cout << avaliarSubarvore(str.substr(str.length() / 2));
    }
    if (str.find('0') != string::npos && str.find('1') != string::npos) return 'F';
    if (str.find('1') != string::npos) return 'I';
    return 'B';
}

int main() {
    int n;
    string entrada;
    cin >> n >> entrada;
    cout << avaliarSubarvore(entrada) << endl;
}

Uma técnica relacionada é reconstruir uma árvore a partir das travessias em-ordem e pós-ordem. Em uma travessia pós-ordem, o último elemento é a raiz. Isso permite dividir recursivamente as travessias para construir a árvore.

void reconstruir(string inOrd, string postOrd) {
    if (!inOrd.empty()) {
        char raiz = postOrd.back();
        cout << raiz;
        int idx = inOrd.find(raiz);
        reconstruir(inOrd.substr(0, idx), postOrd.substr(0, idx));
        reconstruir(inOrd.substr(idx + 1), postOrd.substr(idx, inOrd.length() - idx - 1));
    }
}

int main() {
    string inOrdem, postOrdem;
    cin >> inOrdem >> postOrdem;
    reconstruir(inOrdem, postOrdem);
}

Para calcualr o número de árvores binárias possíveis dadas as travessias em pré-ordem e pós-ordem, é necessário identificar nós com um único filho. Quando um nó tem apenas um filho, ele multiplica as possibilidades.

int main() {
    string preOrd, postOrd;
    cin >> preOrd >> postOrd;
    int count = 0;
    for (int i = 0; i < preOrd.size() - 1; i++) {
        for (int j = 1; j < postOrd.size(); j++) {
            if (preOrd[i] == postOrd[j] && preOrd[i+1] == postOrd[j-1])
                count++;
        }
    }
    cout << (1 << count) << endl;
}