Fie un graf neorientat G=(V,U), unde V e mulțimea vârfurilor, iar U cea a muchiilor sale. Următoarele afirmații sunt echivalente:
1. G este arbore.
2. G este un graf conex minimal („minimal” se numește proprietatea unui graf, că dacă i se elimină orice muchie, se obține un graf neconex).
3. G este un graf fără cicluri maximal („maximal” se numește proprietatea unui graf, că dacă i se adaugă orice muchie, se obține un graf care are măcar un ciclu, și deci nu e arbore).
Un arbore cu n ≥ 2 vârfuri conține cel puțin două vârfuri terminale. Orice arbore cu n vârfuri are n-1 muchii.
Un arbore este o structura ramificata formata dintr-un nod A (radacina) si un numar finit de arbori (subarbori) ai lui A.
- orice nod din arbore este radacina pentru un subarbore iar orice arbore poate deveni subarbore;
- doi subarbori pot fi în relatie de incluziune, când un subarbore este inclus în celalalt sau de excluziune, când nu au noduri comune.
Definitii:
nod = punct în care se întâlnesc doi subarbori;
nivel = numarul de noduri parcurse de la radacina pâna la un nod;
radacina = nivel 1;
descendent = primul nod al unui subarbore;
nod terminal = nod fara descendenti;
înaltimea unui arbore = numarul maxim de niveluri;
arbore binar = arbore în care toate nodurile au maximum 2 descendenti
Dacă avem în vedere faptul că un arbore binar este un arbore, care înainte de toate este un graf, putem spune că printre metodele de reprezentare a arborilor binari se numără şi metodele de reprezentare a grafurilor, cum ar fi:
-reprezentarea prin matricea de adiacenţă;-reprezentarea prin listele de adiacenţă;-reprezentarea prin şirul muchiilor;Modalităţile de reprezentare specifice arborilor binari sunt:1.cu ajutorul vectorilor2.folosind alocarea dinamică
Se numeşte arbore binar complet un arbore binar în fiecare nod, care nu este frunză, are exact doi descendenţi.
Propoziţie:Un arbore binar complet care are p noduri terminale, toate situate pe acelaşi nivel, are în total 2p-1 noduri.
Parcurgerea arborilor binari
ARBORI GENERALIZATI/BINARI
http://bigfoot.cs.upt.ro/~chirila/teaching/upt/lectures/2id-aa/AA-ID-Cap08-1.pdf
Vezi
http://informaticasite.ro/probleme-rezolvate-c++/arbori/
Probleme propuse
test_grafuri_neorientate2.docx
test_grafuri_neorientate3.docx
1. Elevii unei clase stau in banca cate doi sau cate unul singur. Cand este nevoie sa se faca un anunt urgent la sfarsit de saptamana sau in vacanta, ei au stabilit un sistem prin care un elev va anunta pe altii doi care sunt colegi de banca, sau pe unul singur, daca nu are coleg de banca (exista si elevi care nu vor da telefoane mai departe). Stiind ca doamna diriginta face primul anunt (anunta doi elevi care sunt colegi de banca) si apoi fiecare elev isi anunta alti doi colegi de banca (sau unul sau niciunul) de clasa si asa mai departe, se cere sa se scrie un program care realizeaza urmatoarele:
a) memorarea datelor intr-un arbore binar alocat in heap. Un elev inexistent se va marca cu * ARBORE.cxx
b) numara si afiseaza din cati elevi este formata clasa
c) afiseaza numele tuturor elevilor din clasa
d) sa se determine daca un elev face parte din clasa
e) sa se afiseze elevii anuntati de diriginta
f) sa se afiseze cologii de banca (perechi)
g) numara cati elevi au acelasi nume cu un nume dat de la tastatura
h) afiseaza numele elevilor care nu mai au de anuntat pe nimeni
i) sa se afiseze colegul de banca al lui Gigel (sau un nume citit de la tastatura)
j) cine ar fi trebuit sa il anunte pe Dan (sau un nume citit de la tastatura)
k) sa se afiseze elevii care stau in stanga in banci
l) elevul x si elevul y isi schimba locurile. Sa se afiseze.
m) cate banci sunt ocupate de un singur elev
n) cate banci sunt ocupate de doi elevi
o) cate banci sunt ocupate
2. Un arbore binar retine numere intregi.
a) sa se afiseze numerele utilizand una dintre metode.
b) sa se afiseze numerele pare din arbore
c) sa se determine cel mai mare numar din arbore
d) sa se determine suma cifrelor tuturor numerelor din arbore
e) afisati frunzele
f) sa se determine daca exista o anumita valoare in arbore
g) sa se determine daca arborele contine numere prime
h) sa se genereze oglinditul arborelui
i) sa se afiseze subordonatii stangi
j) sa se inlocuiasca o cheie cu o alta
k) sa se inverseze doua chei
l) sa se afiseze fratele lui x
m) sa se afiseze tatal lui x
n) sa se afiseze fii (fiul) lui x
o) sa se determine minimul din arbore
p) sa se afiseze nodurile cu un singur subordonat
2. Fie un arbore binar memorat prin vectorii stang si drept. Sa se parcurga arborele prin cele trei metode.
3. Fiind dat un arbore binar memorat in heap, sa se genereze un nou arbore binar identic cu primul.
4. Fie un arbore binar memora in heap.
a) Sa se afiseze cate niveluri are arborele
b) Sa se afiseze nodurile de pe nivelul x
c) sa se afiseze nodurile pe niveluri
d) Calculati si afisati suma nodurilor de pe un nivel dat
e) sa se afisese frunzele care nu se gasesc pe ultimul nivel
5.Un arbore binar retine caractere.
a) sa se determine cate vocale retine arborele
b) se citeste un sir de caractere de la tastatura. Sa se determine daca sirul citit este egal cu sirul determinat de parcurgerea arborelui (svd, vsd sau sdv).
6. Fie un graf orientat memorat prin matricea de adiacenta. Sa se determine daca graful poate fi arbore binar. In caz afirmativ , pentru o solutie oarecare, sa se parcurga svd.
7. Fie un arbore binar. Sa se completeze arborele astfel incat fiecare nod sa aiba 2 subordonati. Valoarea cu care se face completarea se citeste de la tastatura.
8. Fie un arbore binar cu n noduri numerotate de la 1 la n cu radacina 1, in care cheia fiecarui nod este un numar intreg. Numarul de noduri se citeste de la tastatura. Reprezentarea in memorie se face inlantuit cu referinte descendente astfel: pe fiecare dintre cele n randuri ale fisierului text arbore.in se afla cate trei numere intregi, separate prin cate un spatiu reprezentand fiul stang, fiul drept si valoarea cheii fiecarui nod al arborelui. Sa se scrie cate un program C++ pentru fiecare dintre
cerintele de mai jos:
a) sa se afiseze nodurile care retin informatiile numere pare;
b) sa se afiseze nodurile care au doar descendent stang;
c) sa se afiseze cheile nodurilor care au doar descendent drept;
d) sa se afiseze cheile din nodurile terminale;
e) sa se afiseze fiii nodului x, furnizat de utilizator;
f) sa se afiseze nodul tata al unui nod x, furnizat de utilizator;
g) sa se scrie in fisierul noduri.out, nodurile ale caror chei sunt egale cu o valoare val,
citita de la tastatura;
h) sa se calculeze inaltimea arborelui binar dat;
i) sa se determine nivelul maxim;
j) sa se afiseze cheia maxima.