...
Structuri de date

Arbori binari: ce sunt și cum îi parcurgi

Pe scurt

Un arbore binar este o structură de date formată din noduri, în care fiecare nod are cel mult doi copii: unul în stânga și unul în dreapta. Nodul de sus se numește rădăcină, iar nodurile fără copii sunt frunze. Arborii binari stau la baza arborilor binari de căutare (BST), a heap-urilor și a multor probleme de interviu, care se rezolvă aproape toate cu una dintre cele patru parcurgeri.

  • 2copii, cel mult, pentru fiecare nod
  • 4parcurgeri: preordine, inordine, postordine, pe niveluri
  • O(log n)căutare într-un BST echilibrat
  • 2lecții gratuite, fără card
ARBORE BINAR DE CĂUTARE 831016914 1 3 6 8 9 10 14 inordine S · R · D

Parcurgerile unui arbore, în animație

Alege parcurgerea și apasă „Pornește”. Numărul de lângă fiecare nod arată când a fost vizitat. În inordine, un arbore binar de căutare dă valorile sortate.

Termenii de bază

TermenCe înseamnăÎn arborele din animație
rădăcinănodul de sus, fără părinte8
frunzănod fără copii1, 6, 9, 14
părinte / copillegătura directă dintre două noduri3 e părintele lui 1 și 6
niveldistanța de la rădăcină8 e pe nivelul 0, frunzele pe nivelul 2
înălțimenumărul de niveluri sub rădăcină2
subarboreun nod împreună cu toți descendenții lui3, 1, 6

Un arbore binar e complet când toate nivelurile sunt pline, cu excepția ultimului, și echilibrat când, la fiecare nod, înălțimile celor doi subarbori diferă cu cel mult 1.

Arbore binar și parcurgerea în inordine, în C++, Python și Java

Un nod ține valoarea și legăturile spre copii. Parcurgerile în adâncime se scriu natural recursiv; cea pe niveluri folosește o coadă.

class Nod:
    def __init__(self, val, st=None, dr=None):
        self.val, self.st, self.dr = val, st, dr


def inordine(nod):
    if nod is None:
        return []
    return inordine(nod.st) + [nod.val] + inordine(nod.dr)


#        8
#      /   \
#     3     10
#    / \   /  \
#   1   6 9    14
rad = Nod(8, Nod(3, Nod(1), Nod(6)), Nod(10, Nod(9), Nod(14)))
print(inordine(rad))   # [1, 3, 6, 8, 9, 10, 14]

Încearcă: cele trei parcurgeri ale unui arbore

Problema din lecția 97 a cursului de algoritmi: preordine, inordine și postordine, scrise recursiv în Python.

Exercițiu din lecția 97 · cursul de algoritmi

Parcurgerile în adâncime ale unui arbore

Scrie recursiv preordine(radacina), inordine(radacina) și postordine(radacina), fiecare returnând lista valorilor în ordinea respectivă. Pentru arborele gol returnează []. Clasa Nod și construieste sunt deja scrise.

  1. Cazul de bază: if radacina is None: return [].
  2. Combină [radacina.val] cu rezultatele pentru radacina.st și radacina.dr, în ordinea potrivită.
  3. Trebuie să apară: [1, 2, 4, 5, 3, 6], [4, 2, 5, 1, 3, 6], [4, 5, 2, 6, 3, 1], [] [7].
Indiciu: Diferența dintre cele trei funcții este doar locul lui [radacina.val].
from collections import deque


class Nod:
    def __init__(self, val, st=None, dr=None):
        self.val = val
        self.st = st
        self.dr = dr


def construieste(lista):
    """Creează arborele pe niveluri; None = lipsește copilul."""
    if not lista or lista[0] is None:
        return None
    radacina = Nod(lista[0])
    coada = deque([radacina])
    i = 1
    while coada and i < len(lista):
        nod = coada.popleft()
        if i < len(lista) and lista[i] is not None:
            nod.st = Nod(lista[i])
            coada.append(nod.st)
        i += 1
        if i < len(lista) and lista[i] is not None:
            nod.dr = Nod(lista[i])
            coada.append(nod.dr)
        i += 1
    return radacina


def preordine(radacina):
    if radacina is None:
        return []
    return [radacina.val] + preordine(radacina.st) + preordine(radacina.dr)


def inordine(radacina):
    if radacina is None:
        return []
    return inordine(radacina.st) + [radacina.val] + inordine(radacina.dr)


def postordine(radacina):
    if radacina is None:
        return []
    return postordine(radacina.st) + postordine(radacina.dr) + [radacina.val]


arbore = construieste([1, 2, 3, 4, 5, None, 6])
print(preordine(arbore))
print(inordine(arbore))
print(postordine(arbore))
print(preordine(None), inordine(construieste([7])))
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Pe tema asta, în cursul de algoritmi

Pagina îți arată metoda. În curs o aplici singur, pe probleme din ce în ce mai grele, cu verificare automată la fiecare.

Arborele binar de căutare (BST)

Într-un arbore binar de căutare, pentru fiecare nod, toate valorile din subarborele stâng sunt mai mici, iar cele din dreapta mai mari. De aceea cauți ca la căutarea binară: compari cu nodul curent și cobori într-o singură parte. Într-un BST echilibrat, căutarea, inserarea și ștergerea costă O(log n); într-unul dezechilibrat (de exemplu, dacă inserezi valori deja sortate) pot ajunge la O(n).

Parcurgerea în inordine a unui BST dă valorile în ordine crescătoare. Asta folosești în problema „este un BST valid?” și „al k-lea cel mai mic element”, ambele în lecțiile despre BST.

Arbori la BAC și la interviuri

La BAC Informatică, profilul mate-info, arborii apar în capitolul de grafuri: arbori cu rădăcină, vectorul de tați, frunze, niveluri, lanțuri. La interviuri, problemele cu arbori binari sunt printre cele mai frecvente: înălțimea, arborele în oglindă, diametrul, cel mai apropiat strămoș comun, serializarea. Aproape toate se rezolvă cu o parcurgere recursivă de câteva rânduri.

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

M-am inscris la cursurile de programare online gratuite, dupa care am achizitionat cursurile de java incepatori si intermediari. Foarte bune

Fotografia lui Madalina Pitrop, cursant al Academiei ProgramatorilorMadalina PitropRecenzie pe Google

Foarte profi si utile cursurile. Practica aplicata si explicata de traineri inarmati cu rabdare si cunostine solide.

Fotografia lui Iulian Pahom, cursant al Academiei ProgramatorilorIulian PahomRecenzie pe Google

Cursuri foarte utile si profesori foarte pregatiti. Recomand cu toata increderea.

Fotografia lui Catalina Ioana Dan, cursant al Academiei ProgramatorilorCatalina Ioana DanRecenzie pe Google

Întrebări frecvente

Ce este un arbore binar?

Un arbore binar este o structură de date ierarhică în care fiecare nod are cel mult doi copii, numiți copilul stâng și copilul drept. Nodul fără părinte este rădăcina, iar nodurile fără copii sunt frunzele.

Care sunt parcurgerile unui arbore binar?

Preordine (rădăcină, stânga, dreapta), inordine (stânga, rădăcină, dreapta), postordine (stânga, dreapta, rădăcină) și parcurgerea pe niveluri (BFS), care vizitează nodurile nivel cu nivel folosind o coadă.

Ce este un arbore binar de căutare?

Un arbore binar de căutare (BST) este un arbore binar în care, pentru fiecare nod, valorile din subarborele stâng sunt mai mici decât nodul, iar cele din subarborele drept sunt mai mari. Permite căutarea, inserarea și ștergerea în O(log n) dacă este echilibrat.

Ce este înălțimea unui arbore?

Înălțimea este numărul de muchii de pe cel mai lung drum de la rădăcină la o frunză. Un arbore cu un singur nod are înălțimea 0. Se calculează recursiv: 1 + maximul înălțimilor celor doi subarbori.

Ce diferență e între un arbore binar și un graf?

Un arbore este un graf conex fără cicluri. Un arbore cu n noduri are exact n - 1 muchii. Arborele binar adaugă regula că fiecare nod are cel mult doi copii.

Unde exersez arbori binari?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor ai 15 lecții despre arbori binari, BST, trie și heap, cu probleme rezolvate în Python direct în browser. Primele 2 lecții ale cursului sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.