Arbres binaris de cerca - Elements comuns P42342


Statement
 

pdf   zip   main.py

thehtml

Feu una funció que, donats dos arbres binaris de cerca de naturals, generi els seus elements comuns en ordre creixent.

Digueu quin és el cost asimptòtic de generar tots els elements comuns de dos arbres binaris de cerca utilitzant el vostre algorisme.

Observacions

  • Descarregueu-vos el fitxer code.py. El programa principal, les estructures de dades, la lectura de l’arbre i l’esquelet de la funció ja se us dónen implementats. No podeu canviar la interfície ni els tipus donats.
  • El programa principal serveix per provar la funció i llegeix p parells d’arbres binars de cerca en preordre (amb valors −1 pels arbres buits) i escriu, per a cada parell, els seus elements comuns en ordre creixent en una línia.
  • No podeu utilitzar llistes, ni conjunts ni diccionaris. Sí que podeu utilitzar funcions auxiliars i generadors.
Public test cases
  • Input

    4
    
    5 3 -1 -1 6 -1 -1
    6 5 -1 -1 9 -1 -1
    
    5 3 -1 -1 7 6 -1 -1 -1
    1 -1 3 -1 5 -1 7 -1 9 -1 -1
    
    5 3 -1 -1 6 -1 -1
    -1
    
    666 -1 -1
    666 -1 -1
    

    Output

    5 6
    3 5 7
    
    666
    
  • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python