Predavanje 12 - Rekurzivni algoritmi II -Stabla

1. Uvod

Stabla su matematicke apstrakcije koje su centralne u dizajnu i analizi algoritama:

Stablo (eng. tree) mozemo definirati kao skup vrhova cvorova i grana koji spajaju neke od tih cvorova, te postoji istaknuti cvor tvz. korijen kojeg kada uklonimo dobijemo disjuktnu uniju stabala.

Ova definicija stabla je rekurzivna: Stabla su definirana u terminima stabala. Npr. direktorij je definiran u terminima datoteka koje sadrzi i daljnjih direktorija.

Gornja definicija nema problema sa cirkularnoscu jer uvijek znamo da najmanje stablo je samo jedan cvor.

Gornja definicija povlaci da je svaki cvor stabla zapravo korijen nekog podstabla sadrzanog u cijelom stablu. Broj podstabala danog cvora naziva se stupanj cvora:

Nivo cvora u stablu S definiran je rekurzivno na ovaj nacin:

Uredjeno stablo definira se kao i obicno stablo samo sto specificiramo uredjaj medju podstablima koje dobijemo kada uklonimo korijen na neki nacin. Mi cemo uvijek implicitno pretpostavljati takav uredjaj.

1. Binarna stabla

Binarno stablo je za nas najvazniji slucaj stabla i definira se rekurzivno kao konacan skup cvorova (i grana) koji je ili prazan ili se sastoji od

Primjer: binarno stablo aritmetickog izraza a-b*(c/d+e*f)

Binarno stablo je posebno jednostavno deklarirati u C-u:

typedef struct cvor *veza; struct cvor { NEKI_PODATAK podatak; veza d; /*desna grana*/ veza l; /*lijeva grana*/ };

Kao i kod vezanih list moramo cuvati pokazivac na korijen binarnog stabla. Praznu granu oznacavamo sa NULL.

Pojedini cvorovi stabla kreiraju se na analogno kreiranju elemenata vezane liste:

veza x=(veza)malloc(sizeof *x); if(x){ /*memorija je alocirana*/ x->podatak=neka_vrijednost; x->l=lijevi; x->d=desni; }

2. Setnja po binarnom stablu

Pocevsi od pokazivaca na korijen binarnog stabla trebamo sistematski "prosetati" se kroz stablo tako da posjetimo sve cvorove samo jednom.

Kod vezanih listi smo se kretali linearno od cvora do iduceg cvora dok nismo naisli na znak za kraj liste npr. NULL vezu, a procesirati cvorove mozemo na dva nacina:

Kod binarnih stabala je situacija nesto kompliciranija jer se od svakog cvora mozemo kretati ili lijevo ili desno. Imamo tri mogucnosti:

Rekurzivna implementacija setnje kroz cvorove binarnog stabla u sva tri slucaja. (Uocite male razlike u kodu!)

typedef struct cvor *grana; struct cvor { NEKI_PODATAK podatak; veza d; /*desna grana*/ veza l; /*lijeva grana*/ }; void preorder(veza x){ if(x==NULL) return; /*dosli smo do kraja*/ /* Ovdje napisemo kod koji procesira cvor stabla. Zatim idemo lijevo i desno kao sto treba u inorder-u. */ preorder(x->l); preorder(x->d); } void inorder(veza x){ if(x==NULL) return; /*dosli smo do kraja*/ /*prvo idemo lijevo*/ inorder(x->l); /* Zatim se procesira tekuci cvor stabla. Ovdje dodje kod. Na kraju idemo desno. */ inorder(x->d); } void preorder(veza x){ if(x==NULL) return; /*dosli smo do kraja*/ /*prvo idemo lijevo i desno ...*/ preorder(x->l); preorder(x->d); /* ...onda procesiramo tekuci cvor stabla */ }

2. Primjene setnje po stablu

1. Broj cvorova u stablu:

int broj_cvorova(veza x){ if(x==NULL) return 0; /*dosli smo do kraja*/ /*vratimo broj cvorova lijeve i desne grane*/ return broj_cvorova(x->l)+ broj_cvorova(x->d) + 1; }

2. Visina stabla je maksimum nivoa svih cvorova u stablu. Iduca funkcija racuna visinu stabla.

int visina(veza x){ int u,v; if(x==NULL) return -1; /*dosli smo do kraja*/ /*vratimo broj cvorova lijeve i desne grane*/ u=visina(x->l); v=visina(x->d); if (u>v) return u+1; else return v+1; }

3. Programi prevodioci koriste stabla za internu reprezentaciju programa kojeg se prevodi (cesto u asembler, ali moze i drugi programski jezik). Iduci program parsira stringove koji su aritmeticki izrazi i daje njihovu reprezentaciju u obliku stabla. Npr. iduci program daje binarnu reprezentaciju prefiks oblika u kojem zbog jednostavnosti pretpostavljamo da se pojavljuje samo mala slova za varijable, + i *.

#include<stdio.h> char* a="*+a**bc+def";/*izraz kojeg parsiramo*/ int i; typedef struct cvor *veza; struct cvor { char token; veza d; /*desna grana*/ veza l; /*lijeva grana*/ }; /*kreiramo korijen stabla*/ veza korijen; /* kreiramo cvorove stabla */ veza new(char token, veza lijevi, veza desni){ veza x=(veza)malloc(sizeof *x); x->token=token; x->l=lijevi; x->d=desni; return x; } veza parsiraj(){ char t; veza x; ++i; if((t=a[i])==0) return NULL; /*jer smo dosli do kraja stringa*/ x=new(t, NULL, NULL); if(i==0) korijen=x; /*zapamtimo korijen*/ if((a[i]=='+')||(a[i]=='*')){ x->l=parsiraj(); x->d=parsiraj(); } return x; } /*ispisuje stablo*/ void ispisi(veza x, int nivo){ if(x){ printf("\nnivo=%d. cvor %c: ", nivo, x->token); if(x->l) printf("lijevi= %c; ", x->l->token); else printf("lijevi=NULL; "); if(x->d) printf("desni=%c; ", x->d->token); else printf("desni=NULL. "); ++nivo; if(x->l) ispisi(x->l, nivo); if(x->d) ispisi(x->d, nivo); } } int main(){ i=-1; /*kreiramo stablo */ parsiraj(); ispisi(korijen, 0); } Izvrsen ovaj program ispisuje na standardni output. nivo=0. cvor *: lijevi= +; desni=f; nivo=1. cvor +: lijevi= a; desni=*; nivo=2. cvor a: lijevi=NULL; desni=NULL. nivo=2. cvor *: lijevi= *; desni=+; nivo=3. cvor *: lijevi= b; desni=c; nivo=4. cvor b: lijevi=NULL; desni=NULL. nivo=4. cvor c: lijevi=NULL; desni=NULL. nivo=3. cvor +: lijevi= d; desni=e; nivo=4. cvor d: lijevi=NULL; desni=NULL. nivo=4. cvor e: lijevi=NULL; desni=NULL. nivo=1. cvor f: lijevi=NULL; desni=NULL. Ovaj ispis sadrzi dovoljno informacija da se rekonstruira stablo na slici.

4. Zadaci za DZ

1. Napisite svoju funkciju za ispis binarnog stabla na standardni output.

2. Napisite fukciju koji odredjuje broj listova stabla. Napisite i test program.

3. Napisite program koja ucitava binarno stablo stringova sa standardnog inputa, ispisuje na standardni output, te trazi broj pojavljivanja zadanog stringa u stablu.

4. Napisite program koji ucitava binarno stablo karaktera i u njemu brise sva pojavljivanja unaprijed zadanog karaktera kao lista stabla. Novo stablo se ispisuje na standardni output.

5. Napisite funkciju koja iz dane reprezentacije prefiks izraza u obliku stabla (kao u primjeru sa predavanja) ispisuje izraz na standardni output u infiks obliku sa minimalnim potrebnim brojem zagrada.