Recorreguts recursius d'un arbre general P66413

Statement

thehtml

Feu un programa que llegeixi la descripció d’un arbre general de naturals i escrigui el seu recorregut en postordre.

Tant en aquest exercici com en la resta d’exercicis d’aquesta secció, si no es diu el contrari la descripció d’un arbre general consisteix en el nombre de nodes n seguit del recorregut en preordre, en el qual al valor de cada node li segueix el seu nombre de fills. Aquest recorregut té doncs 2n 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):

typedef vector<int> VE; struct Node { int valor; VE fill; }; // 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. int arbre(int& j, vector<Node>& v) { int a = j; ++j; int f; cin >> v[a].valor >> f; v[a].fill = VE(f); for (int i = 0; i < f; ++i) v[a].fill[i] = arbre(j, v); return a; } ... int main() { int n; cin >> n; vector<Node> v(n); int j = 0; arbre(j, v); ... }

Cada posició del vector guarda el valor d’un node, així com un vector amb les posicions de tots els seus fills d’esquerra a dreta. La posició de l’arrel de l’arbre és sempre 0.

Entrada

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

Sortida

Escriviu una línia amb el recorregut en postordre de l’arbre general. Cada element ha de sortir precedit d’un espai.

Public test cases

Input

12
7 3  8 0  4 2  3 1  0 1  6 0
5 0  2 4  9 0  1 0  8 0  5 0

Output

 8 6 0 3 5 4 9 1 8 5 2 7

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: C++
User solutions: C++ Python