Laborator 2
TDA ARBORE BINAR
Aplicatia 1
Se cere sa se implementeze un arbore binar ordonat continand chei intregi, impreuna cu urmatorii operatori:
void adauga( int cheie ) - insereaza in arbore cheia "cheie" (arborele este ordonat);
int cauta( int cheie ) - cauta cheia "cheie" in arbore; returneaza 1 in caz ca a fost gasita, sau 0 in caz contrar;
void suprima( int cheie ) - cauta cheia "cheie" in arbore si o sterge;
void preordine() - parcurge arborele in preordine, afisand cheile intalnite in aceasta parcurgere;
int aceeasi_forma( arbore a1 , arbore a2 ) - returneaza 1 daca arborii "a1" si "a2" au aceeasi forma geometrica (nu neaparat aceleasi chei), sau 0 in caz contrar;
int cel_mai_mic() - returneaza valoarea celei mai mici chei din arbore;
int intre( int k1 , int k2 ) - returneaza numarul de chei din arbore care au valoarea cuprinsa numeric intre "k1" si "k2";
void afisare_pe_nivele() - afiseaza cheile arborelui pe mai multe linii, fiecare linie corespunzand unui nivel din arbore.
Aplicatia 2
Se cere sa se implementeze un arbore binar ordonat continand chei intregi, impreuna cu urmatorii operatori:
void adauga( int cheie ) - insereaza in arbore cheia "cheie" (arborele este ordonat);
int cauta( int cheie ) - cauta cheia "cheie" in arbore; returneaza 1 in caz ca a fost gasita, sau 0 in caz contrar;
void suprima( int cheie ) - cauta cheia "cheie" in arbore si o sterge;
void postordine() - parcurge arborele in postordine, afisand cheile intalnite in aceasta parcurgere;
arbore simetric( arbore a ) - creeaza si returneaza un arbore simetric in oglinda fata de arborele "a" primit ca parametru;
int cel_mai_mare() - returneaza valoarea celei mai mari chei din arbore;
int mai_mici( int k ) - returneaza numarul de chei din arbore care au valoarea mai mica decat "k";
int mai_mari( int k ) - returneaza numarul de chei din arbore care au valoarea mai mare decat "k";
void relatii( int k1 , int k2 ) - pentru doua chei, "k1" si "k2", afiseaza daca sunt in relatia stramos-descendent, sau daca nu, afiseaza daca se afla pe acelasi nivel in arbore.
import java.util.LinkedList;
class ArboreBinar {
private class Nod {
private int cheie;
private Nod stang = null;
private Nod drept = null;
public Nod(int cheie) {
this.cheie = cheie;
}
public int getCheie() {
return cheie;
}
public void setCheie(int cheie) {
this.cheie = cheie;
}
public Nod getStang() {
return stang;
}
public void setStang(Nod stang) {
this.stang = stang;
}
public Nod getDrept() {
return drept;
}
public void setDrept(Nod drept) {
this.drept = drept;
}
public boolean esteFrunza() {
if (this.stang == null && this.drept == null)
return true;
return false;
}
}
private Nod radacina;
public ArboreBinar(int cheie){
this.radacina=new Nod(cheie);
}
public Nod getRadacina() {
return radacina;
}
private Nod adaugaNod(Nod curent, int cheie) {
if (curent == null) {
return new Nod(cheie);
}
if (cheie < curent.getCheie()) {
curent.setStang(adaugaNod(curent.getStang(), cheie));
}
else
if (cheie > curent.getCheie()) {
curent.setDrept(adaugaNod(curent.getDrept(), cheie));
}
else {
// Cheia deja exista...
return curent;
}
return curent;
}
public void add(int value) {
this.radacina = adaugaNod(this.radacina, value);
}
private boolean contains(Nod curent, int cheie) {
if(curent==null) {
return false;
}
if(cheie==curent.getCheie()) {
return true;
}
if(cheie < curent.getCheie())
return contains(curent.getStang(), cheie);
else
return contains(curent.getDrept(), cheie);
}
public boolean contains(int cheie) {
return contains(this.radacina, cheie);
}
private int ceaMaiMica(Nod radacina) {
if(radacina.getStang()==null)
return radacina.getCheie();
else
return ceaMaiMica(radacina.getStang());
}
private int ceaMaiMare(Nod radacina){
if(radacina.getDrept()==null)
return radacina.getCheie();
else
return ceaMaiMare(radacina.getDrept());
}
public int ceaMaiMare(){
return ceaMaiMare(this.radacina);
}
public int ceaMaiMica(){
return ceaMaiMica(this.radacina);
}
private Nod remove(Nod curent, int cheie) {
if (curent == null) {
return null;
}
if (cheie == curent.getCheie()) {
if (curent.getStang()== null && curent.getDrept()==null){
return null;
}
if (curent.getDrept() == null) {
return curent.getStang();
}
if (curent.getStang() == null) {
return curent.getDrept();
}
int aux = ceaMaiMica(curent.getDrept());
curent.setCheie(aux);
curent.setDrept(remove(curent.getDrept(), aux));
return curent;
}
if (cheie < curent.getCheie()) {
curent.setStang(remove(curent.getStang(), cheie));
return curent;
}
curent.setDrept(remove(curent.getDrept(), cheie));
return curent;
}
public void remove(int cheie) {
remove(this.radacina, cheie);
}
public void afisarePreodine(){
afisarePreodine(radacina);
}
public void afisarePostordine(){
afisarePostordine(radacina);
}
public void afisareInordine(){
afisareInordine(radacina);
}
private void afisarePreodine(Nod n) {
if (n!=null) {
System.out.print(" " + n.getCheie());
afisarePreodine(n.getStang());
afisarePreodine(n.getDrept());
}
}
private void afisarePostordine(Nod n) {
if (n != null) {
afisarePostordine(n.getStang());
afisarePostordine(n.getDrept());
System.out.print(" " + n.getCheie());
}
}
private void afisareInordine(Nod n) {
if (n != null) {
afisareInordine(n.getStang());
System.out.print(" " + n.getCheie());
afisareInordine(n.getDrept());
}
}
public void traversarePeNivele() {
if (radacina == null) {
return;
}
LinkedList<Nod> noduri = new LinkedList<>();
noduri.add(radacina);
while (!noduri.isEmpty()) {
Nod nod = noduri.remove();
System.out.print(" " + nod.getCheie());
if (nod.getStang() != null) {
noduri.add(nod.getStang());
}
if (nod.getDrept()!= null) {
noduri.add(nod.getDrept());
}
}
}
private int inaltimeArbore(Nod n){
if (n == null){
return 0;
}
else{
return 1 +Math.max(inaltimeArbore(n.getStang()),inaltimeArbore(n.getDrept()));
}
}
public int inaltimeArbore(){
return inaltimeArbore(this.radacina);
}
}
public class Main {
public static void main(String[] args) {
ArboreBinar arbore=new ArboreBinar(6);
arbore.add(8);
arbore.add(4);
arbore.add(3);
arbore.add(5);
arbore.add(7);
arbore.add(9);
System.out.println("Arborele contine valoarea 8 : "+arbore.contains(8));
System.out.print("Afisare postordine:");
arbore.afisarePostordine();
System.out.print("\nAfisare Inordine: ");
arbore.afisareInordine();
System.out.print("\nAfisare preodine: ");
arbore.afisarePreodine();
System.out.print("\nAfisare pe nivele: ");
arbore.traversarePeNivele();
arbore.remove(8);
System.out.print("\nAfisare pe nivele: ");
arbore.traversarePeNivele();
System.out.println("\nArborele contine valoarea 8 : "+arbore.contains(8));
System.out.print("\nCea mai mare valoare: "+arbore.ceaMaiMare());
System.out.print("\nCea mai mica valoare: "+arbore.ceaMaiMica());
System.out.print("\nInaltimea arborelui este: "+arbore.inaltimeArbore());
}
}
Varianta C
#include <stdio.h>
#include <stdlib.h>
typedef struct Nod
{
int cheie;
struct Nod* stang;
struct Nod* drept;
}Nod;
Nod* adaugaNod(Nod* curent, int cheie)
{
Nod* p;
if (curent == NULL)
{
p = (Nod*)malloc(sizeof(Nod));
p->cheie = cheie;
p->stang = NULL;
p->drept = NULL;
return p;
}
if (cheie<curent->cheie)
{
curent->stang = adaugaNod(curent->stang, cheie);
}
else
if (cheie >= curent->cheie)
{
curent->drept = adaugaNod(curent->drept, cheie);
}/*
else
{
//return curent;
}
*/
return curent;
}
void afisarePreordine(Nod* curent)
{
if (curent != NULL)
{
printf("%d ", curent->cheie);
afisarePreordine(curent->stang);
afisarePreordine(curent->drept);
}
}
void afisarePostordine(Nod* n)
{
if (n != NULL)
{
afisarePostordine(n->stang);
afisarePostordine(n->drept);
printf("%d ", n->cheie);
}
}
void afisareInordine(Nod* n)
{
if (n != NULL)
{
afisareInordine(n->stang);
printf("%d ", n->cheie);
afisareInordine(n->drept);
}
}
typedef enum { false = 0, true = 1 }bool;
bool aceeasiForma(Nod* curent1, Nod* curent2)
{
if ((curent1 != NULL && curent2 == NULL) || (curent1 == NULL && curent2 != NULL))
return false;
else
{
if (curent1 != NULL && curent2 != NULL)
{
return aceeasiForma(curent1->stang, curent2->stang) && aceeasiForma(curent1->drept, curent2->drept);
}
}
return true;
}
int maxim(int a, int b)
{
if (a>b)
return a;
else
return b;
}
int inaltimeArbore(Nod* curent)
{
if (curent == NULL)
return 0;
else
{
return 1 + maxim(inaltimeArbore(curent->stang), inaltimeArbore(curent->drept));
}
}
int ceaMaiMica(Nod* radacina)
{
if (radacina->stang == NULL)
return radacina->cheie;
else
return ceaMaiMica(radacina->stang);
}
Nod* sterge(Nod* curent, int cheie)
{
if (curent == NULL)
{
return NULL;
}
if (cheie == curent->cheie)
{
if (curent->stang == NULL && curent->drept == NULL)
{
return NULL;
}
if (curent->drept == NULL)
{
return curent->stang;
}
if (curent->stang == NULL)
{
return curent->drept;
}
int aux = ceaMaiMica(curent->drept);
curent->cheie = aux;
curent->drept = sterge(curent->drept, aux);
return curent;
}
if (cheie < curent->cheie)
{
curent->stang = sterge(curent->stang, cheie);
return curent;
}
curent->drept = sterge(curent->drept, cheie);
return curent;
}
int main()
{
printf("Hello world!\n");
Nod* radacina = NULL;
Nod* radacina2 = NULL;
/*
radacina=adaugaNod(radacina,5);
radacina=adaugaNod(radacina,3);
radacina=adaugaNod(radacina,4);
afisarePreordine(radacina);
printf("\nInaltime arbore: %d ",inaltimeArbore(radacina));
radacina2=adaugaNod(radacina2,10);
radacina2=adaugaNod(radacina2,8);
radacina2=adaugaNod(radacina2,9);
printf("\n%d \n",aceeasiForma(radacina,radacina2));
afisarePreordine(radacina2);
*/
radacina = adaugaNod(radacina, 6);
radacina = adaugaNod(radacina, 8);
radacina = adaugaNod(radacina, 4);
radacina = adaugaNod(radacina, 3);
radacina = adaugaNod(radacina, 5);
radacina = adaugaNod(radacina, 7);
radacina = adaugaNod(radacina, 9);
printf("Afisare preordine: ");
afisarePreordine(radacina);
printf("\nAfisare postordine: ");
afisarePostordine(radacina);
printf("\nAfisare inordine: ");
afisareInordine(radacina);
sterge(radacina,8);
printf("\nAfisare inordine dupa stergere: ");
afisareInordine(radacina);
return 0;
}