Arbori Binari.unlocked

Arbori Binari

Noiuni generale Se numete Arbore cu rdcin = graf neorientat conex fr cicluri n care unul din noduri este

desemnat ca rdcin. Nodurile pot fi aezate pe niveluri ncepnd cu rdcina care este plasat pe nivelul 1.

Rdcin = Nod special care genereaz aezarea unui arbore pe niveluri; Aceast operaie se efectueaz n funcie de lungimea lanurilor prin care celelalte noduri sunt legate de rdcin.

Descendent = ntr-un arbore cu rdcin nodul y este descendentul nodului x dac este situat pe un nivel mai mare dect nivelul lui x i exist un lan care le unete i nu trece prin rdcin.

Descendent direct / fiu = ntr-un arbore cu rdcin nodul y este fiul (descendentul direct) nodului x dac este situat pe nivelul imediat urmtor nivelului lui x i exist muchie ntre x i y.

Ascendent = ntr-un arbore cu rdcin nodul x este ascendentul nodului y dac este situat pe un nivel mai mic dect nivelul lui y i exist un lan care le unete i nu trece prin rdcin.

Ascendent direct / printe = ntr-un arbore cu rdcin nodul x este printele (ascendentul direct) nodului y dac este situat pe nivelul imediat superior (cu numr de ordine mai mic) nivelului lui y i exist muchie ntre x i y.

Frai = ntr-un arbore cu rdcin nodul x este fratele nodului y dac au acelai printe.

Frunz = ntr-un arbore cu rdcin nodul x este frunz dac nu are nici un descendent direct

Exemplu

- Nodul 1 este rdcin.

- Nodurile 5, 6, 7 sunt fii nodului 3.

- Nodul 7 este printele nodurilor 9 i 10;

- Nodul 9 este descendentul lui 3

- Nodul 3 este ascendentul lui 10

- Nodurile 8, 9 i 10 sunt frunze

- Nodurile 5, 6 i 7 sunt frai.

Arborii binari sunt un tip aparte de arbori, n care fiecare nod are maxim 2 copii. Pentru un nod dat, ntr-un arbore binar, vom avea copilul din stnga, i copilul din dreapta. Exemplu:

Arborele din figura a are 8 noduri, nodul 1 fiind rdcina. Acesta are ca i copil stnga nodul nr.2, iar ca i copil dreapta nodul nr.3. La rndul su nodul nr.2 are dect un copil(stnga), i anume nodul nr.4.

Deci un nod dintr-un arbore binar poate avea 2 copii (st i dr), un singur copil (doar st sau doar dr) sau nici unul (exemplu nodul 8).

Nodurile care nu au nici un copil se numesc noduri frunz.

Nodurile care au 1 sau 2 copii se numesc noduri interne.

Pentru reinerea informaiei n calculator se pot folosi 2 metode, static (vectori) sau dinamic.

Deoarece pentru fiecare nod n parte este necesar s se rein, pe lng informaia util i legturile cu nodurile copii (adresele acestora). Urmtoarea ar fi structura unui nod:

type Arbore=^Nod;

Nod=record

Info: string;

St,Dr: Arbore

end;

var T: Arbore; {rdcina}

n figura 1 este reprezentat un arbore binar n care rdcina este 1 (s-a renunat la orientarea arcelor, care sunt implicite deoarece se cunoate rdcina).

Observaii:

Nodurile sunt aezate pe mai multe niveluri

Rdcina este pe nivelul 0

Adncimea arborelui este egal cu numrul de niveluri-1. Arborele din figura 1 are 4 niveluri: nivel 0, nivel 1, nivel 2, nivel 3 i adncimea 3

Se face distincie ntre descendentul stng i cel drept

Pentru arborele din figura 1 cei doi vectori rein:

Vectorul stng:

Vectorul drept:

2 4 6 0 0 0 0 0

3 5 7 0 0 0 8 0

Crearea unui arbore binar (recursiv)function Arb_Creare: Arbore;{crearea arborelui binar}var R: Arbore;

s: string;beginreadln(s);if s='' then Arb_Creare:=nil

else beginnew(R);R^.Info:=s;writeln('Dati descendentul stang al nodului

',s,':');R^.St:=Arb_Creare;writeln('Dati descendentul drept al nodului

',s,':');R^.Dr:=Arb_Creare;Arb_Creare:=R;

end;end; {Arb_Creare}

Afiarea unui arbore binar (recursiv)procedure Arb_Afis(T: Arbore; nivel: integer);

{afisarea arborelui binar}

var i: integer;

begin

if Tnil then begin

Arb_Afis(T^.St, nivel+1);

for i:=1 to nivel do

write(' ');

writeln(T^.Info);

Arb_Afis(T^.Dr, nivel+1);

end;

end; {Arb_Afis}

Crearea i afiarea unui arbore binar (recursiv)Program P130;{Crearea unui arbore binar -recursie}type Arbore=^Nod;

Nod=recordInfo: string;St,Dr: Arbore

end;var T : Arbore; {radacina}function Arb_Creare: Arbore;{crearea arborelui binar}

var R: Arbore;s: string;

beginreadln(s);if s='' then Arb_Creare:=nil

else beginnew(R);R^.Info:=s;writeln('Dati descendentul

stang al nodului ',s,':');R^.St:=Arb_Creare;writeln('Dati descendentul

drept al nodului ',s,':');R^.Dr:=Arb_Creare;Arb_Creare:=R;

end;end; {Arb_Creare}procedure Arb_Afis(T: Arbore; nivel: integer);{afisarea arborelui binar}

var i: integer;begin

if Tnil then beginArb_Afis(T^.St, nivel+1);for i:=1 to nivel do

write(' '); writeln(T^.Info);Arb_Afis(T^.Dr, nivel+1);

end;end; {Arb_Afis}begin

writeln('Dati radacina:');T:=Arb_Creare;Arb_Afis(T, 0);readln;

end.

Funcia Arb_Creare citete de la tastatur informaia util, dac se introduce un ir vid nu se creeaz nciun nod.

Dati radacina:1Dati descendentul stang al nodului 1:2Dati descendentul stang al nodului 2:4Dati descendentul stang al nodului 4:

Dati descendentul drept al nodului 4:

Dati descendentul drept al nodului 2:5Dati descendentul stang al nodului 5:


Dati descendentul drept al nodului 1:3

Dati descendentul stang al nodului 3:6Dati descendentul stang al nodului 6:




42

51

63

7

Parcurgerea arborilor binari

1. Parcurgerea n inordine (stnga rdcina dreapta SRD) se parcurgemai nti subarborele stng, apoi rdcina, apoi subarborele drept.

2. Parcurgerea n preordine (rdcina stnga dreapta RSD) se parcurgemai nti rdcina, apoi subarborele stng, apoi subarborele drept.

3. Parcurgerea n postordine (stnga dreapta rdcina SDR) se parcurgemai nti subarborele stng, apoi subarborele drept i la sfrit rdcina.

Exemplu

parcurgere svd - n inordine4 2 5 1 6 3 7 8

parcurgere vsd - n preordine1 2 4 5 3 6 7 8

parcurgere sdv - n postordine4 5 2 6 8 7 3 1

Parcurgere RSD (preordine)

procedure RSD(T: Arbore);

{traversare RSD}

begin

if Tnil then begin

writeln(T^.Info);

RSD(T^.St);

RSD(T^.Dr)

end;

end; {RSD}

Parcurgere SRD (inordine)

procedure SRD(T: Arbore);

{traversare Inordine}

begin

if Tnil then begin

SRD(T^.St);

writeln(T^.Info);

SRD(T^.Dr)

end;

end; {SRD}

Parcurgere SDR (postordine)

procedure SDR(T: Arbore);

{traversare Postordine}

begin

if Tnil then begin

Postordine(T^.Stg);

Postordine(T^.Dr);

writeln(T^.Info)

end;

end; {SDR}

Program P131;{Parcurgerea arborelui binar}type Arbore=^Nod;Nod=recordInfo: string;St,Dr: Arbore

end;var T : Arbore; {radacina}function Arb_Creare: Arbore;{crearea arborelui binar}var R: Arbore;

s: string;beginreadln(s);if s='' then Arb_Creare:=nil

else beginnew(R);R^.Info:=s;writeln('Dati

descendentul stang al nodului ',s,':');

R^.St:=Arb_Creare;writeln('Dati

descendentul drept al nodului

',s,':');R^.Dr:=Arb_Creare;Arb_Creare:=R;

end;end; {Arb_Creare}procedure Arb_Afis(T: Arbore; nivel: integer);{afisarea arborelui binar}var i: integer;begin

if Tnil then beginArb_Afis(T^.St,

nivel+1);for i:=1 to nivel do

write(' '); writeln(T^.Info);Arb_Afis(T^.Dr,

nivel+1);end;

end; {Arb_Afis}

procedure RSD(T: Arbore);{parcurgere Preordine}begin

if Tnil then beginwriteln(T^.Info);RSD(T^.St);RSD(T^.Dr)

end;end; {RSD}procedure SRD(T: Arbore);{parcurgere Inordine}begin

if Tnil then beginSRD(T^.St);writeln(T^.Info);SRD(T^.Dr)

end;end; {SRD}procedure SDR(T: Arbore);{parcurgere Postordine}begin

if Tnil then beginSDR(T^.St);SDR(T^.Dr);

writeln(T^.Info)end;

end; {SDR}beginwriteln('Dati radacina:');T:=Arb_Creare;Arb_Afis(T, 0);readln;writeln('Parcurgere in preordine:');RSD(T);readln;writeln('Parcurgere in inordine:');SRD(T);readln;writeln('Parcurgere in postordine:');SDR(T);end.

Dati radacina:1Dati descendentul stang al nodului 1:2Dati descendentul stang al nodului 2:4Dati descendentul stang al nodului 4:




Dati descendentul drept al nodului 1:3Dati descendentul stang al nodului 3:6Dati descendentul stang al nodului 6:





42

51

63

78

Parcurgere in preordine:12453678

Parcurgere in inordine:42516378

Parcurgere in postordine:45268731

1. Elaborai un program care construiete arborele genealogic propriu a 3 sau 4 generaii. Nodul-rdcin conine numele, penumele i anul naterii, iar nodurile descendente conin datele despre prini.

2. Elaborai o procedur recursiv care parcurge un arbore binar n ordinea:

RDS (rdcin subarborele drept subarborele stng)

DRS (subarborele drept rdcin subarborele stng)

DSR (subarborele drept subarborele stng rdcin)

Arbori Binari.unlocked

Documents

Transcript of Arbori Binari.unlocked