arbori - informatica

ARBORI - informatica

Lecție de consolidare a cunoștințelor

Să ne reamintim

ARBORELE LIBER

Definiţia arborelui liber

Se numeşte arbore liber A un graf neorientat conex şi fără cicluri.

Observaţie.

De obicei se omite adjectivul „liber”, referirea la un graf conex aciclic făcându-se numai cu numele arbore.

Definiţie

Se numeşte subarbore al arborelui A=(X,U), orice arbore S=(Y,V) care are proprietatea: Y⊆X şi V⊆U.

Teorema

• Următoarele definiţii sunt echivalente pentru un graf G cu n noduri şi m muchii:

• (1) G este un arbore.

• (2) G este un graf aciclic cu n-1 muchii.

• (3) G este un graf conex cu n-1 muchii.

• (4) G este un graf fără cicluri maximal (dacă în graful fără cicluri G unim două noduri oarecare neadiacente printr-o muchie, graful obţinut conţine un ciclu).

• (5) G este un graf conex minimal (dacă în graful conex G suprimăm o muchie oarecare, graful obţinut nu mai este conex).

• (6) Orice pereche de noduri este legată printr-un lanţ şi numai unul.

Arbore binar

Definiţia arborelui binar

Se numeşte arbore binar un arbore cu rădăcină poziţional care are proprietatea că fiecare nod are cel mult doi descendenţi direcţi (succesori).

Terminologie:

- Cei doi succesori ai unui nod (dacă există) se numesc succesor stâng (subarbore stâng) şi succesor drept (subarbore drept)

Multiple Choice

Pentru un arbore binar cu n niveluri, numărul maxim de noduri din arbore este:

• n

• 2 ⋅ n

• 2ⁿ −1

• 2^n-1

Multiple Choice

Parcurgerea în postordine presupune:

• parcurgerea subarborelui stâng, a vârfului, apoi a subarborelui drept

• parcurgrea vârfului, a subarborelui stâng după care a celui drept

• parcurgerea subarborelui stâng, a subarborelui drept după care a vârfului

• vizitarea rădăcinii, a nodurilor de pe nivelul 1, a nodurilor de pe nivelul doi etc.

Arbore binar strict

Definiţie

Se numeşte arbore binar stict un arbore care are proprietatea că fiecare nod, cu excepţia nodurilor terminale, are exact doi descendenţi (succesori). 

Un arbore binar strict, care are n noduri terminale, are în total 2n-1 noduri. 

Un arbore binar strict are un număr impar de noduri. 

Multiple Choice

Care este tipul de parcurgere al unui arbore binar asociat unei expresii aritmetice pentru a obţine forma poloneză ?

• inordine

• preordine

• postordine

• lăţime

Multiple Choice

Dacă st şi dr sunt vectorii de reprezentare ai unui arbore binar, unde trebuie pusă instrucţiunea cout<< radacina; astfel încât parcurgerea să fie în inordine :

• înaintea parcurgerii st si dr

• între parcurgerile st și dr

• după parcurgerea st și dr

• nu conteaza unde se pune aceasta instrucțiune