Recorreguts recursius d'un arbre P57669

Feu un programa que llegeixi la descripció d’un arbre binari de naturals i escrigui els seus recorreguts en postordre i inordre.

Tant en aquest exercici com en la resta d’exercicis d’aquesta secció, si no es diu el contrari la descripció d’un arbre consisteix en el nombre de nodes $n$ seguit del recorregut en preordre, el qual inclou les fulles marcades amb un -1. Aquest recorregut té doncs $2n + 1$ elements.

(Per veure un exemple amb l’arbre corresponent a l’exemple d’entrada-sortida, consulteu la versió pdf o ps d’aquest enunciat.)

Per resoldre tant aquest exercici com la majoria d’aquesta secció, us caldrà emmagatzemar l’arbre en un vector. Feu-ho usant aquest codi (lleugerament modificat si cal):

    struct Node {
        int valor;
        int esq, dre;
    };

    // Llegeix un arbre i el desa a un tros del vector v començant a la posicio j.
    // Modifica la variable j perque apunti a la seguent posicio lliure de v.
    // Retorna la posicio dins de v de l'arrel del (sub)arbre llegit (o -1).
    int arbre(int& j, vector<Node>& v) {
        int x;
        cin >> x;
        if (x == -1) return -1;

        int a = j;
        ++j;
        v[a].valor = x;
        v[a].esq = arbre(j, v);
        v[a].dre = arbre(j, v);
        return a;
    }

    ...

    int main() {
        int n;
        cin >> n;
        vector<Node> v(n);
        int j = 0;
        int a = arbre(j, v);
        ...
    }

Amb l’arbre de l’exemple, el contingut final del vector @v@ seria

Fixeu-vos que cada posició del vector guarda el valor d’un node, així com la posició del seu fill esquerre i del seu fill dret. El valor -1 s’usa per indicar els arbres buits. La variable @a@ del programa principal és la posició de l’arrel de l’arbre, i val -1 si l’arbre és buit, i 0 si no ho és.

Entrada

L’entrada consisteix en la descripció d’un arbre binari de naturals.

Sortida

Escriviu dues línies, amb els recorreguts en postordre i inordre de l’arbre. Cada element ha de sortir precedit d’un espai.