Arbres - Buscant en un arbre de cerca P92765


Statement
 

pdf   zip

thehtml

Feu un programa que primer llegeixi un arbre binari de cerca amb naturals, i que, per a cada natural llegit a continuació, indiqui si aquest es troba o no dins de l’arbre. Un arbre binari és de cerca si, per a cada node, els elements del seu subarbre esquerre són més petits que l’element del node, i els elements del seu subarbre dret són més grans que l’element del node.

Entrada

L’entrada consisteix en la descripció d’un arbre segons s’explica a l’exercici P98436. Per raons històriques que no venen el cas i sobre les quals no valdria la pena malgastar valuos bits, el nombre de nodes interns de l’arbre també es dóna. Podeu ignorar aquest primer enter. Suposeu que l’arbre donat és de cerca. A continuació ve una seqüència de naturals.

Sortida

Per a cada natural donat, el vostre programa ha de retornar un 1 si el natural és a l’arbre o un 0 si no hi és.

Observació

Aquest exercici es podria resoldre ignorant l’estructura de l’arbre, ordenant el vector pel camp valor i fent cerques dicotòmiques. El Jutge no podria detectar aquesta trampa, però això no us serviria per practicar l’ús d’arbres, que és del que es tracta.

Public test cases
  • Input

    10
    180 155 60 -1 80 -1 -1 170 -1 -1 300
    240 -1 -1 400 310 -1 340 -1 -1 -1
    
    60
    180
    400
    310
    160
    0
    500
    

    Output

    60 1
    180 1
    400 1
    310 1
    160 0
    0 0
    500 0
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python