1

Programare in limbajul C – Cursul 17 Arbori

Prof. univ. dr. Constantin Popescu

Agenda Arbori binari Arbori oarecare Exemple

Arbori binari Vom defini arborii binari ca un set finit T de unul sau mai multe

noduri, astfel încât:– Există un nod cu destinaţie specială numit tulpină (rădăcină) arborelului;– Celelalte noduri sunt repartizate în două seturi disjuncte şi fiecare din

aceste seturi la rândul lui este un arbore binar. Observaţii:

– Cei doi arbori subordonaţi de rădăcină poartă denumirea de subarbore stâng şi subarbore drept;

– Această definiţie este recursivă, acest lucru fiind de mare folos în continuare;

– Dacă un nod nu subordonează arbori, îl vom numi nod terminal, în caz contrar îl vom numi nod neterminal.

Presupunem că vrem să tratăm problema contorizării cuvintelor dintr-un text.

Fiecare nod al arborelui conţine o structură cu următoarele informaţii:– Un pointer la cuvânt– Un contor care numără apariţiile cuvântului– Un pointer la subarborele stâng– Un pointer la subarborele drept

Arbori binari Vom crea arborele astfel încât în subarborele stâng al oricărui nod să

avem numai cuvinte care sunt mai mici (lexicografic) decât cuvintele din nod

In subarborele drept al oricărui nod să avem numai cuvinte care sunt mai mari (lexocografic) decât cuvântul din nod.

Pentru a vedea dacă un cuvânt a mai fost întâlnit, procedăm în felul următor: pornim de la rădăcină şi comparăm cuvântul nou cu cuvântul din acel nod.

În caz de egalitate, incrementăm contorul. Dacă noul cuvânt este mai mic decât cuvântul din nod, căutarea se face în subarborele stâng, iar în caz contrar în subarborele drept.

Dacă procesul de căutare nu mai poate continua (nodul în care am ajuns nu mai are alţi subarbori), cuvântul va fi plasat în arbore în locul corespunzător. Descrierea unui nod se poate face astfel:

struct tnode {char *word; int count;struct tnode *left;struct tnode *right;

};

Arbori binari Este incorect ca o structură să conţină o referire la ea

însăşi (să fie recursivă), ca în exemplul de mai jos:struct tnode /* GREŞIT */{

char *word;int count;struct tnode left;struct tnode right;

}; Declaraţia

struct tnode *left; declară pe left ca fiind pointer la structura tnode (ceea

ce este corect) şi nu o structură tnode.

Exemplu Dăm în continuare varianta recursivă a programului pentru

rezolvarea problemei contorizării cuvintelor din intrare. Cuvintele vor fi citite dintr-un fişier text.

#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAXWORD 100

struct tnode{

char *word; int count; struct tnode *left;

struct tnode *right;};struct tnode * addtree( struct tnode *, char * );void treeprint( struct tnode * );

Exempluint main(){ struct tnode *root; char word[MAXWORD]; FILE *fp; root = NULL; fp = fopen("text.dat", "rt"); if( fp == NULL) {

fprintf(stderr, "Nu pot deschide fisierul\n\b"); return 1;

} do {

fscanf(fp, "%s", word); if( word[0] != '\0' )

root = addtree(root, word); } while(!feof(fp)); treeprint( root ); return 0; }

Exemplustruct tnode * addtree( struct tnode *p, char *w ){ int cond; if( p == NULL) {

p = malloc( sizeof(struct tnode) ); p->word = strdup(w); p->count = 1; p->left = p->right = NULL;

} else if( (cond = strcmp(w, p->word)) == 0 )

p->count++; else if( cond < 0 )

p->left = addtree( p->left, w);else

p->right = addtree( p->right, w); return p;}

Exempluvoid treeprint( struct tnode * p)

{

if( p != NULL )

{

treeprint( p->left );

printf("%s %d\n", p->word, p->count );

treeprint( p->right );

}

}

Exemplu Dăm în continuare o variantă nerecursivă a funcţiei de adăugare

a unui nou nod în arborele binar de căutare, variantă care este mult mai clară şi mai eficientă:

void addtree2( struct tnode **root, char * w){

int in = 0, cond; struct tnode *p = *root, *q; if( p == NULL) {

p = malloc( sizeof(struct tnode) ); p->word = strdup(w); p->count = 1; p->left = p->right = NULL; *root = p; in = 1;

}

Exempluwhile( !in ) {

if( (cond = strcmp(w, p->word)) == 0) {p->count++;in = 1;

} else if( cond < 0 )

if( p->left !=NULL )p = p->left;

else { q = malloc( sizeof(struct tnode) ); q->word = strdup(w); q->count = 1; q->left = q->right = NULL; p->left = q; in = 1;}

Exempluelse if( p->right != NULL )

p = p->right; else {

q = malloc( sizeof(struct tnode) ); q->word = strdup(w); q->count = 1; q->left = q->right = NULL; p->right = q; in = 1;}

}}

Arbori oarecare Un arbore oarecare este un set finit T de unul sau mai multe

noduri astfel încât: – Există un nod cu destinaţie specială numit rădăcina arborelui;– Celelalte noduri sunt repartizte în m>0 seturi disjuncte T1, T2, …, T3

unde fiecare din aceste seturi la rândul său este un arbore oarecare.

Vom scrie un program pentru crearea unui arbore oarecare pe care îl vom parcurge în două moduri folosite de obicei pentru parcurgerea arborilor oarecare: – parcurgerea în adâncime (deapth first) în care se vizitează prima dată

rădăcina, apoi subarborii de la stânga la dreapta;– parcurgerea în lăţime (breadth first) presupune parcurgerea pe nivele a

arborelui. Rădăcina arborelui se consideră că este pe nivelul 0 Toate nodurile legate direct de rădăcina se consideră pe nivelul 1

etc.

Exemplu de arbore oarecare Exemplu de arbore oarecare:

Parcurgerea în adâncime a acestui arbore: 1 2 5 6 3 7 4 8. Parcurgerea în lăţime: 1 2 3 4 5 6 7 8. Programul de mai jos crează un arbore oarecare, pornind de la

rădăcină. Pentru fiecare nod se cere informaţia din nod, care în cazul

nostru va fi un număr întreg, şi numărul de fii ai acelui nod. Crearea arboreului se face în funcţia recursivă crearb. Funcţiile padinc şi plat sunt funcţiile pentru parcurgerea

arborelului în adâncime respectiv în lăţime.

Exemplu#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

struct nod

{

int inf;

int dim;

struct nod* tab[100];

};

struct nod * crearb(void);

/* Functia pentru parcurgerea in adincime */

void padinc(struct nod *);

/*Functia pentru parcurgerea in latime*/

void plat(struct nod *);

Exempluint main(){ struct nod *root;

clrscr();

/*Creez arborele*/

root = crearb(); printf("Parcurgere in adincime:"); padinc(root); printf("\nParcurgere in latime:"); plat(root); return 0;}

Exemplustruct nod * crearb(){ int inf; int n, i; struct nod *p; printf("Inf="); scanf("%d", &inf); p = malloc( sizeof(struct nod) ); p->inf = inf; printf("Cati fii are?"); scanf("%d", &n); p->dim = n; for(i = 0; i < n; i++)

p->tab[i] = crearb(); return p;}

Exempluvoid padinc(struct nod *p)

{

int i;

if( p != NULL )

{

printf("%d", p->inf);

for( i = 0; i < p->dim; i++)

padinc( p->tab[i] );

}

}

Exempluvoid plat(struct nod *p)

{

struct nod *queue[100];

struct nod *t; int front = 0, back = 0;

int i;

queue[ front++ ] = p;

while ( ! (front == back) )

{

t = queue[ back ]; back++;

printf("%d", t->inf);

for(i = 0; i < t->dim; i++)

queue[ front++ ] = t->tab[i];

}

}