Arbori Binari de Cautare

Proiect
7.5/10 (2 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 17 în total
Cuvinte : 2476
Mărime: 35.48KB (arhivat)
Cost: 4 puncte
Universitatea din Craiova Facultatea de Automatica, Calculatoare si Electronica

Cuprins

Arbori binari de cautare

1. Definiţii 3

2. Transformarea unui arbore generalizat in arbore binar 3

3. Operatorii arborelui binar 4

4. Arbori binari de căutare 5

5. Parcurgerea arborilor binari de cautare 6

6. Ştergerea unui nod dintr-un arbore binar ordonat 7

Aplicaţie – Operaţii cu arbori binari de cautare

1. Descrierea algoritmului 8

2. Funcţiile programului 9

3. Programul C++ 11

Bibliografie 18

Extras din document

Arbori binari de cautare

1. Definiţii

Un arbore este un graf orientat in care nu exista nici un ciclu(graf orientat aciclic)

Un arbore binar este o multime de n >= 0 noduri, care daca nu este vida, contine un nod numit radacina, restul nodurilor formând doi arbori disjuncti numiti subarborele stâng si subarborele drept.

Aceasta structura de date e importanta pentru ca e usor de reprezentat si prelucrat, orice arbore putând fi transformat în arbore binar

2. Transformarea unui arbore generalizat în arbore binar

Un arbore generalizat poate fi transformat intr-un arbore binar, astfel incât secventele de noduri pentru parcurgerea in preordine sa fie identice in cazul ambilor arbori.

Un arbore generalizat A cu radacina A1 si subarborii A1,1, A1,2, ,A1,k se transforma în arbore binar având radacina A1, A1,1 fiul sau stâng, iar A1,i devin fiii drepti ai lui A1,i-1 pentru 2<=i<=k.

Secventele de noduri în parcurgerea în preordine a arborelui generalizat si a celui binar obtinut prin transformare, sunt identice.

Exemplu: Se considera arborele generalizat de mai sus. Aplicând regula descrisa, se obtine arborele binar reprezentat.

Implementarea arborilor binari

Un arbore binar poate fi descris cu ajutorul urmatoarei structuri de date dinamice:

typedef struct informatie{

char nume[100];

long int pret ;

int cantitate;

}s;

typedef struct arbore{

informatie inf;

arbore *st,*dr;

}nod;

nod*prim,*prim1;

3. Operatorii arborelui binar

INITIALIZEAZA(A) - face vid arborele A;

INSEREAZA(X,A) - insereaza cheia X în arborele A;

CAUTA(X,A) - cauta cheia X, returnând true la gasire;

SUPRIMA(X,A) - suprima cheia X, daca exista;

TRAVERSEAZA(A) - parcurge toate cheile arborelui A

4. Arbori binari de cautare- Creare

Se numeste arbore de cautare un arbore binar ale carui noduri au o cheie de identificare, iar pentru fiecare nod sunt valabile proprietatile urmatoare:

- Orice cheie asociata unui nod este mai mare decat cheia subordonatului stang

- Orice cheie asociata unui nod este mai mica decat cheia subordonatului drept

Cheile de identificare sunt distincte.

Fie arborele din figura urmatoare. Cheile sunt : 30, 21 , 27, 15, 37, 31, 33, 36, 35, 24

Observatie: ordinea de inserare a cheilor poate determina o alta configuratie pentru arbore. Spre exemplu daca se insereaza mai intai 30 si apoi 27 si 21 atunci 27 va deveni subordonat stang pentru 30 si 21 subordonat stang pentru 27.

Crearea arborilor de cautare se realizeaza aplicand de un numar de ori operatia de inserare. Inserarea se realizeaza astfel:

-se compara valoarea k de inserat cu cheia asociata nodului curent. Exista urmatoarele posibilitati:

- cheia coincide cu valoarea de inserat si se renunta la inserare

- cheia este mai mica decat k caz in care se incearca inserarea in subarborele drept

- cheia este mai mare decat k caz in care se incearca inserarea in subarborele stang

- inserarea propriuzisa se realizeaza atunci candsubarborele stang , respectiv drept, este vid, altfel se reia.

Parcurgerea arborilor de cautare se face ca orice arbore binar (svd, vsd sdv).

Cautarea unei valori se determina in mod similar cu subprogramul de inserare

Preview document

Arbori Binari de Cautare - Pagina 1
Arbori Binari de Cautare - Pagina 2
Arbori Binari de Cautare - Pagina 3
Arbori Binari de Cautare - Pagina 4
Arbori Binari de Cautare - Pagina 5
Arbori Binari de Cautare - Pagina 6
Arbori Binari de Cautare - Pagina 7
Arbori Binari de Cautare - Pagina 8
Arbori Binari de Cautare - Pagina 9
Arbori Binari de Cautare - Pagina 10
Arbori Binari de Cautare - Pagina 11
Arbori Binari de Cautare - Pagina 12
Arbori Binari de Cautare - Pagina 13
Arbori Binari de Cautare - Pagina 14
Arbori Binari de Cautare - Pagina 15
Arbori Binari de Cautare - Pagina 16
Arbori Binari de Cautare - Pagina 17

Conținut arhivă zip

  • Arbori Binari de Cautare.doc

Alții au mai descărcat și

Tablou de Structuri

1.Introducere Limbajul C apare pe la sfîrşitul anilor 60, cînd Martin Richards a propus limbajul BCPL, orientat programatorilor ce cunoşteau bine...

Arhitectura Calculatoarelor - Intel vs AMD

Rezultatele din testul 3DS Max 7 SPECapc Test Testul alaturat consta in crearea modelelor 3D, modificarea si randarea scripturilor. Conform...

Algoritmi și Structuri de Date

Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...

Aplicatii cu Arbori Binari - Evaluarea Arborilor Asociati Expresiilor

Obiective In urma parcurgerii acestui laborator, studentul va fi capabil: - sa inteleaga notiunea de arbore si structura unui arbore binar; - sa...

Siruri de Caractere in C si C++

Functii de intrare / iesire relative la siruri de caractere. Pentru a citi un sir de caractere de la intrarea standard se foloseste functia gets()...

Ai nevoie de altceva?