Question

Care sunt nodurile care au exact 2 descendenţi directi pentru un arbore cu rădăcină, cu
7 noduri, numerotate de la 1 la 7, dat de vectorul de ”taţi”: (3,3,0,1,2,2,4)?

Cum pot face o problema de genul acesta fara sa mai desenez efectiv arborele ? Va rog sa explicati !

Answer 1

Raspuns : 2 si 3

Explicatie :  

Pentru a determina nodurile care au exact 2 descendenti directi numaram valorile care apar de doua ori in vectorul de tati

Spre exemplu, nodul 3 apare de doua ori (deci are doi descendenti directi).

Observam ca nodul 2 apare si el de doua ori (are doi descendenti directi).

Generalizare

Daca un o valoare apare de n ori intr-un vector de tati atunci nodul corespunzator valorii respective are n descendenti.

Spre exemplu, in acest arbore :

- Nodurile 1,4 au un descendent direct (apar o singura data in vectorul de tati)

- Nodurile 7,6,5 nu au descendenti (nu apar niciodata in vectorul de tati). Acestea se mai numesc si frunze. Deci frunzele sunt nodurile care nu apar in vectorul de tati.