Arbori Binari

Aspecte teoretice:

În informatică, un arbore binar este un arbore în care fiecare nod are cel mult doi succesori (fii). De obicei, succesorii se numesc „nodul stânga” și „nodul dreapta”. Arborii binari sunt folosiți mai ales drept arbori binari de căutare sau și la structurile de date de tip heap.

Un arbore binar este o mulțime de noduri care îndeplinesc următoarele condiții:
fiecare nod are 0, 1 sau 2 succesori;
fiecare nod are un singur predecesor, cu excepția rădăcinii care nu are niciunul;
succesorii fiecărui nod sunt ordonați (fiul stâng, fiul drept; dacă este unul singur trebuie menționat care).

Definiția recursivă:
(Baza:) Arborele fără nici un nod este un arbore binar.
(Pasul recursiv:) Fie a și b doi arbori binari, iar n un nod. Atunci arborele care îl are pe n ca rădăcină, pe a ca subarbore stâng și pe b ca subarbore drept este un arbore binar.

Implementare C++ operații cu arbori binari:

// ArboriBinariCPP.cpp : Defines the entry point for the console application.
 // Arbbin_inginerie.cpp : main project file. 
 
#include "stdafx.h" 
#include <iostream> 
#include <conio.h>
 
using namespace std; 
 
#define tip_element int 
struct nod_arb 
{ 
	tip_element info; 
	nod_arb *ss,*sd; 
	nod_arb(tip_element inf, nod_arb * sss = NULL, nod_arb *ssd = NULL): 
	info(inf),ss(sss),sd(ssd) 
	{ 
		// functie constructor 
		// creaza obiecte de tip nod_arbore 
		// instantiaza cu NULL subarborii stang si drept 
	} 
}; 
 
struct arbbin 
{ 
	nod_arb * rad; 
	int nr_noduri; 
	arbbin():rad(NULL),nr_noduri(0){};// instantiez radacina ca fiind NULL si nr noduri cu 0 
	void preord(nod_arb*); 
	void inord (nod_arb*); 
	void postord (nod_arb*);
	int count(){return nr_noduri;} 
	bool frunza (nod_arb *r) {return r->ss ==NULL && r->sd==NULL;} 
	nod_arb * insert(nod_arb*, tip_element); 
	void afis_RSD(){preord(rad);} 
	void afis_SRD(){inord(rad);} 
	arbbin &operator <<(tip_element k){rad = insert(rad,k); return *this;} 
}; 
 
nod_arb* arbbin::insert(nod_arb *r, tip_element k) 
{ 
	if(r) // daca radacina e diferita de null prelucreaza 
	{ 
		if(k==r->info); 
		else if (k>r->info) r->sd= insert(r->sd,k); 
		else 
		r->ss = insert(r->ss,k); 
		return r; 
	} 
	else 
	return nr_noduri++,new nod_arb(k); //altfel aloca memorie si creaza un nod nou, radacina; 
} 
 
void arbbin::preord (nod_arb *r) 
{ 
	if(r) 
	{ 
	cout<<r->info; 
	if(!frunza(r)) 
	{ 
	cout<< "subarb stang "; 
	cout<<"("; 
	preord(r->ss); 
	cout<<")"; 
	cout<<"subarb drept"; 
	cout<<"("; 
	preord(r->sd); 
	cout<<")"; 
	cout<< endl; 
	} 
	} 
	else cout<<"."; 
} 
 
 
void arbbin::inord (nod_arb *r) 
{ 
	if(r) 
	{ if(!frunza(r)) 
	{ 
	cout<<"("; 
	inord(r->ss); 
	cout<<")"; 
	} 
	cout<<r->info;
	if (!frunza(r)) { 
	cout<< "("; 
	inord(r->sd); 
	cout<<")"; 
	} 
	} 
	else cout<<"."; 
} 
 
void arbbin::postord(nod_arb *r)
{ 
	if(r!=NULL)
	{ postord(r->ss);
	postord(r->sd);
	//prelucrare r->info
	}
}
 
 
 
int main() 
{ 
	arbbin a; 
	a<<56<<12<<34<<90<<67<<80<<101; 
	a.afis_RSD (); 
	cout<<endl; 
	a.afis_SRD (); 
	cout<<endl; 
	cout<<"Arborele are "<<a.count()<<" noduri"<<endl; 
	//Console::WriteLine(L"Hello World"); 
	// tema afisare Postordine SDR(); 
	system("pause");
}