Recursive traversal of a general tree P66413


Statement
 

pdf   zip

html

Write a program that reads the description of a general tree of natural numbers and prints its postorder traversal.

In this exercise as well as in the rest of exercises of this section, unless the contrary is said the description of a general tree consists of the number of nodes n followed by the pre-order traversal, in which the value of each node is followed by its number of children. This traversal has 2n elements.

(To see an instance with the tree corresponding to the input-output instance, consult the pdf or ps version of this wording.)

To solve this exercixe as well as most of the exercises of this section, you will need to store the tree in a vector. Do it using this code (slightly modified if it is necessary):

typedef vector<int> VE; struct Node { int value; VE children; }; // Reads a tree and stores a part of the vector v starting at the position j. // Modifies the variable j in order to indicates the following free position of v. // Returns the position in c of the root of the read (sub)tree. int tree(int& j, vector<Node>& v) { int a = j; ++j; int f; cin >> v[a].value >> f; v[a].children = VE(f); for (int i = 0; i < f; ++i) v[a].children[i] = tree(j, v); return a; } ... int main() { int n; cin >> n; vector<Node> v(n); int j = 0; tree(j, v); ... }

Each position of the vector stores the value of a node, and the vector with the positions of all its children from the left to the right. The position of the tree root is always 0.

Input

Input consists of the description of a general tree of natural numbers.

Output

Your program must print a line with the postorder traversal of the general tree. Each element must be preceded by a space.

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
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python