1
┌──────────┼──────────┐
2 3 4
┌───┴───┐ ┌──┴──┐ │
5 6 7 8 9
┌─┴─┐ │ ┌┴┐ │
10 11 12 13 14 15
Explicații pentru acest arbore:
Definiție:
Un arbore cu rădăcină poate fi reprezentat simplu printr-un vector numit vector de tați.
Pentru fiecare nod al arborelui se notează tatăl său.
Rădăcina are valoarea 0 (deoarece nu are tată).
Această metodă este foarte eficientă pentru că:
1
┌─────────┬───────────┬─────────┐
2 3 4 5
┌──┴──┐ ┌──┴──┐ ┌──┴──┐ │
6 7 8 9 10 11 12
┌┴┐ ┌┴┐ │ ┌─┴─┐ │
13 14 15 16 17 18 19 20
Explicații:
| T[i] | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | 7 | 9 | 10 | 10 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Nod (i) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
1
/ \
2 3
/ \
4 5
Fiecare nod are cel mult doi fii. Exemplu:
1
/ \
2 3
/ \
4 5
Ultimul nivel este umplut de la stânga la dreapta. Exemplu:
1
/ \
2 3
/ \ /
4 5 6
Toate nivelurile sunt complet umplute. Numărul total de noduri = 2^h - 1, unde h este înălțimea arborelui. Exemplu:
1
/ \
2 3
/ \ / \
4 5 6 7
Pentru fiecare nod, toate nodurile din subarborele stâng au valori mai mici, iar cele din subarborele drept au valori mai mari.
Exemplu:
50
/ \
25 75
/ \ / \
12 37 62 87
/ \ / \ / \ / \
6 18 31 43 56 68 81 93
Același arbore, dar verificăm echilibrarea (diferența de înălțime ≤1 între subarborii stâng și drept). Exemplu:
50
/ \
25 75
/ \ / \
12 37 62 87
/ \ / \ / \ / \
6 18 31 43 56 68 81 93
Enunț: Se citește un arbore binar cu 7 noduri. Determinați vectorul de tați și lista frunzelor.
Exemplu:
1
/ \
2 3
/ \
4 5
Rezolvare:
Enunț: Se citește un arbore binar. Determinați înălțimea arborelui.
Exemplu:
1
/ \
2 3
/ \
4 5
Rezolvare: Cel mai lung lanț de la rădăcină la frunză: 1 → 2 → 4 → înălțime = 2
Se citește următorul arbore binar cu 15 noduri:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
Determinați vectorul de tați.
Rezolvare:
tati[1]=0, tati[2]=1, tati[3]=1, tati[4]=2, tati[5]=2, tati[6]=3, tati[7]=3, tati[8]=4, tati[9]=4, tati[10]=5, tati[11]=5, tati[12]=6, tati[13]=6, tati[14]=7, tati[15]=7
Se citește următorul arbore binar:
1
/ \
2 3
/ \ / \
4 5 6 7
Aflați frunzele arborelui.
Rezolvare: Frunze: 4, 5, 6, 7
Se dă un arbore binar cu 10 noduri:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
|
10
Determinați înălțimea maximă a arborelui.
Rezolvare: Înălțime maximă = 4 (lanț: 1 → 2 → 4 → 8 → 10)
Se dă un arbore binar complet cu 7 noduri:
1
/ \
2 3
/ \ /
4 5 6
\
7
Precizați frunzele arborelui.
Rezolvare: Frunze: 4,5,6,7
Se dă un arbore binar perfect cu 15 noduri:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
Precizați nivelul fiecărui nod.
Rezolvare: Nivel 0:1; Nivel1:2,3; Nivel2:4,5,6,7; Nivel3:8-15
Se citește următorul arbore binar:
1
/ \
2 3
/ \ \
4 5 6
Determinați vectorul de tați.
Rezolvare: tati[1]=0, tati[2]=1, tati[3]=1, tati[4]=2, tati[5]=2, tati[6]=3
Se dă un arbore binar cu 9 noduri:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
Aflați toate frunzele arborelui.
Rezolvare: Frunze: 4,5,8,9,7
Se dă un arbore binar complet cu 10 noduri. Determinați numărul maxim de frunze.
Rezolvare: Frunze maxime = 6 (nivel complet până la penultimul nivel + ultimele noduri)
Se dă un arbore binar perfect cu 31 de noduri. Determinați înălțimea arborelui și numărul de frunze.
Rezolvare: Înălțime = 4 (niveluri 0–4), frunze = 16
Se dă un arbore binar:
1
/ \
2 3
/ / \
4 5 6
\
7
Determinați nivelul fiecărui nod.
Rezolvare: Nivel 0:1; Nivel1:2,3; Nivel2:4,5,6; Nivel3:7
Se citește un arbore binar cu 6 noduri:
1
/ \
2 3
/ \
4 5
\
6
Determinați vectorul de tați.
Rezolvare: tati[1]=0, tati[2]=1, tati[3]=1, tati[4]=2, tati[5]=2, tati[6]=5
Se dă un arbore binar cu 12 noduri, complet până la nivelul 3. Determinați frunzele arborelui.
Rezolvare: Frunze: 8,9,10,11,12
Se dă un arbore binar perfect cu 7 noduri. Determinați înălțimea și numărul de frunze.
Rezolvare: Înălțime = 2, Frunze: 4,5,6,7 → 4 frunze
Se dă un arbore binar cu 5 noduri:
1
/ \
2 3
/ \
4 5
Determinați vectorul de tați și frunzele arborelui.
Rezolvare: tati[1]=0, tati[2]=1, tati[3]=1, tati[4]=2, tati[5]=2; Frunze: 3,4,5
Se dă un arbore binar cu 8 noduri:
1
/ \
2 3
/ \ / \
4 5 6 7
/
8
Determinați nivelul fiecărui nod și frunzele arborelui.
Rezolvare: Nivel 0:1; Nivel1:2,3; Nivel2:4,5,6,7; Nivel3:8; Frunze: 5,6,7,8
1. Într-un arbore cu 50 de noduri, numerotate de la 1 la 60, rădăcina este nodul numerotat cu 1, iar tatăl oricărui alt nod i al său este nodul numerotat cu [i/2]. Indicați lungimea lanțului elementar cu o extremitate în nodul 32 și cealaltă extremitate în nodul 23.
2. Un arbore cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [1,3], [2,4], [2,5], [2,6]. Indicați două noduri care pot fi alese drept rădăcină, astfel încât arborele obținut, pentru fiecare dintre acestea, să aibă trei frunze.
3. Un arbore cu 8 noduri, numerotate de la 1 la 8, este reprezentat prin vectorul de „tați” (3, 0, 2, 5, 2, 5, 1, 5). Enumerați două noduri ale arborelui care pot fi alese drept rădăcină (cu excepția rădăcinii curente), astfel încât nodul 4 să aibă aceiași „frați” ca în reprezentarea dată.
4. Un arbore cu 11 noduri, numerotate de la 1 la 11, este reprezentat prin vectorul de „tați” (4,3,7,6,7,8,6,0,7,7,7). Indicați numărul maxim de descendenți direcți (“fii”) ai unui nod.
5. Un arbore cu 14 noduri, numerotate de la 1 la 14, este reprezentat prin vectorul de “tați” (13,3,0,6,13,3,3,7,6,2,13,2,6,13). Indicați nodul care este rădăcina arborelui.
6. Un arbore cu 8 noduri, numerotate de la 1 la 8, este reprezentat prin vectorul de „tați”: (3,0,2,5,2,5,1,5). Enumerați, în ordinea parcurgerii lor, nodurile celui mai lung lanț elementar care are extremitatea inițială în rădăcină.
7. Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „tați” (7,4,6,7,4,7,0,9,6,5). Indicați numărul de noduri „frunză” ale acestui arbore.
8. Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „tați” (8,1,4,5,0,9,4,5,4,3). Enumerați toate nodurile arborelui care au câte un singur descendent direct („fiu”).
9. Un arbore cu 7 noduri, numerotate de la 1 la 7, este reprezentat prin vectorul de „tați” (4,6,6,2,2,0,1). Indicați adâncimea arborelui.
10. Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „tați” (4,8,0,3,2,10,3,3,2,4). Indicați adâncimea arborelui.
11. Un arbore cu 14 noduri, numerotate de la 1 la 14, este reprezentat prin vectorul de „tați” (13,3,0,6,13,3,3,7,6,2,13,2,6,13). Indicați adâncimea arborelui.
12. Într-un arbore cu 50 de noduri, numerotate de la 1 la 50, rădăcina este nodul numerotat cu 1, iar tatăl oricărui nod i al său este nodul numerotat cu [i/2]. Indicați numărul de frați ai nodului numerotat cu 25.
13. Un arbore cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [1,3], [1,4], [4,5], [4,6]. Indicați două noduri care pot fi alese drept rădăcină, astfel încât arborele obținut, pentru fiecare dintre acestea, să aibă trei frunze.
14. Un arbore cu 8 noduri, numerotate de la 1 la 8, este reprezentat prin vectorul de „tați” (3,0,2,5,2,5,1,5). Indicați numărul de noduri „frunză” ale arborelui.
15. Un arbore cu 11 noduri, numerotate de la 1 la 11, este reprezentat prin vectorul de „tați” (4,3,7,6,7,8,6,0,7,7,7). Indicați adâncimea arborelui.
16. Un arbore cu 7 noduri, numerotate de la 1 la 7, este reprezentat prin vectorul de „tați” (2,7,2,3,3,5,0). Enumerați nodurile arborelui care sunt frunze.
17. Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „tați” (8,1,4,5,0,9,4,5,4,3). Indicați numărul de frați ai nodului numerotat cu 4.
18. Într-un arbore cu 50 de noduri, numerotate de la 1 la 50, rădăcina este nodul numerotat cu 1, iar tatăl oricărui nod i al său este nodul numerotat cu [i/2]. Indicați adâncimea arborelui.
19. Un arbore cu 6 noduri, numerotate de la 1 la 6, are muchiile [1,2], [1,3], [1,4], [4,5], [4,6]. Indicați doi strămoși ai nodului 6 care nu sunt succesivi.
20. Un arbore cu 10 noduri, numerotate de la 1 la 10, este reprezentat prin vectorul de „tați” (7,4,6,7,4,7,0,9,6,5). Indicați numărul maxim de descendenți direcți („fii”) ai unui nod.