Nelamurire arbori!

[•GEORGE-S]

Salutări, sunt nou si as dori sa ma ajutati si pe mine, cu cateva informatii legate de arbori.

Tin sa mentionez, inainte de toate, ca nu am facut arborii la clasa, fiind la profilul real, specializarea matematica-informatica neintensiv.

Doresc, daca se poate, sa-mi spuneti si mie urmatoarele notiuni si cum le pot identifica intr-un arbore: descendent, descendent direct/fiu, ascendent, ascendent direct/parinte. Si nu in ultimul rand, cum pot face lista "de descendeti". Multumesc anticipat!

[•Owlree]

La ce te referi mai exact când zici identifica?

Un arbore este un graf aciclic și conex în care ne alegem un nod pe post rădăcină. Doarece avem un graf aciclic conex, există un unic drum elementar între oricare două noduri. Dacă vrem, putem să și orientăm graful dinspre rădăcină înspre exterior (înspre frunze).

• descdendent - un nod A se numește descendent al unui nod B dacă și numai dacă A este diferit de B și drumul elementar de la rădăcină la A îl conține pe B
• descdendent direct - un nod A se numește descedendent direct al unui nod B dacă și numai dacă îi este descendent și adiacent
• ascendent - un nod B se numește ascendent al unui nod A dacă și numai dacă A este descendent al lui B
• ascendent direct - un nod B se numește ascendent direct al unui nod A dacă și numai dacă îi este ascdendent și adiacent

Intuitiv, noțiunile de desendent și ascendent sunt legate una de alta, un nod A nu-i poate fi descendent unui nod B dacă nodul B nu îi este ascendent lui A. Și mai intuitiv, ascendenții unui nod un aceia pe care îi găsești plimbându-te de la nodul tău în sus, înspre rădăcină, deci nodurile care sunt practic deasupra nodului respectiv. Descendenții, în mod analog, sunt aceia pe care îi găsești dedesubt.


(imagine wikipedia)

Pe exemplul din figura de mai sus o să mă refer la nodul cu valoarea x ca nodul x, deoarece valorile sunt unice înafară de valoarea 2, pe care nu o să o folosesc ca să nu dăm în ambiguitate. Deci, avem că, spre exemplu, 11 este descendent al lui 7 (avem drumul elementar 2 7 6 11). Evident, 7 este ascendent al lui 11. Un descdendent direct al lui 7 ar fi 6 (de ce?). Evident, 7 este ascendent direct al lui 6 (iar, de ce?).

Mă îndoiesc că ce-am zis eu aici a făcut prea multă lumină. Dacă nu stăpânești bine noțiunile, recomandarea mea este să îți desenezi chiar tu câțiva arbori și să îți faci câteva exemple pe ei.

Pentru lista de descdenenți, dacă vrei un exemplu în C/C++, depinde cum memorezi arborele. Dacă ai putea da ceva mai multe detalii ar fi super.

[•GEORGE-S]

In primul rand, iti multumeac pentru atentia acordata.

Ideea cu "identifica", faceam referire la notiunile acestora(ce inseamna?) Si cum poti sa-ti dai seama in arbore, care sunt acestia.

Cat de cat, m-ai luminat putin. Dar mai am o singura intrebare, spre exemplu, 5 poate fi descendent al lui 7, si 7 ascendent al lui 5? (2 7 6 5)

La lista de descendenti, ma refeream, cum pot fi scrisi pe o foaia (vreau sa dau bacul la informarica). La fel cum este lista de adiacenta, ca la grafurile neorientate si orientate.

1-4-2-3 (graf neorientat)

L1: 4
L2: 3, 4
L3: 2
L4: 1, 2

Sper sa fi fost pe inteles!

[•Owlree]

Cat de cat, m-ai luminat putin. Dar mai am o singura intrebare, spre exemplu, 5 poate fi descendent al lui 7, si 7 ascendent al lui 5? (2 7 6 5)

Evident. De fapt, nici nu se poate altfel - dacă 5 este descendent al lui 7, atunci 7 trebuie să fie ascendent al lui 5.

La lista de descendenti, ma refeream, cum pot fi scrisi pe o foaia (vreau sa dau bacul la informarica). La fel cum este lista de adiacenta, ca la grafurile neorientate si orientate.

Hmm, să vedem dacă am înțeles. Am făcut un exemplu nou pentru asta, are aceeași structură cu cel de mai sus, dar am redenumit nodurile ca să fie mai clar.

(imagine creată cu yEd)

Pe exemplul ăsta, listele de descendenți pentru fiecare nod în parte ar arăta cam așa:
A: {B, C, D, E, F, G, H, I}
B: {D, E, G, H}
C: {F, I}
D: {}
E: {G, H}
F: {I}
G: {}
H: {}
I: {}.

Ca să obții lista de descendenți a unui nod, te uiți pe arbore și vezi unde poți ajunge plecând de la nodul respectiv și mergând în jos pe muchii.

Bonus, listele de ascendenți pentru fiecare nod:
A: {}
B: {A}
C: {A}
D: {A, B}
E: {A, B}
F: {A, C}
G: {A, B, E}
H: {A, B, E}
I: {A, C, F}.

Pentru lista de ascendenți este exact invers - te uiți pe arbore și, plecând de la nodul căruia vrei să îi faci lista, vezi unde poți ajunge mergând în sus pe muchii.