Articolele lui Candale Silviu (silviu)

Înlănțuire

Înlănțuirea metodelor (method chaining) este un stil de programare ce poate fi utilizat în contextul programării orientate pe obiecte. Constă în faptul că metodele vor avea ca rezultat obiecte. În acest mod apelurile metodelor pot fi înlănțuite într-o singură instrucțiune, evitând declararea unor variabile care să stocheze rezultate intermediare.

Cascadarea

O situație particulară este cascadarea metodelor. Constă în faptul că metodele returnează tocmai obiectul curent (instanța curentă). Astfel apelurile lor sunt înlănțuite, făcând programul ușor de înțeles și evitând “efortul” necesar pentru alegerea unor nume pentru variabile.

Cascadarea metodelor este posibilă în C++ datorită pointerului this – pointer la obiectul curent. Pentru a realiza cascadarea trebuie îndeplinite următoarele:

• tiplul metodei este referință la clasa curentă;
• metoda returnează obiectul curent prin dereferențierea pointerului this, adică * this.

Exemple

Operatorul <<

Un exemplu C++ binecunoscut este operatorul de inserție în flux <<, care are ca rezultat obiectul din stânga. Acest fapt permite scrie unei instrucțiuni de forma:

cout << a << " " << b;

Ea este echivalentă cu următoarea secvență:

cout << a;
cout << " ";
cout << b;

sum00

Programul de mai jos este o rezolvare pentru problema #sum00 (suma a două numere):

#include <iostream>

using namespace std;

class T{
    private:
        int a , b;
    public:
        T & Citire(){
            cin >> a >> b;
            return * this;
        }
        T & Suma(){
            cout << a + b;
            return * this;
        }
};

int main()
{
    T().Citire().Suma();
    return 0;
}

Cascadare vs. înlănțuire

Considerăm următoarele două clase:

class A{
    private:
        int n;
    public:
        A & Citire(){
            cin >> n;
            return * this;
        }
        A & Afisare(){
            cout << n << endl;
            return * this;
        }

        A & Dublare(){
            n *= 2;
            return * this;
        }
};

class B{
    private:
        int n;
    public:
        B Citire(){
            cin >> n;
            return * this;
        }
        B Afisare(){
            cout << n << endl;
            return * this;
        }

        B Dublare(){
            n *= 2;
            return * this;
        }
};

Ele diferă doar prin faptul că metodele clasei A returnează însuși obiectul curent, în timp ce metodele clasei B returnează o copie a obiectului curent.

Următoarele două secvențe vor afișa același lucru, deși mecanismele sunt diferite:

A().Citire().Dublare().Afisare();

B().Citire().Dublare().Afisare();

Diferențele sunt vizibile în următoarele exemple:

A x;
x.Citire().Dublare();
x.Afisare();

B y;
y.Citire().Dublare();
y.Afisare();

Generalități

Cuvântul polimorfism se referă la proprietatea unor substanțe, ființe, obiecte de a avea mai multe forme.

În contextul programării orientate pe obiecte, polimorfismul se referă la posibilitatea claselor de a avea mai multe metode cu același nume, dar cu efecte și rezultate diferite.

Supraîncărcarea funcțiilor și operatorilor sunt tratate în acest articol: www.pbinfo.ro/articole/25851/supraincarcarea-functiilor-si-a-operatorilor.

Suprascrierea funcțiilor

Suprascrierea funcțiilor (overriding) se referă la situația ca într-o ierarhie de clase să avem metode cu același nume, dar cu efecte diferite. Considerăm clasele Animal și Caine.

#include<iostream>

using namespace std;

class Animal{
	public:
		void vorbeste()
		{
			cout << "Animalul vorbeste." << endl;
		}
};

class Caine: public Animal{
	public:
		void vorbeste()
		{
			cout << "Cainele latra." << endl;
		}
};

int main(){
	Caine C;
	Animal A;
	C.vorbeste();
	A.vorbeste();
	C.Animal::vorbeste();
	// A.Caine::vorbeste(); // imposibil
}

În exemplul anterior:

• clasa Caine este derivată din clasa Animal;
• obiectul C este de tip Caine, obiectul A este de tip Animal; ambele sunt obiecte statice;
• metoda vorbeste() este disponibilă în ambele clase, fiind suprascrisă în clasa derivată
• putem accesa corespunzător pentru fiecare obiect propria metoda vorbeste()
• pentru obiectul derivat putem accesa metoda clasei de bază folosind operatorul de rezoluție: C.Animal::vorbeste(); – invers nu este posibil!

Constatăm că pentru obiectele referite static accesarea metodelor suprascrise este rezolvată elegant, putând accesa orice metodă disponibilă în obiectul curent (proprie obiectului curent sau proprie aflate mai “sus” în ierarhie).

Suprascrierea în cazul pointerilor

Să vedem cum putem accesa membri claselor de bază/derivată în cazul pointerilor. Folosind clasele definite mai sus, considerăm următorul exemplu:

Caine C;
Animal A;
Animal * p;
p = & A;
p->vorbeste(); // Animalul vorbeste.
p = & C;
p->vorbeste(); // Animalul vorbeste. (?!?)

Caine * q;
q = & C;
q->vorbeste();
// q = & A; // imposibil

Constatăm că:

• pointerul la clasa derivată (q) poate memora doar adresa unui obiect al acesteia;
• pointerul la clasa de bază (p) poate memora atât adresa unui obiect al clasei de bază, cât și adresa unui obiect al clasei derivate;
• chiar dacă pointerul memoreaza adresa unui obiect al clasei derivată, prin acel pointer se accesează metode ale clasei de bază!

Funcții virtuale

C++ oferă un mecanism prin care se alege metoda accesată printr-un pointer dinamic, la execuția programului, în funcție de clasa din care face obiectul referit de pointer (de bază sau derivată). Acest mecanism este reprezentat de funcțiile virtuale.

Declararea unei funcții (metode) virtuale este precedată de cuvântul C++ rezervat virtual în clasa de bază:

virtual tipRezultat metoda(parametri)

Exemplu:

#include<iostream>

using namespace std;

class Animal{
	public:
		virtual void vorbeste()
		{
			cout << "Animalul vorbeste." << endl;
		}
};

class Caine: public Animal{
	public:
		void vorbeste()
		{
			cout << "Cainele latra." << endl;
		}
};

int main(){
	Caine C;
	Animal A;
	Animal * p;
	p = & A;
	p->vorbeste(); // Animalul vorbeste.
	p = & C;
	p->vorbeste(); // Cainele latra. (!)
}

Constatăm că:

• p este declarat pointer la clasa de bază;
• p poate memora fie adresa unui obiect din clasa de bază, fie adresa unui obiect din clasa derivată;
• se apelează metoda corespunzătoare clasei din care face parte obiectul referit de pointer!

Încapsularea presupune și ascunderea datelor sensibile ale unui obiect. Acest lucru este necesar din cel puțin două motive:

• datele membre ale obiectului trebuie să fie consistente. De exemplu:
  • varsta unei persoane poate fi cel puțin 0, într-un interval cunoscut – nu putem avea 157 sau 1204578 de ani!
  • numitorul unei fracții trebuie să fie strict pozitiv, iar fracția trebuie să fie ireductibilă.
• obiectul este o cutie neagră. Utilizatorii săi nu-i cunosc structura internă, ci doar metodele publice prin care poate fi manipulat!

Astfel, datele membru ale unui clase sunt declarate private. Acest lucru duce la respectarea regulilor de mai sus, dar conduce totodată și la imposibilitatea de a vedea din afara clasei care este valoare unei date membru private sau de a o schimba. Aceste operații pot fi făcute prin intermediul metodelor GET și SET (getter-e și setter-e).

Definiții

O metodă GET este o metodă publică a clasei care returnează valoarea ueni date membru private.

O metodă SET este o metodă publică a clasei care atribuie unei date membru private o anumită valoare.

Observații

• getter-ele și setter-erele sunt metode publice;
• ele nu există de la sine, trebuie implementate;
• setter-ele trebuie să valideze valoarea pe care o atribuie datei private și totodată să realizeze anumite prelucrări asupra obiectului, dacă sunt necesare;
• nu există reguli stricte privind numele metodelor GET și SET. O convenție frecventă este următoarea:
  • numele metodei lor să fie similar cu cel al datei private pe care o citește/scrie, de regulă scris cu majusculă:
  • metoda GET nu are parametri și returnează valoarea datei private corespunzătoare;
  • metoda SET are ca parametru noua valoare, iar rezultatul este void sau este obiectul curent, pentru a putea înlănțui apelul metodelor.

Exemplu

În exemplul de mai jos implementăm clasa Fractie, înzestrând-o cu metode GET și SET. Folosim aceste metode la scrierea unei funcții care determină suma a două fracții.

#include <iostream>

using namespace std;

class Fractie{
	private:
		int numarator, numitor;	// proprietăți
		void Simplifica();		// metodă privată
	public:
		Fractie(int _numarator = 0, int _numitor = 1); // constructor
		Fractie(const Fractie &);	// constructor de copiere
		Fractie & Citeste();	//	metodă publică
		Fractie & Scrie();		// metodă publică
		// metode GET
		int Numarator();
		int Numitor();
		// metode SET
		Fractie & Numarator(int);
		Fractie & Numitor(int);
};

Fractie::Fractie(const Fractie & F)
{	// constructor de copiere
	numarator = F.numarator;
	numitor = F.numitor;
	Simplifica();
}

Fractie::Fractie(int _numarator /* = 0 */, int _numitor /* = 1 */)
{	// constructor
	numitor = _numitor, numarator = _numarator;
	Simplifica();
}

int Fractie::Numarator()
{
	//metoda GET
	return numarator;
}

int Fractie::Numitor()
{
	//metoda GET
	return numitor;
}

Fractie & Fractie::Numarator(int x)
{
	numarator = x;
	Simplifica();
	return * this;
}

Fractie & Fractie::Numitor(int x)
{
	// validam valoarea lui x
	if(x == 0)
	{
		cerr << "Numitor nul" << endl;
		return * this;
	}
	numitor = x;
	if(x < 0)
		numarator *= -1, numitor *= -1;
	Simplifica();
	return * this;
}

Fractie & Fractie::Citeste()
{
	// citeste numaratorul si numitorul obiectului curent
	// returnează obiectul curent
	int a , b;
	cin >> a >> b;
	// validam valorile citite
	if(b == 0)
	{
		cerr << "Numitor nul"<<endl;
		return * this;
	}
	if(b < 0)
		a = -a , b = -b;
	numarator = a, numitor = b;
	Simplifica();
	return * this;
}

Fractie & Fractie::Scrie()
{
	// afisează numaratorul si numitorul obiectului curent
	// returnează obiectul curent
	cout << numarator << " " << numitor <<endl;
	return * this;
}

void Fractie::Simplifica()
{	//metoda privata; realizeaza simplificarea fractiei merorate în obiectul curent
	int a = abs(numarator), b = abs(numitor);
	while(b)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	numarator /= a;
	numitor /= a;
}

Fractie Suma(Fractie F, Fractie G)
{
	// funcție oarecare. Accesam datele private ale obiectelor prin metodele GET si SET
	int x = F.Numarator() * G.Numitor() + F.Numitor() * G.Numarator(),
		y = F.Numitor() * G.Numitor();
	Fractie R; 
	R.Numarator(x).Numitor(y); // apelam metodele SET
	return R; // s-a apelat costructorul de copiere
}

int main()
{
	Fractie a , b;
	a.Citeste(), b.Citeste();
	Suma(a , b).Scrie();
	return 0;
}

Introducere

Derivarea claselor (moștenirea) este unul dintre principiile fundamentale ale programării orientate pe obiecte. Ne permite să definim o clasă pornind de la altă clasă, creată anterior, și facilitează crearea și întreținerea aplicațiilor. Tototdată permite reutilizarea codului și micșorează timpul de implementare a programelor.

La crearea unei clase, în loc să scriem date și funcții membre complet noi, putem să precizăm că noua clasă va moșteni membri unei clase existente. Se obțin astfel ierarhii de clase.

Moștenirea are sens numai când obiectele din clasa moștenită fac parte din obiectele clasei de bază – relația dintre ele este de tipul Is A (este un/o). De exemplu:

• paralelogramul este un patrulater. Clasa Paralelogram poate fi derivată din clasa Patrulater.
• câinele este un animal. Clasa Caine poate fi derivată din clasa Animal.

Terminologie

Fie B o clasă care există deja, iar D clasa care moștenește membrii clasei B. Spunem că:

• B este clasa de bază;
• D este clasa derivată;
• clasa D s-a obținut prin derivarea clasei B;
• clasa B a fost derivată și s-a obținut clasa D;
• clasa D moștenește clasa B;
• relația de moștenire se reprezintă prin următoarea diagramă:
  

În C++, o clasă poate fi derivată pornind de la mai multe clase de bază. Totodată, specificatorii de acces cunoscuți (public, private, protected) sunt folosiți și pentru a preciza modul în care se face derivarea. Efectul lor este legat de vizibilitatea membrilor clasei de bază în clasa derivată.

Derivarea unei clase

Cea mai simplă formă de derivarea a unei clase este prezentată mai jos:

class D: public B{
	// membri noi ai clasei derivate
}

Observații:

• clasa B este clasa de bază, care trebuie să fie deja definită;
• clasa D este clasa derivată;
• specificatorul de acces folosit în exemplu, public, face ca:
  • membrii public din clasa de bază B rămân public și în clasa derivată D – pot fi accesați din afara clasei D;
  • membrii protected din clasa de bază B rămân protected și în clasa derivată D – pot fi accesați din clasa derivata D și vor putea fi acesați din alte clase vor moșteni clasa D;
  • membrii private din clasa de bază B nu pot fi accesați din clasa derivată D;
• la definiția clasei derivate, în loc de public putem folosi private sau protected. Semnificația lor va fi discutată ceva mai târziu!

Exemplu

#include<iostream>

using namespace std;

class Animal{
	private:

	protected: 
		int varsta;
	public:
		Animal(){
			varsta = 0;
			cout << "S-a nascut un animal." << endl;
		}
		~Animal(){
			cout << "Animalul a murit." << endl;
		}
		void creste()
		{
			++ varsta;
			cout << "Animalul are " << varsta << (varsta == 1 ? " an":" ani") << endl;
		}
};

class Caine: public Animal{
	public:
		Caine(){
			cout << "S-a nascut un caine." << endl;
		}
		~Caine(){
			cout << "Cainele a murit." << endl;
		}
		void latra()
		{
			for(int i = 1 ; i <= varsta ; i ++)
				cout << "Ham " ;
			cout << endl;
		}
		void creste()
		{
			++ varsta;
			cout << "Cainele are " << varsta << (varsta == 1 ? " an":" ani") << endl;
		}
};

int main(){
	Caine X;
	X.creste(); 
	X.Animal::creste();
	X.latra(); 
	X.creste();
	X.latra();
}

S-a nascut un animal.
S-a nascut un caine.
Cainele are 1 an
Animalul are 2 ani
Ham Ham 
Cainele are 3 ani
Ham Ham Ham 
Cainele a murit.
Animalul a murit.

Observații

• Animal este clasa de bază, iar Caine este clasa derivată;
• din clasa derivată (metoda latra()) am accesat proprietatea varsta din clasa de bază:
  • acest lucru a fost posibil deoarece proprietatea varsta a fost declarată protected
  • dacă ar fi fost declarată private, nu putea fi accesată din clasa derivată
• din exterior – funcția main(), pentru obiectul X de tip Caine am accesat:
  • metoda latra(), disponibilă doar în clasa derivată;
  • metoda creste(), moștenită din clasa de bază;
  • ambele metode sunt publice în clasa derivată;
• ambele clase sunt înzestrate cu constructori și destructori:
  • în cazul constructorului, mai întâi se apeleaza cel al clasei de bază, apoi cel al clasei derivate;
  • în cazul destructorului, ordinea este inversă;
• dacă în clasa de bază și în clasa derivată avem doi membri cu același nume (overriding), prioritate are cel din clasa derivată. Pentru a-l accesa pe cel din clasa de bază vom folosi operatorul de rezoluție:
  

  X.creste(); // Cainele are 1 an
  
  X.Animal::creste(); // Animalul are 2 ani

• în exemplul de mai jos se evidențiază modul în care se poate face atribuirea între o variabilă de tipul clasei de bază și una de tipul clasei derivate:
  

  int main(){
  	Caine X;
  	X.creste();  // Cainele are 1 an
  	X.latra();	 // Ham
  	Animal A;
  	A = X;
  	A.creste();	// Animalul are 2 ani
  	// X = A; eroare de sintaxă
  
  }

  
  A este de tipul Animal (clasa de bază), iar X este de tipul Caine (clasa derivată). Atunci:
  • atribuirea A = X; este corectă. În A se vor copia doar membri din X care fac parte din clasa de bază.
  • atribuirea X = A; nu este corectă. Clasa derivată conține și membri care nu aparțin clasei de bază, ce nu pot fi inițializați prin această atribuire!

Accesul la membrii claselor derivate

Accesul la membrii (date sau funcții) clasei de bază în clasa derivată se face în funcție de regulile de acces la membrii clasei de bază și în funcție de modalitatea în care s-a făcut derivarea.

Sunt trei moduri de declarare a membrilor unei clase:

• publici – public – pot fi accesați din afara clasei, dar și din interiorul ei
• protejati – protected – nu pot fi accesați din exteriorul clasei (de bază sau derivate). Pot fi accesați din interiorul clasei de bază și din interiorul claselor derivate
• privați – private – pot fi accesați numai din interiorul clasei.

Modalitățile de derivarea ale unei clase sunt:

• derivare publică:
  

  class D: public B{ … }

  • membrii publici ai clasei B rămân publici și în clasa D;
  • membrii protejați al clasei B rămân protejați în clasa D;
  • membrii privați ai clasei B sunt inaccesibili în clasa D;
• derivare protejată:
  

  class D: protected B{ … }

  • membrii publici ai clasei B devin protejați și în clasa D;
  • membrii protejați al clasei B rămân protejați în clasa D;
  • membrii privați ai clasei B sunt inaccesibili în clasa D;
• derivare privată:
  

  class D: private B{ … }

  • membrii publici ai clasei B devin privați și în clasa D;
  • membrii protejați al clasei B devin privați în clasa D;
  • membrii privați ai clasei B sunt inaccesibili în clasa D;

Generalități

Supraîncărcarea funcțiilor (eng. functions overloading) se referă la posibilitatea ca în același program să fie declarate și definite mai multe funcții cu același nume, care să difere prin parametri. La apelul unei funcții supraîncărcate, compilatorul stabilește care dintre declarații se potrivește cu apelul respectiv, comparând numărul și tipul parametrilor actuali cu cel al parametrilor formali.

Metodele unei clase, fiind funcții, pot fi supraîncărcate. Totodată, în interiorul unei clase pot fi definiți și supraîncărcați operatori (+, -, *, etc.), care permit utilizarea naturală a obiectelor, în raport cu înțelesul lor.

De exemplu, fracțiile pot fi adunate, scăzute, etc. O clasa care implementează fracții poate fi îmbogățită cu operațiile naturale de adunare, scădere, înmulțire, împărțire, dar și cu comparații, incrementări/decrementări, citire, afișare, etc.

În acest fel lucrul cu obiecte devine natural, evitând apelul explicit al unor metode care poate părea forțat, în anumite situații.

Supraîncărcarea metodelor

De știut:

• în definiția unei clase putem avea mai multe metode cu același nume;
• ele trebuie să difere prin numărul și tipul parametrilor, nu prin tipul rezultatului;
• nu se pot supraîncărca funcții care diferă numai prin tipul rezultatului!

Exemplu

În exemplul următor, definim pentru clasa Fracție două metode creste():

• una fără parametri, care va mări valoarea fracției încapsulate în obiect cu 1;
• una cu un parametru întreg n, care va mări valoarea fracției încapsulate în obiect cu n.

#include <iostream>

using namespace std;

class Fractie{
    private:
        int numarator, numitor;
    public:
		void afiseaza() /// metodă pentru afișarea fractiei
		{
			cout << numarator << "/" << numitor << endl;
		}
		Fractie(int a , int b) /// constructor
		{
			if(b < 0)
				a = -a, b = -b;
			numarator = a, numitor = b;
		}
		Fractie & creste()
		{
			numarator += numitor;
			return *this;
		}
		Fractie & creste(int n)
		{
			numarator += n * numitor;
			return *this;
		}
};

int main(){
	Fractie x(1 , 4);
	x.afiseaza();
	x.creste();
	x.afiseaza();
	x.creste(3);
	x.afiseaza();
	return 0;
}

Programul de mai sus va afișa:

1/4
5/4
17/4

Supraîncărcarea operatorilor

Putem supraîncărca aproape toți operatorii C++ predefiniți. În acest mod putem folosi operatorii și pentru tipurile definite de noi, nu doar pentru cele predefinite.

Nu putem supraîncărca operatori pentru tipurile de bază: int, double, etc.

Nu putem supraîncărca operatori care nu există. De exemplu, nu putem adăuga operatorul #.

Nu putem schimba prioritatea operatorilor.

Operatorii sunt funcții cu un nume special: cuvântul rezervat operator, urmat de simbolul operatorului pe care îl definim. La fel ca orice altă funcție, și operatorii au tip al rezultatului și listă de parametri.

Operatorii care pot fi supraîncărcați sunt:

• +, -, *, /, %
• ^, &, |, ~,
• ,
• =
• <, >, <=, >=, ==, !=,
• !, &&, ||
• ++, --
• <<, >>,
• +=, -=, /=, %=, ^=, &=, |=, *=, <<=, >>=,
• [], ()
• ->, ->*
• new, new [], delete, delete []

Următorii operatori nu pot fi supraîncărcați:

• ::, .*, ., ?:

Sunt două modalități de defini operatori pentru o clasă:

• prin intermediul metodelor;
• prin intermediul funcțiilor prietene.

Putem folosi metodele când operatorul este unar, sau când este binar și primul operand este obiect al clasei pentru care definim operatorul. Dacă operatorul este binar și primul operator nu este obiect al clasei, vom defini operatorul prin intermediul funcțiilor prietene.

Exemplu

În programul de mai jos definim o clasă Fractie în care vom defini și supraîncărca operatorul + pentru a implementa adunarea fracțiilor și adunarea fracțiilor cu întreg. Distingem următoarele cazuri:

• operația F + G, unde F și G sunt fracții, poate fi implementată atât printr-o metodă cât și ca funcție prietenă;
• operația F + n, unde F este fracție și n este număr întreg, poate fi implementată atât printr-o metodă cât și ca funcție prietenă;
• operația n + F, unde F este fracție și n este număr întreg, va fi implementată printr-o funcție prietenă.

Situația de mai sus se datorează faptului că, la implementarea operatorului ca metodă, obiectul curent, pentru care se implementează metoda, este primul operand.

#include <iostream>

using namespace std;

class Fractie{
    private:
        int numarator, numitor;
    public:
		void afiseaza() /// metodă pentru afișarea fractiei
		{
			cout << numarator << "/" << numitor << endl;
		}
		Fractie(int a = 0, int b = 1) /// constructor
		{
			if(b < 0)
				a = -a, b = -b;
			numarator = a, numitor = b;
		}
		Fractie operator+ (Fractie F)
		{
			Fractie R;
			R.numarator = numarator * F.numitor + numitor * F.numarator;
			R.numitor = numitor * F.numitor;
			return R;
		}
		Fractie operator+ (int n)
		{
			Fractie R;
			R.numarator = numarator + n * numitor;
			R.numitor = numitor;
			return R;
		}
		friend Fractie operator + (int n, Fractie F)
		{
			Fractie R;
			R.numarator = F.numarator + n * F.numitor;
			R.numitor = F.numitor;
			return R;
		}
};

int main(){
	Fractie X(1 , 4), Y(2, 3);
	Fractie R = X + Y;
	R.afiseaza();
	R = X + 2;
	R.afiseaza();
	R = 2 + X;
	R.afiseaza();
	return 0;
}

Programul de mai sus va afișa:

11/12
9/4
9/4

Înmulțirea a la russe

Considerăm următorul algoritm, aplicat pentru două numere naturale a și b:

R ← 0
┌ cattimp a ≠ 0 executa
│   ┌ daca a este impar atunci
│   │   R ← R + b
│   └■
│   a ← [a / 2]
│   b ← b * 2
└■
scrie R

Dacă îl vom aplica pentru a = 18 și b = 12 vom constata că:

Observăm că rezultatul R = 216 este de fapt chiar 18 * 12. Aceasta nu este o coincidență!

Algoritmul determină rezultatul înmulțirii dintre a și b și se numește înmulțirea a la russe (înmulțirea rusească). În ciuda numelui, se pare că metoda era cunoscută în Egiptul Antic și poate fi descrisă astfel:

• înmulțim numerele a și b:
  1. dacă a este impar, il adunăm pe b la rezultat, care inițial este 0;
  2. a se înjumătățește, iar b se dublează;
  3. continuăm pași 1 și 2 până când a devine 0.

Aparent ciudată, metoda se bazează de fapt pe scrierea unui număr ca sumă de puteri ale lui 2 ( sau reprezentarea numerelor în baza 2) – știm că orice număr natural are o unică reprezentare în baza 2, poate fi scris în mod unic ca sumă de puteri ale lui 2.

Să-l scrie pe \(a = 18\) ca sumă de puteri ale lui 2: \(18 = 2 + 16 = 0 \cdot 2^0 + 1 \cdot 2^1 + 0 \cdot 2^2 + 0 \cdot 2^3 + 1 \cdot 2^4\). 0 1 0 0 1 sunt cifrele reprezentării lui 18 în baza 2, în ordine inversă (ordinea în care sunt determinate, prin metoda cunoscută ca resturi ale împărțirii la 2).

Atunci:
$$\begin{align} 18 \cdot 12 & = \left(0 \cdot 2^0 + 1 \cdot 2^1 + 0 \cdot 2^2 + 0 \cdot 2^3 + 1 \cdot 2^4 \right) \cdot 12 \\ & = \left(0 \cdot 1 + 1 \cdot 2 + 0 \cdot 4 + 0 \cdot 8 + 1 \cdot 16 \right) \cdot 12 \\ & = 0 \cdot 12 + 1 \cdot 24 + 0 \cdot 48 + 0 \cdot 96 + 1 \cdot 192 \\ & = 24 + 192 \\ & = 216 \\
\end{align}$$

Observăm deci că valorile care se adună pentru a obține rezultatul sunt tocmai acele valori obținute prin dublările succesive ale lui b când a este impar – ceea ce corespunde cifrei binare 1!!

Acest modalitate de înmulțire este interesantă, dar nu este neapărat utilă în practică. Mult mai interesant este următorul algoritm pentru ridicarea la putere, care poate fi utilizat în rezolvarea de probleme de informatică.

Ridicarea la putere rapidă

Să considerăm \(A^{25}\). Îl vom scrie pe \(25\) ca sumă de puteri ale lui \(2\): \(25 = 1 + 8 + 16\).

Atunci \( A^{25} = A^{1 + 8 + 16} = A^1 \cdot A^8 \cdot A^{16} = \underbrace{{(A^1)}^1}_{=A^1} \cdot \underbrace{{(A^2)}^0}_{=1} \cdot \underbrace{{(A^4)}^0}_{=1} \cdot \underbrace{{(A^8)}^1}_{=A^8} \cdot \underbrace{{(A^{16})}^1}_{=A^{16}}\). Observăm, desigur, că exponenții \(0\) și \(1\) sunt cifrele reprezentării în baza \(2\) a lui \(25\).

Pentru a determina An procedăm astfel:

• vom determina un produs P, format din factori de forma A1, A2, A4, A8, …
• determinăm cifrele reprezentării în baza 2 a lui n, începând cu cea mai nesemnificativă:
  • dacă cifra curentă este 1, înmulțim pe A la P, P ← P * A;
  • înmulțim pe A cu el însuși, A ← A * A;, obținând următoarea putere din șirul de mai sus

Următorul program pseudocod descrie algoritmul de mai sus:

citeste A,n (baza, exponent)
P ← 1
┌ cattimp n ≠ 0 executa
│   c ← n % 2
│   ┌ daca c = 1 atunci
│   │   P ← P * A
│   └■
│   n ← [n / 2]
│   A ← A * A
└■
scrie P

Observăm că algoritmul este foarte eficient! Numărul de iterații este egal cu numărul de cifre din reprezentarea în baza 2 a lui n – mult mai mic decât n!

Definiție

Definiție: Se numește arbore binar de cautare un arbore binar în care fiecare nod are o cheie unică de identificare care respectă următoarele condiții:

• pentru orice subarbore, cheile nodurilor din subarborele stâng sunt mai mici decât cheia rădăcinii;
• pentru orice subarbore, cheile nodurilor din subarborele drept sunt mai mari decât cheia rădăcinii.

Exemplu

Observații:

• Conform definiției, cheile asociate nodurilor dintr-un arbore binar de căutare nu se pot repeta. Dacă se dorește repetarea lor, definiția trebuie modificat încât în subarborele drept (sau stâng) cheile să poată fi și egale cu cheia rădăcinii.
• În practică informația utilă din nodurile arborelui poate fi de orice tip, cu condiția să conțină și cheia. Pentru simplitate, în cele ce urmează informatia utilă va consta exclusiv în cheia de identificare.
• În cele ce urmează vom folosi reprezentarea dinamică a arborilor binari, prin referințe descendente. Structura C++ folosită pentru nodurile arborelui este cea uzuală:
  

  struct nod{
  	int info;
      nod * st, * dr;
  
  };
  
  

Proprietăți

• Parcurgerea în inordine a nodurilor unui arbore binar de căutare se face în ordinea crescătoare a cheilor.
• Operațiile uzuale cu un arbore binar de căutare sunt:
  • inserarea unui nod nou
  • căutarea unui nod
  • ștergerea unui nod
  • parcurgerea nodurilor din arbore
• Căutarea unui nod care o cheie precizată se realizează destul de repede, deoarece, dacă rădăcina nu corespunde cheii date, căutarea va continua doar în unul dintre subarbori – stâng sau drept, în funcție de relația dintre cheia dată și cheia corespunzătoare rădăcinii.

Operații cu arborii binari de căutare

Așa cum ma văzut mai sus, principalele operații sunt:

• inserarea unui nod nou;
• căutarea unei valori;
• ștergerea unui nod;
• parcurgerea nodurilor din arbore (traversarea arborelui).

În implementarea acestor operații vom folosi metoda divide-et-impera. Principiul este:

• prelucrăm rădăcina;
• parcurgem subarborele stâng și/sau subarborele drept.

Inserarea

Se cunoaște adresa rădăcinii unui arbore binar de căutare (sau NULL dacă arborele este vid) și o valoare. Se cere să se insereze în arbore un nod care are drept cheie de identificare valoarea dată.

Inserarea trebuie realizată astfel încât să se păstreze proprietatea specifică arborilor binari de căutare!

Procedăm astfel:

• dacă arborele este nevid:
  • dacă valoarea dată este identică cu cheia rădăcinii se renunță la inserare;
  • dacă valoarea dată este mai mică decât cheia rădăcinii, se continuă cu subarborele stâng;
  • dacă valoarea dată este mai mare decât cheia rădăcinii, se continuă cu subarborele drept;
• dacă arborele este vid:
  • se creează un nod nou care având cheia egală cu valoarea dată și descendenți stâng și drept NULL. Legarea nodului la subarbore se face automat, datorită transmiterii prin referință a parametrului care reprezintă adresa rădăcinii.

Pentru a creea un arbore binar de căutare vom porni de la un arbore vid și vom aplica în mod repetat operația de inserare.

Funcție C++

void Inserare(nod * & R, int x)
{
	if(R != NULL)
    {
    	if(R->info == x)
        	return;
        else
        	if(R->info > x)
            	Inserare(R->st , x);
            else
            	Inserare(R->dr , x);
    }
    else
    {
    	R = new nod;
        R->info = x;
        R->st = NULL;
        R->dr = NULL;
    }	
}

Căutarea

Se cunoaște adresa rădăcinii unui arbore binar de căutare (sau NULL dacă arborele este vid) și o valoare. Se cere să se stabilească dacă există în arbore un nod care are cheia de identificare egală cu valoarea dată.

Procedăm astfel:

• dacă arborele este nevid:
  • dacă valoarea dată este identică cu cheia rădăcinii atunci am găsit nodul căutat;
  • dacă valoarea dată este mai mică decât cheia rădăcinii, se continuă căutarea în subarborele stâng;
  • dacă valoarea dată este mai mare decât cheia rădăcinii, se continuă căutarea în subarborele drept;
• dacă arborele este vid:
  • valoarea căutată nu există în arbore.

Funcție C++

Funcția de mai jos caută valoarea x în arborele pentru care adresa rădăcinii este memorată în pointerul R. Funcția returnează adresa nodului care are cheia egală cu x sau NULL dacă nu există un asemenea nod.

nod * Cautare(nod * R , int x)
{
	if(R == NULL)
		return NULL;
	if(R->info == x)
		return R;
	if(R->info > x)
		return Cautare(R->st , x);
	else
		return Cautare(R->dr , x);
}

Ștergerea unui nod

Se cunoaște adresa rădăcinii unui arbore binar de căutare (sau NULL dacă arborele este vid) și o valoare. Se cere să se șteargă din arbore nodul care are cheia de identificare egală cu valoarea dată.

Ștergerea trebuie realizată astfel încât să se păstreze proprietatea specifică arborilor binari de căutare!

Procedăm astfel:

• dacă arborele este nevid:
  • dacă valoarea dată este identică cu cheia rădăcinii atunci am găsit nodul căutat. Procedăm astfel:
    • dacă nodul este terminal (subarborele stâng și subarborele drept sunt vizi) se va șterge acest nod, iar adresa reținută de părinte pentru el devine NULL;
    • dacă numai subarborele stâng este nevid nodul se va șterge, iar adresa reținută de părinte pentru el devine adresa subarborelui stâng;
    • dacă numai subarborele drept este nevid nodul se va șterge, iar adresa reținută de părinte pentru el devine adresa subarborelui drept;
    • dacă ambii subarbori sunt nevizi:
      • se identifică cel mai mare nod din subarborele stâng (cel mai din dreapta nod al subarborelui stâng). Acest nod nu poate avea subarbore drept!
      • se copiază informația din acest nod în nodul analizat;
      • nodul identificat este șters. Ștergerea se realizează ca în cazul în care nodul este terminal sau ca în cazul în care nodul are numai subarbore stâng;
  • dacă valoarea dată este mai mică decât cheia rădăcinii, se continuă căutarea în subarborele stâng;
  • dacă valoarea dată este mai mare decât cheia rădăcinii, se continuă căutarea în subarborele drept;
• dacă arborele este vid:
  • valoarea căutată nu există în arbore.

Secvența C++

Mai jos sunt prezentate două funcții: Stergere și StAux. Funcția StAux tratează cazul când nodul curent trebuie șters și are ambii subarbori.

void StergAux(nod * & p, nod * & R)
{
	// R - nodul care trebuie sters
	// p - pointer cu care identificăm nodul cel mai din dreapta
	if(p->dr)
		StergAux(p -> dr , R);
	else
	{
		R->info = p->info;
		nod * aux = p;
		p = p->st;
		delete aux;
	}
}

void Stergere(nod * & R , int x)
{
	if(R != NULL)
	{
		if(R->info == x)
		{
			// nodul trebuie șters
			if(R->st == NULL && R->dr == NULL)
			{
				delete R;
				R = NULL;
			}
			else
				if(R->dr == NULL)
				{
					nod * aux = R;
					R = R->st;
					delete aux;
				}
				else
					if(R->st == NULL)
					{
						nod * aux = R;
						R = R->dr;
						delete aux;
					}
					else
						StergAux(R->st, R);
		}
		else
			if(R->info > x)
				Stergere(R->st , x);
			else
				Stergere(R->dr , x);
	}
	else
		return; // valoarea x nu apare în arbore
}

Parcurgerea

Arborii binari de căutare pot fi parcurși în orice mod: inordine, preordine, postordine. Datorită structurii interne a arborilor (pentru orice subarbore, cheia asociată rădăcinii este mai mare decât orice cheie din subarborele stâng și mai mică decât orice cheie din subarborele drept), parcurgerea în inordine (Stâng-Rădăcină-Drept)se face în ordinea crescătoare a cheilor!

Pentru a realiza o parcurgere în ordinea descrescătoare a cheilor, folosim tot o parcurgere în inordine, dar de tip Drept-Rădăcină-Stâng!

Secvență C++

void Afisare(nod * r)
{
    if(r != NULL)
    {
		Afisare(r->st);
		cout << r->info << " ";
		Afisare(r->dr);
	}
}

Concluzii

• Căutarea rapidă a informațiilor este foarte importantă în practică, arborii binari de căutare fiind utilizați ca suport pentru diverse structuri de date eficiente.
• Eficiența operațiilor depinde de ordinea în care se realizează inserarea nodurilor în arbore. De exemplu, dacă nodurile sunt create în ordinea crescătoare a cheilor, arborele devine degenerat, fiecare nod având numai descendent drept. Operațiile nu mai sunt eficiente, complexitatea lor devenind \(O(n)\), unde \(n\) este numărul nodurilor din arbore.
• Pentru a evita această situație, arborii binari de căutare primesc proprietăți suplimentare astfel încât să devină arbori echilibrați – să aibă înălțimea mică în raport cu numărul \(n\) de noduri: aproximativ \(\log_2n\).
  • operațiile de inserare, ștergere și căutare aplicate pe arborii binari de căutare echilibrați au complexitatea \(O(\log n)\);
  • exemple de arbori echilibrați: arborii AVL (Adelson-Velskii și Landis au fost doi cercetători sovietici care au folosit prima dată arborii echilibrați), arborii roșu-negru.
• Containerele STL map și set sunt implementate cu ajutorul arborilor binari de căutare echilibrați – de regulă arbori roșu-negru.

Acest articol conține o listă cu probleme propuse pentru examenul de bacalaureat la care se cer soluții eficiente din punct de vedere a memoriei utilizate și/sau a timpului de execuție (punctul III.3).
Problemele pot fi filtrate folosind butoanele din stânga!

2 9
1 1 1 2 2 3 5 5 5 5 6 6 7 8 10 10 12 15 21 21

9 7 
112 20 42 112 5013 824 10012 55 155 
402 1024 321 521 57 6542 255 

13 

210
3445 210 893210 1245 1210 3210 15210 67120 20210 12

263
39628
79
887308

9988887766333220

12
4 6 3 7 8 1 6 2 7 9 10 8

4 6 6 7 8 8 8 8 8 9 10 10

4  1 10
1 16  1
4  2  8
2  1  5
1  5  2

5
2 10 5 20 21 0 10 60 15 3 9 20 20 5 45

Definiție și proprietăți

Definiție. Se numește arbore binar un arbore cu rădăcină în care fiecare nod are cel mult doi descendenți direcți: descendentul stâng și descendentul drept.

Exemplu.

În arborele de mai sus:

• nodul 1 este rădăcina;
• rădăcina are doi descendenți direcți (fii): 2 este descendent stâng a lui 1, iar 3 este descendent drept;
• nodul 2 are un singur descendent, pe 4. Acest este descendent stâng al lui 2;
• similar, 7 este descendent drept al lui 4;
• nodurile 5, 6 și 7 sunt noduri terminale (frunze).

Observație. Dacă un nod are un singur descendent acesta va fi descendent stâng sau drept – acest lucru trebuie să fie precizat. Cei doi arbori de mai jos sunt considerați distincți.

O altă definiție, recursivă, a arborelui binar este următoarea: Un arbore binar este o mulțime finită de noduri, astfel:

• există un nod special, numit rădăcina arborelui;
• celelalte noduri sunt grupate în două submulțimi disjuncte \(A_1\) și \(A_2\), fiecare dintre ele fiind la rândul lor arbori binari. Arborii \(A_1\) și \(A_2\) reprezintă subarborele stâng, respectiv subarborele drept, al rădăcinii.

Această definiție recursivă este utilă deoarece foarte multe probleme cu arbori binari constau în prelucrarea nodurilor din arbore: a rădăcinii și a celor doi subarbori, în mod recursiv, prin metoda Divide et Impera.

Proprietății ale arborilor binari

1. Fiecare nivel i=0,1,2,... dintr-un arbore binar conține cel mult 2i noduri.
2. Un arbore binar de înălțime h conține cel mult 2h+1-1 noduri. Demonstrația se bazează pe afirmația anterioară.
3. Într-un arbore cu n noduri și înâlțime h avem relația \( h \geq \log_{2}{(n+1)} -1 \).
4. Dacă într-un arbore binar numărul nodurilor terminale este a, iar c este numărul nodurilor care au exact 2 fii, atunci a = c + 1.

Tipuri speciale de arbori binari

Arbore binar strict

Definiție: Se numește arbore binar strict un arbore binar în care fiecare nod, cu excepția celor terminale, are exact doi descendenți.

Exemplu:

Proprietăți:

• Un arbore binar strict cu \(k\) noduri terminale are \(n = 2 \cdot k – 1\) noduri.
• Un arbore binar strict are număr impar de noduri.

Arbore binar plin

Definiție: Se numește arbore binar plin un arbore binar în care fiecare nivel \( k \in \left\{ 0 , 1, 2, \cdots, h \right\} \), unde \(h\) este înălțimea arborelui, conține \(2^k\) noduri.

Exemplu:

Proprietăți:

• Arborele binar plin este un caz particular de arbore binar strict, în care toate nodurile terminale sunt situate pe același nivel.
• Un arbore binar plin cu \(k\) noduri terminale are \(n = 2 \cdot k – 1\) noduri.
• Un arbore binar plin cu înălțimea \(h\) are \(2^h-1\) noduri.

Arbore binar complet

Definiție: Se numește arbore binar complet un arbore binar în care fiecare nivel \( k \in \left\{ 0 , 1, 2, \cdots, h – 1 \right\} \), unde \(h\) este înălțimea arborelui, conține \(2^k\) noduri, iar nivelul \(k\) conține eventual mai puțin de \(2^h\) noduri, acestea fiin grupate de regulă în partea stângă.

Exemplu:

Observație: Arborele binar plin este și arbore binar complet.

Reprezentarea arborilor binari

Arborii binari se pot reprezenta fie prin referințe ascendente, fie prin referințe descendente, fie combinând cele două variante.

Reprezentarea prin referințe ascendente

În cazul reprezentării prin referințe ascendente, pentru fiecare nod din arbore trebuie să se cunoască:

• nodul părinte
• ce fel de descendent este (stâng sau drept).

Pentru memorarea informațiilor, considerând nodurile numerotate începând cu 1, putem folosi două tablouri: Tata[] și Tip[], unde Tata[k] reprezintă nodul părinte al lui k sau 0 dacă k este chiar rădăcina arborelui, iat Tip[k] este 0, dacă k este rădăcina arborului (caz în care nu are părinte), respectiv -1 dacă k este descendent stâng al lui Tata[k] sau 1 dacă k este descendent drept al lui Tata[k].

Exemplu.

Pentru arborele de mai sus, cele doua tablouri sunt:

Reprezentarea prin referințe descendente

În cazul reprezentării prin referințe descendente, trebuie să fie cunoscută rădăcina arborelui binar, iar pentru celelalte noduri din arbore, trebuie să se cunoască fiul stâng și fiul drept.

Această reprezentare se poate face cu ajutorul tablourilor sau prin intermediul alocării dinamice.

Reprezentarea cu tablouri

Dacă folosim tablouri, vom avea nevoie de două tablouri, st[] (de la stânga) și dr[] (de la dreapta). Considerând nodurile numerotate de la 1 la n:

• st[k] reprezintă numărul de ordine al nodului care este descendent stâng al lui k, sau 0 dacă k nu are descendent stâng;
• dr[k] reprezintă numărul de ordine al nodului care este descendent drept al lui k, sau 0 dacă k nu are descendent drept.

Exemplu.

Pentru arborele de mai sus, cele doua tablouri sunt:

Cunoscând valorile din cele două tablouri putem identifica rădăcina ca nodul care nu apare nici în st[], nici în dr[]. În exemplul de mai sus aceasta este 1.

Reprezentarea folosind alocarea dinamică

Pentru fiecare nod al arborelui se crează o variabilă dinamică de tip structură, în care se vor memora următoarele câmpuri:

• numărul nodului, sau orice informație utilă de spre nod
• două câmpuri de legătură, de tip pointer, reprezentând adresa nodului care este descendent stâng, respectiv adresa nodului care este descendent drept, sau NULL dacă nodul nu are descendent stâng (sau drept).

Următoarea secvență C/C++ definește structura:

struct nod{
	int info;
    nod * st, * dr;
};

Pentru operațiile cu arborele reprezentat astfel este necesar să cunoaștem adresa nodului rădăcină:

nod * R;

Pornind de la nodul rădăcină pot fi parcurse toate nodurile din arbore, pentru a efectua diverse operații cu acestea.

Crearea arborilor binari

Pentru a crea un arbore binar trebui cunoscute pentru fiecare nod:

• informația utilă memorată în acel nod
• nodurile descendenților stâng și drept, dacă există

În funcție de reprezentarea folosită, mecanismul creării poate avea mai multe forme.

Crearea arborilor binari folosind reprezentarea statică

În cazul reprezentării statice pot fi citite numărul de noduri n și elementele tablourilor st[] și dr[], ca în exemplul următor:

// variabilele n, st[] si dr[] sunt considerate globale

void Citire()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
        cin >> st[i];
    for(int i = 1 ; i <= n ; i ++)
        cin >> dr[i];
}

În numeroase probleme este necesară identificarea nodului rădăcină, folosind informațiile din cele două tablouri.

Determinarea rădăcinii se poate face ținând cont de faptul că ea nu este descendent al niciunui nod din arbore, deci nu va apărea în cele două tablouri:

int Radacina()
{
    int v[101] = {0};
    for(int i = 1 ; i <= n ; i ++)
    {
        if(st[i] != 0)
            v[st[i]] = 1;
        if(dr[i] != 0)
            v[dr[i]] = 1;
    }
    for(int i = 1 ; i <= n ; i ++)
        if(v[i] == 0)
            return i;
    return 0;
}

Crearea arborilor binari folosind reprezentarea dinamică

Reprezentarea dinamică unui arbore impune ca operațiile cu nodurile arborelui, inclusiv crearea, să se realizeze pornind de la rădăcină și continuând pe rând cu cei doi subarbori. Tehnica folosită este recursivitatea: pentru toți arborii (arborele initial și subarborii) realizăm aceleași operații – prelucrăm rădăcina și continuăm cu cei doi subarbori.

Schema folosită în funcția Creare din programul de mai jos este următoarea:

• funcția primește ca parametru un pointer, inițial NULL. Crează arborele (subarborele) și îl întoarce având ca valoare adresa rădăcinii;
• pentru fiecare apel (autoapel):
  • citim informația utilă din nodul curent – rădăcina arborelui (subarborelui);
  • dacă nodul curent are descendent stâng, continuăm cu acesta
  • dacă nodul curent are descendent drept, continuăm cu acesta

Pentru afișarea arborelui folosim funcția Afisare care procedează similar:

• are ca parametru adresa rădăcinii sau NULL
• afișează rădăcina (informația utilă din rădăcină)
• continuă recursiv cu subarborele stâng
• continuă recursiv cu subarborele drept

#include <iostream>

using namespace std;

int n , st[101], dr[101];

struct nod {
	int info;
	nod * st, * dr;
};

void Creare(nod * & r, int x)
{
    if(x != 0)
    {
		r = new nod;
		r->info = x;
		r->st = r->dr = NULL;
		int y;
		cout << "st[" << x << "]="; cin >> y;
		Creare(r -> st , y);
		cout << "dr[" << x << "]="; cin >> y;
		Creare(r -> dr , y);;
	}
}

void Afisare(nod * r)
{
    if(r != NULL)
    {
		cout << r->info << " ";
		Afisare(r->st);
		Afisare(r->dr);
	}
}

int main()
{
	nod * R = NULL;
	int x;
	cout << "Eticheta radacinii: "; cin >> x;
    Creare(R , x);
    Afisare(R);
    return 0;
}

Parcurgerea arborilor binari

Pentru a prelucra un arbore este necesar ca nodurile sale să fie vizitate. La fel ca în cazul grafurilor (ceea ce și sunt de fapt arborii binari), ei pot fi parcurși în lățime sau în adâncime, a doua metodă fiind de regulă folosită.

Parcurgerea începe din rădăcină.

În funcție de ordinea în care se vizitează nodurile avem următoarele parcurgeri:

1. parcurgerea în inordine – SRD – se parcurge mai întâi subarborele stâng (S), apoi rădăcina (R), apoi subarborele drept (D);
2. parcurgerea în preordine – RSD – se parcurge mai întâi rădăcina (R), apoi subarborele stâng (S), apoi subarborele drept (D);
3. parcurgerea în postordine – SDR – se parcurge mai întâi subarborele stâng (S), apoi subarborele drept (D), apoi rădăcina (R).

Observație: În programul de mai sus, crearea și afișarea arborelui se fac cu ajutorul parcurgerii, mai precis a parcurgerii în preordine.

Exemplu

Pentru arborele de mai sus, ordinea de parcurgere este:

• Inordine – SRD: 4 7 2 1 5 3 6
• Preordine: RSD 1 2 4 7 3 5 6
• Postordine: SDR 7 4 2 5 6 3 1

Deoarece parcurgerea începe din rădăcină și continuă cu nodurile descendent (cu subarborii stâng și drept), reprezentarea folosită este cea cu referințe descendente.

Programul C++ următor conține subprograme care implementează cele trei modalități de parcurgere pentru afisarea nodurilor din arbore. Reprezentarea arborelui este prin tablourile st[] și dr[]. Datele de intrare se citesc de la tastatură: mai întâi se citește numărul de noduri, n, apoi elementele vectorului st[], apoi elementele vectorului dr[].

#include <iostream>

using namespace std;

int n , st[101], dr[101];

void Citire()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
        cin >> st[i];
    for(int i = 1 ; i <= n ; i ++)
        cin >> dr[i];
}

int Radacina()
{
    // radacina este un nod intre 1 și n care nu apare în tablourile st[] și dr[]
    int v[101] = {0};
    for(int i = 1 ; i <= n ; i ++)
    {
        if(st[i] != 0)
            v[st[i]] = 1;
        if(dr[i] != 0)
            v[dr[i]] = 1;
    }
    for(int i = 1 ; i <= n ; i ++)
        if(v[i] == 0)
            return i;
    return 0;
}

void Inordine(int x)
{
    if(x != 0)
    {
        Inordine(st[x]);
        cout << x << " ";
        Inordine(dr[x]);
    }
}

void Preordine(int x)
{
    if(x != 0)
    {
        cout << x << " ";
        Preordine(st[x]);
        Preordine(dr[x]);
    }
}

void Postordine(int x)
{
    if(x != 0)
    {
        Postordine(st[x]);
        Postordine(dr[x]);
        cout << x << " ";
    }
}

int main()
{
    Citire();
    int R = Radacina();
    Inordine(R); 
    cout << endl;
    Preordine(R); 
    cout << endl;
    Postordine(R); 
    cout << endl;
    return 0;
}

Programul C++ următor conține subprograme care implementează cele trei modalități de parcurgere pentru afisarea nodurilor din arbore, reprezentarea acestuia fiind cea dinamică.

#include <iostream>

using namespace std;

int n , st[101], dr[101];

struct nod {
	int info;
	nod * st, * dr;
};

void Creare(nod * & r, int x)
{
    if(x != 0)
    {
		r = new nod;
		r->info = x;
		r->st = r->dr = NULL;
		int y;
		cout << "st[" << x << "]="; cin >> y;
		Creare(r -> st , y);
		cout << "dr[" << x << "]="; cin >> y;
		Creare(r -> dr , y);;
	}
}


void Preordine(nod * r)
{
    if(r != NULL)
    {
		cout << r->info << " ";
		Preordine(r->st);
		Preordine(r->dr);
	}
}

void Inordine(nod * r)
{
    if(r != NULL)
    {
		Inordine(r->st);
		cout << r->info << " ";
		Inordine(r->dr);
	}
}

void Postordine(nod * r)
{
    if(r != NULL)
    {
		Postordine(r->st);
		Postordine(r->dr);
		cout << r->info << " ";
	}
}

int main()
{
	nod * R = NULL;
	int x;
	cout << "Eticheta radacinii: "; cin >> x;
    Creare(R , x);
    Preordine(R); cout << endl;
    Inordine(R);  cout << endl;
    Postordine(R); cout << endl;
    return 0;
}

Ștergerea arborilor binari

Ștergerea arborilor binari este necesară cu precădere în cazul reprezentării dinamice a acestora.

Ștergerea se va face nod cu nod, folosind parcurgerea în postordine: parcurgem subarbore stâng, apoi subarborele drept, apoi prelucrăm rădăcina. În acest fel la ștergerea nodului rădăcină cei doi subarbori sunt deja șterși.

Funcția C++ de mai jos șterge arborele binar pentru care adresa rădăcinii este transmisă ca parametru. Acesta parametru este de intrare-ieșire: intră cu adresa rădăcinii și iese cu valoarea NULL – arborele a fost șters.

void Stergere(nod * & R)
{
	if(R != NULL)
    {
    	Stergere(R->st);
        Stergere(R->dr);
        delete R;
        R = NULL;
    }
}

Funcția de mai sus poate fi utilizată și pentru ștergerea unui subarbore dintr-un arbore dat. Este însă important ca parametrul să fie câmpul st sau dr din nodul părinte, nu un pointer oarecare care să memoreze adresa rădăcinii subarborelui.

Exemplu: Considerăm un arbore binar pentru care adresa rădăcinii este memorată în pointerul R. Dorim să ștergem subarborele stâng al rădăcinii, care are adresa în R->st.

Următoarea secvență este corectă.

Stergere(R->st);

Următoarea secvență este greșită. De ce?

nod * p = R->st;
Stergere(p);

Stars and bars (Stele și bare) este o metodă de rezolvare a unor probleme de combinatorică. Se poate folosi când trebuie să determinăm numărul de modalități de a grupa un număr dat de obiecte identice.

Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii este egal cu: \( C_{n+k-1}^{k-1} \).

Demonstrația implică separarea celor n obiecte (stele) în k cutii prin k-1 bare – de unde și numele. De exemplu, configurația următoare are n=7 stele și k=4 cutii: \( \star \vert \star \star \vert \vert \star \star \star \star \) și corespunde următoarei situații:

• prima cutie conține un obiect
• a doua cutie conține două obiecte
• a treia cutie nu conține niciun obiect
• a patra cutie conține patru obiecte

Configurația este echivalentă cu următoarea configurație de biți: 0100110000, în care bitul 1 corespunde obiectului, \( \star \), iar 1 corespunde barei, \( \vert \). Toate configurațiile convenabile au n-k+1 biți, dintre care n au valoarea 0 și k-1 au valoarea 1 și corespund submulțimilor cu k-1 elemente ale unei mulțimi cu n+k-1 elemente.

Astfel, numărul lor este \( C_{n+k-1}^{k-1} \).

Consecință Ecuația \(x_1 + x_2 + x_3 + \cdots + x_k = n\) are \( C_{n+k-1}^{k-1} \) soluții întregi nenegative (mai mari sau egale cu 0).

Afirmația este echivalentă cu teorema de mai sus, în care \(x_i\) fiind egal cu numărul de obiecte din cutia i.

Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii astfel încât fiecare cutie conține cel puțin un obiect este egal cu: \( C_{n-1}^{k-1} \).

Demonstrația 1: Fixăm în fiecare cutie câte un obiect. Rămân \(n – k\) obiecte care trebuie plasate în \(k\) cutii, în condițiile teoremei de mai sus. Astfel, numărul de variante este \( C_{n-k+k-1}^{k-1} = C_{n-1}^{k-1} \).

Demonstrația 2: Folosim metoda Stars and bars. Separarea obiectelor în cutii se face plasând \(k\) bare în golurile dintre obiecte. Sunt \(n-1\) goluri în care putem plasa \(k\) bare în \( C_{n-1}^{k-1} \) moduri.