Recorreguts recursius d'un arbre P57669


Statement
 

pdf   zip

thehtml

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

||
posició0123456789
v.valor3074254761
v.esq12-1-1-16-18-1-1
v.dre543-1-17-1-19-1
||

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.

Public test cases
  • Input

    10
    3 0 7 -1 4 -1 -1 2 -1 -1 5
    4 -1 -1 7 6 -1 1 -1 -1 -1
    

    Output

     4 7 2 0 4 1 6 7 5 3
     7 4 0 2 3 4 5 6 1 7
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++ Python