Reconstruint arbres de cerca P36853


Statement
 

pdf   zip

thehtml

En l’exercici es descriu un arbre binari de cerca amb el seu recorregut en preordre, el qual inclou un -1 per a cada fulla. Però, de fet, no cal incloure els -1’s en el preordre d’un arbre de cerca per poder reconstruir-lo.

Feu un programa que llegeixi una seqüència d’arbres binaris de cerca descrits amb els seus recorreguts en preordre sense -1’s. Per a cada arbre, cal escriure el seu recorregut en postordre.

Entrada

L’entrada consisteix en una seqüència de descripcions d’arbres binaris segons s’explica a l’exercici , amb una excepció: S’ometen els -1’s corresponents a les fulles. Suposeu que els arbres són de cerca i que els seus elements són naturals.

Sortida

Per a cada arbre de l’entrada, escriviu una línia amb el recorregut en postordre de l’arbre. Cada element ha de sortir precedit d’un espai.

Public test cases
  • Input

    10
    180 155 60 80 170 300 240 400 310 340
    
    3
    30 20 10
    

    Output

     80 60 170 155 240 340 310 400 300 180
     10 20 30
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    Python