ARBORI
Continutul lucrarii
Īn lucrare sunt prezentate operatiile de baza asupra arborilor binari, binari total echilibrati si arborilor oarecare.
Consideratii teoretice
Arborele binar, foarte des īntālnit īn aplicatii, este arborele īn care orice nod are cel mult doi descendenti: fiul stāng si fiul drept.
Construirea, traversarea si stergerea unui arbore binar.
Construirea unui arbore binar se face citind īn preordine din fisierul de intrare informatiile din nodurile arborelui. Subarborii vizi trebuie sa fie notati cu un semn distinctiv. De 858f53i exemplu pentru arborele din figura 2.1.1, notānd identificatorul pentru arborele vid cu * , introducerea identificatorilor nodurilor se va face astfel:
A B D * G * *
* C E * * F * H * *
Fig. 2.1.1. Arbore binar.
Tipul unui nod se declara astfel:
typedef struct tip_nod TIP_NOD;
Construirea unui arbore binar se face conform functiei de construire, avānd urmatoarea structura:
TIP_NOD *construire( )
return p;
Apelul functiei se va face astfel:
radacina = construire ( )
Traversarea unui arbore binar se poate face īn cele 3 moduri cunoscute: preordine, inordine, postordine.
Īn programul urmator sunt implementate operatiile de constructie si traversare a unui arbore binar. Nodul contine numai identificatorul sau. Afisarea nodurilor vizitate se face cu indentare.
/* Program de construire si afisare a arborilor binari */
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
typedef struct tip_nod TIP_NOD;
TIP_NOD *rad;
void preordine(TIP_NOD *p, int nivel)
void inordine(TIP_NOD *p, int nivel)
void postordine(TIP_NOD *p, int nivel)
TIP_NOD *constructie()
return p;
void main(void)
Arbori binari total echilibrati
Un arbore binar total echilibrat este un arbore binar care īndeplineste urmatoarea conditie: numarul nodurilor unui oricare subarbore stāng difera cu cel mult 1 īn plus fata de numarul nodurilor subarborelui corespunzator drept. Rezulta ca frunzele sale se afla pe ultimele doua niveluri.
Algoritmul de construire a unui arbore binar total echilibrat cu n noduri, este urmatorul:
a) un nod este radacina;
b) se iau nstg = [n/2] noduri pentru arborele stāng si se trece la construirea lui (pasul a);
c) se iau cele ndr=n-nstg-1 noduri ramase pentru subarborele drept si se trece la construirea lui (pasul a).
Pentru oricare nod exista relatia:
ndr <= nstg <= ndr + 1
Īn programul urmator este implementat acest algoritm pentru construirea unui arbore binar total echilibrat, citirea informatiei īn noduri facāndu-se īn preordine.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
/* ARBORI BINARI TOTAL ECHILIBRATI */
typedef struct tip_nod TIP_NOD;
TIP_NOD *rad;
void preordine(TIP_NOD *p, int nivel)
void inordine(TIP_NOD *p, int nivel)
}
void postordine(TIP_NOD *p, int nivel)
}
TIP_NOD *constructie(int nr_noduri)
return p;
}
void main(void)
Arbori oarecare
Arborele oarecare este un arbore a carui noduri au mai mult de doi descendenti.
Un nod are urmatoarea structura:
typedef struct tip_nod TIP_NOD;
Construirea arborelui se realizeaza astfel:
pentru fiecare nod se citeste informatia utila si numarul de fii;
nodurile citite īn postordine si adresele sunt pastrate īntr-o stiva pāna cānd apare nodul al carui fii sunt. Īn acest moment adresele fiilor sunt scoase din stiva, iar adresele lor sunt trecute īn nodul tata, dupa care adresa nodului tata este pusa īn stiva. Īn final singura adresa īn stiva va fi cea a radacinii, arborele fiind construit.
Traversarea arborelui pe orizontala (nivel dupa nivel) se va face astfel:
se utilizeaza o coada pentru pastrarea adreselor nodurilor ce urmeaza sa fie prelucrate;
initial coada este vida;
se introduce īn coada adresa radacinii;
se scoate pe rānd din coada adresa a cāte unui nod, se prelucreaza informatia din nod, iar apoi se introduc adresele fiilor nodului respectiv. Se repeta acest pas pāna cānd coada devine vida.
Mersul lucrarii
Se citeste de la tastatura o expresie matematica īn forma postfixata, sub forma unui sir de caractere. Sa se construiasca arborele corespunzator acestei expresii, fiecare nod continānd un operator sau un operand.
Sa se tipareasca expresia de la punctul 3.1. īn forma postfixata si infixata.
Sa se evalueze expresia matematica de la punctul 3.1.
Sa se evalueze un arbore care contine īn noduri constantele 0 si 1 si operatorii AND, OR, NOT.
Sa se scrie functii de pretty-print (tiparire frumoasa) a arborilor.
Sa se scrie functii nerecursive pentru traversarea arborilor.
Arborele genealogic al unei persoane se reprezinta astfel: numele persoanei este cheia nodului radacina si pentru fiecare nod cheia descendentului stāng este numele tatalui, iar a descendentului drept este numele mamei. Se citesc doua nume de la tastatura. Ce relatie de rudenie exista īntre cele doua persoane? Se presupune ca o familie are doar un singur fiu.
Sa se scrie un program care transforma un arbore binar īntr-o lista dublu īnlantuita.
Sa se scrie un program care sa interschimbe subarborele drept cu cel stāng pentru un nod dat.
Sa se scrie o functie care determina īnaltimea unui arbore binar.
Sa se scrie o functie care determina numarul de frunze ale unui arbore binar.
Sa se scrie o functie care determina daca doi arbori binari sunt echivalenti (arborii binari sunt echivalenti daca sunt structural echivalenti si datele corespunzatoare nodurilor sunt aceleasi).
Sa se scrie un program de construire si traversare a unui arbore oarecare conform indicatiilor din lucrare (paragraful 2.3.).
|
