Arbori

ARBORI

Continutul lucrarii

In lucrare sunt prezentate operatiile de baza asupra arborilor binari, binari total echilibrati si arborilor oarecare.

Consideratii teoretice

Arborele binar, foarte des intalnit in aplicatii, este arborele in care orice nod are cel mult doi descendenti: fiul stang si fiul drept.

Construirea, traversarea si stergerea unui arbore binar.

Construirea unui arbore binar se face citind in preordine din fisierul de intrare informatiile din nodurile arborelui. Subarborii vizi trebuie sa fie notati cu un semn distinctiv. De exemplu pentru arborele din figura 2.1.1, notand 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, avand urmatoarea structura:

TIP_NOD  *construire( )

return p;

Apelul functiei se va face astfel:

radacina = construire ( )

Traversarea unui arbore binar se poate face in cele 3 moduri cunoscute: preordine, inordine, postordine.

In 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)

Analiza: Documente specifice operatiilor cu numerar Eseu: Forma de contabilitate utilizata la o societate comerciala

Arbori binari total echilibrati

Un arbore binar total echilibrat este un arbore binar care indeplineste urmatoarea conditie: numarul nodurilor unui oricare subarbore stang difera cu cel mult 1 in 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 stang 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

In programul urmator este implementat acest algoritm pentru construirea unui arbore binar total echilibrat, citirea informatiei in noduri facandu-se in 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 in postordine si adresele sunt pastrate intr-o stiva pana cand apare nodul al carui fii sunt. In acest moment adresele fiilor sunt scoase din stiva, iar adresele lor sunt trecute in nodul tata, dupa care adresa nodului tata este pusa in stiva. In final singura adresa in 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 in coada adresa radacinii;

se scoate pe rand din coada adresa a cate unui nod, se prelucreaza informatia din nod, iar apoi se introduc adresele fiilor nodului respectiv. Se repeta acest pas pana cand coada devine vida.

Mersul lucrarii

Se citeste de la tastatura o expresie matematica in forma postfixata, sub forma unui sir de caractere. Sa se construiasca arborele corespunzator acestei expresii, fiecare nod continand un operator sau un operand.

Sa se tipareasca expresia de la punctul 3.1. in forma postfixata si infixata.

Sa se evalueze expresia matematica de la punctul 3.1.

Sa se evalueze un arbore care contine in 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 stang este numele tatalui, iar a descendentului drept este numele mamei. Se citesc doua nume de la tastatura. Ce relatie de rudenie exista intre cele doua persoane? Se presupune ca o familie are doar un singur fiu.

Sa se scrie un program care transforma un arbore binar intr-o lista dublu inlantuita.

Sa se scrie un program care sa interschimbe subarborele drept cu cel stang pentru un nod dat.

Sa se scrie o functie care determina inaltimea 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.).