Because of necessary software maintenance, Jutge.org may not work well on the afternoons of the 20th and 21th of april.

Recorreguts recursius d'un arbre P57669

Statement

html

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ó	0	1	2	3	4	5	6	7	8	9
@v.valor@	3	0	7	4	2	5	4	7	6	1
@v.esq@	1	2	-1	-1	-1	6	-1	8	-1	-1
@v.dre@	5	4	3	-1	-1	7	-1	-1	9	-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