Fisierul respectiv face o parcurgere a arborelui prin referinte descendente, de tip tata. Mai intai spune parintele si apoi copilul.
Programarea dinamica de obicei se formeaza de la coada la capat. Incepi cu cea mai simpla unitate si ajungi dupa aceea la cea mai complexa.
Asta inseamna ca arborele ar trebui parcurs prin referinte ascendente, de la nodurile terminale pana la radacina.
Transformarea din referinte descendente in referinte ascendente ia destul de multe operatii, pentru ca trebuie sa iei terminalele de la cel cu cea mai mica eticheta la cel cu cea mai mare, altfel risti sa faci cicluri in citire(citesti parinte, apoi fiu, apoi acelasi tata, apoi iar fiul initial)
In arborele tau de aici, incepi cu 3, apoi cu 4, 7,8 si apoi il iei pe 6, care devine nod terminal dupa inlaturarea lui 7 si 8.
La final o sa ai doi vectori t si pt(parinte terminal) care o sa arate asa
t:3 4 7 8 6 5 2
pt:2 1 6 6 4 2 1
Odata aflati acesti 2 vectori faci urmatorii pasi per cautare
1) Setezi un vector de cost cu 1(fiecare nod se cunoaste pe el insusi)
2) verifici pentru un nod parinte daca este un succesor al nodului X la care cauti(altfel nu are sens sa faci calcule partiale)
3) incepi sa faci calcule partiale
Fisierul CPP are o gramada de alte functii de le-am mai facut eu comentate pentru diverse teste. Dar oricum, ma tem ca acea transformare din referinte descendente in referinte ascendente o sa faca programul incet.
Oricum, si dimensiunile vectorilor sunt mici, doar de 20, este ceva demonstrativ cam cum s-ar face pornind de la terminale.
