Modul 10 — Arbori binari: cele trei parcurgeri

Arborele binar și reprezentarea lui

Fiecare nod are cel mult un fiu stâng și cel mult un fiu drept; 0 înseamnă „lipsă".

1// C++: doi vectori de „legături"

2int st[8] = {0, 2, 4, 0, 0, 7, 0, 0};

3int dr[8] = {0, 3, 5, 6, 0, 0, 0, 0};

4// nodul 1: fiu stâng 2, fiu drept 3

5// nodul 3: FĂRĂ fiu stâng, fiu drept 6

1# Python: clasa list (cum cere programa!)

2# fii[i] = [stang, drept], 0 = lipsă

3fii = [[], [2,3], [4,5], [0,6],

4 [0,0], [7,0], [0,0], [0,0]]

5stang, drept = fii[1] # despachetare

Stânga ≠ dreapta, chiar și singur: nodul 3 are DOAR fiu drept (6) — nu e totuna cu „are un fiu". Într-un arbore oarecare n-ar conta; la binar, poziția e parte din structură.

Cele trei parcurgeri — același arbore, trei melodii

Alege parcurgerea și apasă Pas: auriu = nodul AFIȘAT acum, albastru = pe stivă (în așteptare), verde = terminat.

stiva

afișat

alege parcurgerea și apasă Pas 👆

1void parcurg(int u) {

2 if (u == 0) return;

3 // PREordine: cout << u — AICI (înainte)

4 parcurg(st[u]);

5 // INordine: cout << u — AICI (între)

6 parcurg(dr[u]);

7 // POSTordine: cout << u — AICI (după)

Interpretările din programă: PREordine = șeful anunță întâi, apoi coboară — diseminarea rapidă a sarcinilor · POSTordine = întâi rapoartele de jos, șeful concluzionează la final — evaluarea completă · INordine = echilibru între ramuri — iar pe arborele binar de CĂUTARE (M11!) inordinea scoate valorile SORTATE.

Clasica de BAC: reconstruirea din preordine + inordine

Ți se dau două parcurgeri ale ACELUIAȘI arbore — și trebuie să-l refaci (sau să dai direct postordinea). Rețeta, pe exemplul nostru:

pre = [1, 2, 4, 5, 7, 3, 6] · in = [4, 2, 7, 5, 1, 3, 6]

① Rădăcina

PRIMUL din preordine = rădăcina: 1.

② Tai inordinea

Ce e ÎNAINTE de 1 în inordine = subarborele stâng {4,2,7,5}; ce e DUPĂ = cel drept {3,6}.

③ Repetă

Pe fiecare bucată, de la capăt: în stânga, rădăcina e 2 (primul din pre) → stânga lui: {4}, dreapta: {7,5}…

Verificarea finală: arborele reconstruit e exact cel din simulator, deci postordinea lui e 4, 7, 5, 2, 6, 3, 1 — răspunsul cerut la examen, fără să desenezi la întâmplare. Recursivitate curată: aceeași rețetă pe bucăți tot mai mici (X·M10!).

Fișa de sinteză

Arborele binar, condensat.

Arbore binar: cel mult 2 fii, cu identitate — stâng și drept; 0 = fiu lipsă; st[i]/dr[i] sau fii[i] = [s, d].

Preordine (RSD): rădăcina ÎNAINTE — 1, 2, 4, 5, 7, 3, 6. Primul element = rădăcina arborelui!

Inordine (SRD): rădăcina ÎNTRE — 4, 2, 7, 5, 1, 3, 6. Pe ABC (M11): valorile ies SORTATE.

Postordine (SDR): rădăcina DUPĂ — 4, 7, 5, 2, 6, 3, 1. Ultimul element = rădăcina!

Reconstrucția: rădăcina din pre → taie inordinea în stânga/dreapta → repetă recursiv pe bucăți.

Toate trei sunt aceeași funcție recursivă — diferă doar POZIȚIA lui cout << u (înainte / între / după apeluri).

Urmează: arborele binar care ține valorile ORDONATE prin construcție — arborele binar de căutare: căutarea binară din a X-a, devenită structură vie, cu inserare și căutare în O(înălțime).

Stânga, rădăcina, dreapta