I2R06. Pares i fills P93115


Statement
 

pdf   zip

thehtml

Feu un programa que llegeixi un arbre binari de nombres enters positius, tots diferents, i que escrigui totes les seves relacions pare–fill. Primer, cal escriure aquestes relacions en l’ordre en què es llegeixen. Després, cal fer-ho de petit a gran.

Entrada

L’entrada consisteix en el recorregut en preordre d’un arbre binari, el qual inclou les fulles marcades amb un -1. No es dóna el nombre de nodes, ja que no cal guardar els arbres a cap vector per resoldre aquest problema. Tots els nombres són diferents.

(Per veure l’arbre corresponent al primer exemple d’entrada-sortida, consulteu la versió pdf o ps d’aquest enunciat.)

Sortida

Primer, escriviu les relacions pare–fill en l’ordre en què es llegeixen, una per línia. Després, cal escriure una lína amb 5 guions. Finalment, escriviu les relacions pare–fill de petit a gran, també una per línia.

Public test cases
  • Input

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

    Output

    3 0
    0 7
    7 4
    0 2
    3 5
    5 9
    5 8
    8 6
    6 1
    -----
    0 2
    0 7
    3 0
    3 5
    5 8
    5 9
    6 1
    7 4
    8 6
    
  • Input

    -1
    

    Output

    -----
    
  • Input

    9 6 -1 -1 3 -1 -1
    

    Output

    9 6
    9 3
    -----
    9 3
    9 6
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++