Arbre de xifres

Implementeu una funció RECURSIVA que, donat un arbre binari no buit de
nombres naturals i un dígit (0,1,2,3,4,5,6,7,8 o 9), retorna true si
qualsevol dels nodes de l’arbre conté el dígit.

Aquesta és la capçalera de la funció:

    bool treeContainsDigit(BinaryTree<int>& t, int d);

Aquesta funció principal ha de fer servir una funció auxiliar ITERATIVA,
que també cal que implementeu, per comprovar si un nombre natural conté
un dígit. Tingueu en compte que no es pot fer servir cap funció que
converteixi el nombre a cadena.

La funció auxiliar ha de tenir la següent capçalera:

    bool numberContainsDigit(int n, int d);

Aquí tenim un exemple de paràmetres d’entrada de la funció principal i
la corresponent sortida, que és true degut a que l’arbre conté la xifra
7 dins del node 17:

    d: 7    
    t:           5
                 |
          ------- -------
         |               |
         3               4
         |               |
     ---- ----       ----
    |         |     |
    2         5     17

    =>

    true

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que
haureu d’utilitzar per a compilar:
Makefile, program.cpp, BinaryTree.hpp, digitsTree.hpp. Us falta crear el
fitxer digitsTree.cpp amb els corresponents includes i implementar-hi
les dues funcions anteriors. Quan pugeu la vostra solució al jutge,
només cal que pugeu un tar construït així:

    tar cf solution.tar digitsTree.cpp

Entrada

La primera linia de l’entrada conté el dígit que es busca a tots els
arbres. La segona descriu el format en el que es descriuen els arbres, o
bé INLINEFORMAT o bé VISUALFORMAT. Després venen un nombre arbitrari de
casos. Cada cas consisteix en una descripció d’un arbre binari no buit
de nombres naturals majors o igual a zero. Fixeu-vos en que el programa
que us oferim ja s’encarrega de llegir aquestes entrades. Només cal que
implementeu les funcions abans esmentades.

Sortida

Per a cada cas, la sortida és SI o NO. Fixeu-vos en que el programa que
us oferim ja s’encarrega d’escriure aquest resultat. Només cal que
implementeu les funcions abans esmentades.

Observació

- Les funcions/accions que implementis han de treballar només amb arbres
  binaris i han de tenir les corresponents PRE i POST.

- En les crides recursives, inclou la hipòtesi d’inducció, és a dir una
  explicació del que es compleix després de la crida, i també la funció
  de fita/decreixement.

- En els bucles inclou l’invariant del bucle i la funció de fita.

- Finalment, afegeix un comentari al final de tot del teu codi amb la
  justificació informal de la correctesa de la funció recursiva.

Informació del problema

Autoria: Alfonso da Silva

Generació: 2026-01-25T20:33:57.595Z

© Jutge.org, 2006–2026.
https://jutge.org
