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:
 |
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.).
|
