Question

Intr-un arbore cu 10 noduri, numerotate de la 1 la 10, gradul fiecarui nod este maximum 4. Daca arborele este reprezentat prin vectorul de "tati" (x,0,1,1,2,1,8,2,2,2), care sunt valorile posibile ale lui x?

Answer 1

Pentru a intelege mai usor vectorul de tati, se poate face o reprezentare, in care se trec si indici, pentru a vedea care sunt fii unui nod.

$\left[\begin{array}{cccccccccc}x&0&1&1&2&1&8&2&2&2\\1&2&3&4&5&6&7&8&9&10\end{array}\right]$

Din vector ne dam seama ca nodul 2 este radacina arborelui, si are patru copii:5,8,9,10, astfel nu poate fi si parintele lui 1.Nodul care mai are un copil este 8, avand ca si copil pe 7. Varfurile 3,4 si 6 nu pot fii noduri parinte pentru 1 deoarece 1 este parintele lor, astfel nodurile care ar putea fi parintii lui 1 sunt:5,8,9,7 si 10.