Reading Addition Trees X91812


Statement
 

pdf   zip

html

Addition trees are binary trees where only the leaves can store arbitrary numbers (float’s in our case). Values associated to internal nodes get computed according to a fixed rule: the sum of the values associated to the subtrees (thus, in some applications, it may not be necessary to actually store the value). Note that there are no empty addition trees.

Addition trees are the main combinatorial structure behind Huffman codes (see https://jutge.org/problems/P62266 for more). They are also a very close relative of the Product Trees of https://jutge.org/problems/P30012.

We describe addition trees in preorder as indicated below. Write a program that reads such a description and prints the preorder, inorder and postorder traversals of the tree read. (The pdf version of the statement of https://jutge.org/problems/P62266 graphically depicts one of the public test trees below.)

Input

Addition trees are described here in preorder as follows: for leaves, the corresponding float is given, whereas for internal nodes only the character ’+’ is written. All these tokens are space-separated and might come distributed arbitrarily along several lines.

Output

Three sequences of floats, as obtained by preorder, inorder, and postorder of the tree described by the input. Print each float with 4 decimal places.

Public test cases

  • Input

    + + 5 + 2 3 90

    Output

    100.0000 10.0000 5.0000 5.0000 2.0000 3.0000 90.0000 
5.0000 10.0000 2.0000 5.0000 3.0000 100.0000 90.0000 
5.0000 2.0000 3.0000 5.0000 10.0000 90.0000 100.0000

  • Input

    + 90 + + 2 3 5

    Output

    100.0000 90.0000 10.0000 5.0000 2.0000 3.0000 5.0000 
90.0000 100.0000 2.0000 5.0000 3.0000 10.0000 5.0000 
90.0000 2.0000 3.0000 5.0000 5.0000 10.0000 100.0000

  • Input

    + + + 10.2 10.6 21 
+ + 11.6 12.7 + + 6.3 8.6 19.0

    Output

    100.0000 41.8000 20.8000 10.2000 10.6000 21.0000 58.2000 24.3000 11.6000 12.7000 33.9000 14.9000 6.3000 8.6000 19.0000 
10.2000 20.8000 10.6000 41.8000 21.0000 100.0000 11.6000 24.3000 12.7000 58.2000 6.3000 14.9000 8.6000 33.9000 19.0000 
10.2000 10.6000 20.8000 21.0000 41.8000 11.6000 12.7000 24.3000 6.3000 8.6000 14.9000 19.0000 33.9000 58.2000 100.0000
    • Information
    Author
    José Luis Balcázar
    Language
    English
    Official solutions
    Python
    User solutions
    Python