Laborator 1
TDA ARBORE GENERALIZAT
Aplicatia 1
Se cere sa se implementeze folosind tablouri de indicatori spre parinte un arbore generalizat continand chei intregi, impreuna cu urmatorii operatori:
void insereaza_radacina( int cheie_radacina ) - distruge arborele generalizat daca acesta exista si creeaza unul nou avand "cheie_radacina" pe post de radacina;
void insereaza_cheie( int cheie , int cheie_parinte ) - insereaza in arbore cheia "cheie" ca si cheie fiu a cheii "cheie_parinte";
int cauta_cheie( int cheie ) - cauta cheia "cheie" in arbore; returneaza 1 in caz ca a fost gasita cheia, sau 0 in caz contrar;
int sterge_cheie( int cheie ) - cauta cheia "cheie" in arbore si o sterge; returneaza 1 in caz ca a fost gasita si stearsa cheia, sau 0 in caz contrar;
void preordine() - parcurge arborele in preordine, afisand cheile intalnite in aceasta parcurgere;
void inordine() - parcurge arborele in inordine, afisand cheile intalnite in aceasta parcurgere;
void postordine() - parcurge arborele in postordine, afisand cheile intalnite in aceasta parcurgere;
int inaltime_arbore() - returneaza inaltimea arborelui generalizat;
int grad_arbore() - returneaza gradul arborelui generalizat;
int cel_mai_din_stanga_frate( int cheie ) - returneaza cheia celui mai din stanga frate al cheii "cheie" sau -1 daca acesta nu exista;
int cel_mai_din_dreapta_frate( int cheie ) - returneaza cheia celui mai din dreapta frate al cheii "cheie" sau -1 daca acesta nu exista;
int numar_frati( int cheie ) - returneaza numarul de frati ai cheii "cheie".
Aplicatia 2
Se cere sa se implementeze folosind tablouri de indicatori spre primul fiu si spre fratele drept un arbore generalizat continand chei intregi, impreuna cu urmatorii operatori:
void insereaza_radacina( int cheie_radacina ) - distruge arborele generalizat daca acesta exista si creeaza unul nou avand "cheie_radacina" pe post de radacina;
void insereaza_cheie( int cheie , int cheie_parinte ) - insereaza in arbore cheia "cheie" ca si cheie fiu a cheii "cheie_parinte";
int cauta_cheie( int cheie ) - cauta cheia "cheie" in arbore; returneaza 1 in caz ca a fost gasita cheia, sau 0 in caz contrar;
int sterge_cheie( int cheie ) - cauta cheia "cheie" in arbore si o sterge; returneaza 1 in caz ca a fost gasita si stearsa cheia, sau 0 in caz contrar;
void preordine() - parcurge arborele in preordine, afisand cheile intalnite in aceasta parcurgere;
void inordine() - parcurge arborele in inordine, afisand cheile intalnite in aceasta parcurgere;
void postordine() - parcurge arborele in postordine, afisand cheile intalnite in aceasta parcurgere;
int inaltime_arbore() - returneaza inaltimea arborelui generalizat;
int grad_arbore() - returneaza gradul arborelui generalizat;
int cel_mai_din_stanga_frate( int cheie ) - returneaza cheia celui mai din stanga frate al cheii "cheie" sau -1 daca acesta nu exista;
int cel_mai_din_dreapta_frate( int cheie ) - returneaza cheia celui mai din dreapta frate al cheii "cheie" sau -1 daca acesta nu exista;
int numar_frati( int cheie ) - returneaza numarul de frati ai cheii "cheie".
Aplicatia 1
import java.util.LinkedList;
class ArboreGeneralizat {
private class Nod {
private int cheie;
private Nod Tata = null;
public Nod(int cheie) {
this.cheie = cheie;
}
public Nod getTata() {
return Tata;
}
public int getCheie() {
return cheie;
}
public void setCheie(int cheie) {
this.cheie = cheie;
}
public void setTata(Nod tata) {
Tata = tata;
}
private LinkedList<Nod>fii=new LinkedList<>();
public void adaugaFiu(int cheie){
Nod fiu=new Nod(cheie);
fiu.setTata(this);
fii.add(fiu);
}
public boolean esteRadacina(){
if(this.getTata()==null)
return true;
return false;
}
public boolean esteFrunza(){
if(fii.size()==0)
return true;
return false;
}
public void eliminaTata(){
this.setTata(null);
}
public LinkedList<Nod> getFii() {
return fii;
}
public int gasesteFiu(Nod n){
for(int i = 0; i< fii.size(); i++)
if(fii.get(i).cheie==n.getCheie())
return i;
return -1;
}
}
private Nod radacina;
private LinkedList<Nod> listaNoduri;
public ArboreGeneralizat(){
}
public void creeazaRadacina(int cheie){
this.radacina=new Nod(cheie);
this.radacina.setTata(null);
listaNoduri =new LinkedList<Nod>();
listaNoduri.add(radacina);
}
private Nod gasesteNod(int cheie){
for(int i = 0; i< listaNoduri.size(); i++)
if(listaNoduri.get(i).cheie==cheie)
return listaNoduri.get(i);
return null;
}
private int gasesteNod(Nod n){
for(int i = 0; i< listaNoduri.size(); i++)
if(listaNoduri.get(i).cheie==n.getCheie())
return i;
return -1;
}
public void addFiu(int cheieTata,int cheieFiu){
Nod fiu=new Nod(cheieFiu);
Nod tata=gasesteNod(cheieTata);
if(tata!=null) {
tata.adaugaFiu(cheieFiu);
fiu.setTata(tata);
listaNoduri.add(fiu);
}
}
public int inaltimeArbore(int cheie){
Nod aux=gasesteNod(cheie);
int nivele = 0;
for(Nod fiu : aux.getFii()){
int inaltimeFiu = inaltimeArbore(fiu.getCheie());
if(inaltimeFiu > nivele){
nivele = inaltimeFiu;
}
}
return nivele + 1;
}
public void stergeCheie(int cheie){
Nod aux=gasesteNod(cheie);
if(aux!=null){
if(aux.getFii().size()!=0){
for(int i=0;i<aux.getFii().size();i++){
stergeCheie(aux.getFii().get(i).getCheie());
i--;
}
}
Nod tata=aux.getTata();
tata.getFii().remove(tata.gasesteFiu(aux));
aux.setTata(null);
listaNoduri.remove(gasesteNod(aux));
}
}
public int numarFrati(int cheie){
Nod aux=gasesteNod(cheie);
if(aux!=null){
Nod tata=aux.getTata();
int n=tata.getFii().size();
return n;
}
return 0;
}
public int celMaiDinStangaFrate(int cheie){
Nod aux=gasesteNod(cheie);
if(aux!=null){
Nod tata=aux.getTata();
if(aux.cheie!=tata.getFii().getFirst().cheie)
return tata.getFii().getFirst().cheie;
}
return -1;
}
public int celMaiDinDreaptaFrate(int cheie){
Nod aux=gasesteNod(cheie);
if(aux!=null){
Nod tata=aux.getTata();
if(aux.cheie!=tata.getFii().getLast().cheie)
return tata.getFii().getLast().cheie;
}
return -1;
}
public int gradArbore(){
int gradMaxim=0,gradCurent=0;
for(int i=0;i<listaNoduri.size();i++){
gradCurent=listaNoduri.get(i).getFii().size();
if(gradCurent>gradMaxim)
gradMaxim=gradCurent;
}
return gradMaxim;
}
public void afisarePreordine(int cheie){
Nod aux=gasesteNod(cheie);
System.out.print(" "+aux.getCheie());
for(int i=0;i<aux.getFii().size();i++)
afisarePreordine(aux.getFii().get(i).getCheie());
}
public void afisarePostordine(int cheie){
Nod aux=gasesteNod(cheie);
for(int i=0;i<aux.getFii().size();i++)
afisarePostordine(aux.getFii().get(i).getCheie());
System.out.print(" "+aux.getCheie());
}
public void afisareInordine(int cheie){
Nod aux=gasesteNod(cheie);
if(aux.getFii().size()>0)
afisareInordine(aux.getFii().get(0).getCheie());
System.out.print(" "+aux.getCheie());
for(int i=1;i<aux.getFii().size();i++)
afisareInordine(aux.getFii().get(i).getCheie());
}
}
public class Main {
public static void main(String[] args) {
ArboreGeneralizat arbore=new ArboreGeneralizat();
arbore.creeazaRadacina(7);
arbore.addFiu(7,2);
arbore.addFiu(7,3);
arbore.addFiu(7,4);
arbore.addFiu(4,5);
arbore.addFiu(4,6);
arbore.addFiu(6,8);
// arbore.addFiu(5,7);
// arbore.addFiu(6,8);
// arbore.addFiu(8,10);
// arbore.addFiu(8,11);
System.out.println("Inaltime arbore: "+arbore.inaltimeArbore(7));
System.out.print("Afisare preordine: ");
arbore.afisarePreordine(7);
System.out.println();
System.out.print("Afisare postordine:");
arbore.afisarePostordine(7);//2 3 5 6 4 7
System.out.println();
System.out.print("Afisare inordine: ");
arbore.afisareInordine(7); // 2 7 3 5 4 6
arbore.stergeCheie(4);
System.out.println();
System.out.print("Afisare preordine dupa stergere: ");
arbore.afisarePreordine(7);
System.out.println();
}
}
Aplicatia 2
//stergeCheie(int cheie)...intra intr-un ciclu infinit...work to be done
import java.util.LinkedList;
class ArboreGeneralizat {
private class Nod {
private int cheie;
private Nod primulFiu = null;
private Nod frateDreapta =null;
public Nod(int cheie) {
this.cheie = cheie;
}
public int getCheie() {
return cheie;
}
public void setCheie(int cheie) {
this.cheie = cheie;
}
public Nod getPrimulFiu() {
return primulFiu;
}
public void setPrimulFiu(Nod primulFiu) {
this.primulFiu = primulFiu;
}
public Nod getFrateDreapta() {
return frateDreapta;
}
public void setFrateDreapta(Nod frateDreapta) {
this.frateDreapta = frateDreapta;
}
private LinkedList<Nod>fii=new LinkedList<>();
private int gasesteNod(int cheie){
for(int i=0;i<fii.size();i++)
if(fii.get(i).getCheie()==cheie)
return i;
return -1;
}
private Nod gasesteNod(Nod n){
for(int i=0;i<fii.size();i++)
if(fii.get(i).getCheie()==n.getCheie())
return fii.get(i);
return null;
}
public void adaugaFiu(int cheie){
Nod aux=new Nod(cheie);
if(this.primulFiu==null)
this.primulFiu=aux;
fii.add(aux);
if(fii.size()>1)
fii.get(gasesteNod(aux.getCheie())-1).setFrateDreapta(aux);
}
public LinkedList<Nod> getFii() {
return fii;
}
public boolean esteFrunza(){
if(fii.size()==0)
return true;
return false;
}
}
private Nod radacina;
private LinkedList<Nod> listaNoduri;
public ArboreGeneralizat(){
}
public void creeazaRadacina(int cheie){
this.radacina=new Nod(cheie);
listaNoduri =new LinkedList<Nod>();
listaNoduri.add(radacina);
}
private Nod gasesteNod(int cheie){
for(int i = 0; i< listaNoduri.size(); i++)
if(listaNoduri.get(i).cheie==cheie)
return listaNoduri.get(i);
return null;
}
private int gasesteNod(Nod n){
for(int i = 0; i< listaNoduri.size(); i++)
if(listaNoduri.get(i).cheie==n.getCheie())
return i;
return -1;
}
public void adaugaFiu(int cheieTata,int cheieFiu){
Nod fiu=new Nod(cheieFiu);
Nod tata=gasesteNod(cheieTata);
if(tata!=null) {
/*
Metoda alternativa...fara a folosi metoda adaugaFiu(cheieFiu)
if(tata.primulFiu==null)
tata.setPrimulFiu(fiu);
else{
Nod aux=tata.getPrimulFiu().getFrateDreapta();
while(aux!=null)
aux=aux.getFrateDreapta();
aux.setFrateDreapta(fiu);
}
*/
tata.getFii().add(fiu);
if(tata.primulFiu==null)
tata.setPrimulFiu(fiu);
else{
tata.getFii().get(tata.gasesteNod(fiu.getCheie())-1).setFrateDreapta(fiu);
}
// tata.adaugaFiu(cheieFiu); nu sunt sigur de ce metoda nu functioneaza
listaNoduri.add(fiu);
}
}
public int inaltimeArbore(int cheie){
Nod aux=gasesteNod(cheie);
int nivele = 0;
for(Nod fiu : aux.getFii()){
int inaltimeFiu = inaltimeArbore(fiu.getCheie());
if(inaltimeFiu > nivele){
nivele = inaltimeFiu;
}
}
return nivele + 1;
}
private Nod getTata(int cheie){
Nod aux=new Nod(cheie);
if(estePrimulFiu(cheie)==false){
aux=listaNoduri.get(celMaiDinStangaFrate(aux.getCheie()));
}
for(int i=0;i<listaNoduri.size();i++)
if(listaNoduri.get(i).getPrimulFiu()!=null)
if(listaNoduri.get(i).getPrimulFiu().getCheie()==aux.getCheie())
return listaNoduri.get(i);
return null;
}
/*
public void stergeCheie(int cheie){
Nod aux=gasesteNod(cheie);
if(aux!=null){
if(aux.getFii().size()!=0){
for(int i=0;i<aux.getFii().size();i++){
stergeCheie(aux.getFii().get(i).getCheie());
i--;
}
}
Nod tata=getTata(aux.getCheie());
if(estePrimulFiu(aux.getCheie())==false&&celMaiDinDreaptaFrate(tata.getPrimulFiu().getCheie())!=aux.getCheie())
tata.getFii().get(tata.gasesteNod(aux.getCheie())-1).setFrateDreapta(tata.getFii().get(tata.gasesteNod(aux
.getCheie())+1));
else{
if(celMaiDinDreaptaFrate(tata.getPrimulFiu().getCheie())==aux.getCheie())
tata.getFii().get(celMaiDinDreaptaFrate(cheie)-1).setFrateDreapta(null);
}
tata.getFii().remove(tata.gasesteNod(aux.getCheie()));
aux.setFrateDreapta(null);
listaNoduri.remove(gasesteNod(aux));
}
}
*/
public int numarFrati(int cheie){
Nod aux=gasesteNod(cheie);
if(estePrimulFiu(cheie)==false) {
aux=gasesteNod(celMaiDinStangaFrate(aux.getCheie()));
}
int numarFrati=0;
while(aux.getFrateDreapta()!=null){
aux=aux.getFrateDreapta();
numarFrati++;
}
return numarFrati;
}
private boolean estePrimulFiu(int cheie ){
for(int i=0;i<listaNoduri.size();i++)
if(listaNoduri.get(i).getPrimulFiu()!=null)
if(listaNoduri.get(i).getPrimulFiu().getCheie()==cheie)
return true;
return false;
}
public int celMaiDinStangaFrate(int cheie){
Nod aux=gasesteNod(cheie);
if(aux!=null){
if(estePrimulFiu(cheie))
return -1;
while(estePrimulFiu(aux.getCheie())==false){
int i = 0;
boolean gasit=false;
while (i < listaNoduri.size()&&gasit==false){
if(listaNoduri.get(i).getFrateDreapta()!=null)
if(listaNoduri.get(i).getFrateDreapta().getCheie() == aux.getCheie()) {
gasit = true;
aux = listaNoduri.get(i);
}
if(gasit==false&&i<listaNoduri.size())
i++;
}
// aux = listaNoduri.get(i);
}
return aux.getCheie();
}
return -1;
}
public int celMaiDinDreaptaFrate(int cheie){
Nod aux=gasesteNod(cheie);
if(aux!=null){
if(aux.getFrateDreapta()!=null) {
Nod aux2 = aux.getFrateDreapta();
while (aux2.getFrateDreapta() != null) {
aux2 = aux2.getFrateDreapta();
}
return aux2.getCheie();
}
}
return -1;
}
public int gradArbore(){
int gradMaxim=0,gradCurent=0;
for(int i=0;i<listaNoduri.size();i++){
gradCurent=listaNoduri.get(i).getFii().size();
if(gradCurent>gradMaxim)
gradMaxim=gradCurent;
}
return gradMaxim;
}
public void afisarePreordine(int cheie){
Nod aux=gasesteNod(cheie);
System.out.print(" "+aux.getCheie());
for(int i=0;i<aux.getFii().size();i++)
afisarePreordine(aux.getFii().get(i).getCheie());
}
public void afisarePostordine(int cheie){
Nod aux=gasesteNod(cheie);
for(int i=0;i<aux.getFii().size();i++)
afisarePostordine(aux.getFii().get(i).getCheie());
System.out.print(" "+aux.getCheie());
}
public void afisareInordine(int cheie){
Nod aux=gasesteNod(cheie);
if(aux.getFii().size()>0)
afisareInordine(aux.getFii().get(0).getCheie());
System.out.print(" "+aux.getCheie());
for(int i=1;i<aux.getFii().size();i++)
afisareInordine(aux.getFii().get(i).getCheie());
}
}
public class Main {
public static void main(String[] args) {
ArboreGeneralizat arbore=new ArboreGeneralizat();
arbore.creeazaRadacina(7);
arbore.adaugaFiu(7,2);
arbore.adaugaFiu(7,3);
arbore.adaugaFiu(7,4);
arbore.adaugaFiu(4,5);
arbore.adaugaFiu(4,6);
arbore.adaugaFiu(6,8);
// arbore.addFiu(5,7);
// arbore.addFiu(6,8);
// arbore.addFiu(8,10);
// arbore.addFiu(8,11);
System.out.println("Inaltime arbore: "+arbore.inaltimeArbore(7));
System.out.print("Afisare preordine: ");
arbore.afisarePreordine(7);
System.out.println();
System.out.print("Afisare postordine:");
arbore.afisarePostordine(7);//2 3 5 8 6 4 7
System.out.println();
System.out.print("Afisare inordine: ");
arbore.afisareInordine(7); // 2 7 3 5 4 8 6
System.out.println("\nCel mai din dreapta frate a lui 2: "+arbore.celMaiDinDreaptaFrate(2));
System.out.println("Cel mai din dreapta frate a lui 4: "+arbore.celMaiDinDreaptaFrate(4));
System.out.println("\nNumarul de frati a lui 2: "+arbore.numarFrati(2));
System.out.println("Numarul de frati a lui 4: "+arbore.numarFrati(4));
System.out.println("\nCel mai din stanga frate a lui 2: "+arbore.celMaiDinStangaFrate(2));
System.out.println("Cel mai din stanga frate a lui 4: "+arbore.celMaiDinStangaFrate(4));
// arbore.stergeCheie(4);
System.out.println();
System.out.print("Afisare preordine dupa stergere: ");
arbore.afisarePreordine(7); // 7 2 3
System.out.println();
}
}
Varianta C
#include <stdio.h>
#include <stdlib.h>
#define max 100
typedef struct Nod
{
int cheie;
struct Nod* tata;
struct Nod* fii[max];
int nrFii;
}Nod;
void initFii(Nod* f)
{
int i;
for(i=0;i<max;i++)
{
f->fii[i]=NULL;
}
f->nrFii=0;
}
Nod* creeazaRadacina(int cheie)
{
Nod* radacina=(Nod*)malloc(sizeof(Nod));
radacina->tata=NULL;
radacina->cheie=cheie;
initFii(radacina);
return radacina;
}
Nod* gasesteNod(Nod* radacina, int cheie)
{
int i;
Nod* r=NULL;
if(radacina!=NULL)
{
if(radacina->cheie==cheie)
{
if(radacina)
return radacina;
}
else
{
for(i=0;i<radacina->nrFii;i++)
{
r=gasesteNod(radacina->fii[i],cheie);
if(r)
return r;
}
}
}
return NULL;
}
void adaugaNod(int cheieTata, int cheieFiu, Nod* radacina)
{
Nod* fiu=(Nod*)malloc(sizeof(Nod));
Nod* tata=gasesteNod(radacina, cheieTata);
fiu->cheie=cheieFiu;
fiu->tata=tata;
initFii(fiu);
tata->fii[tata->nrFii]=fiu;
tata->nrFii++;
}
void afisarePreordine(Nod* radacina)
{
int i;
if(radacina!=NULL)
{
printf("%d ",radacina->cheie);
for(i=0;i<radacina->nrFii;i++)
afisarePreordine(radacina->fii[i]);
}
}
void afisarePostordine(Nod* radacina)
{
int i;
if(radacina!=NULL)
{
for(i=0;i<radacina->nrFii;i++)
afisarePostordine(radacina->fii[i]);
printf("%d ",radacina->cheie);
}
}
void afisareInordine(Nod* radacina)
{
int i;
if(radacina!=NULL)
{
if(radacina->nrFii>0)
afisareInordine(radacina->fii[0]);
printf("%d ",radacina->cheie);
for(i=1;i<radacina->nrFii;i++)
afisareInordine(radacina->fii[i]);
}
}
int inaltimeArbore(Nod* radacina)
{
int nivele=0;
int i;
for(i=0;i<radacina->nrFii;i++)
{
int inaltimeFiu=inaltimeArbore(radacina->fii[i]);
if(inaltimeFiu>nivele)
nivele=inaltimeFiu;
}
return nivele+1;
}
int main()
{
printf("Hello world!\n");
Nod* rad=creeazaRadacina(7);
adaugaNod(7,2,rad);
adaugaNod(7,3,rad);
adaugaNod(7,4,rad);
adaugaNod(4,5,rad);
adaugaNod(4,6,rad);
adaugaNod(6,8,rad);
// adaugaNod(1,5);
// adaugaNod(1,3);
// adaugaNod(1,4);
printf("Afisare preordine: ");
afisarePreordine(rad);
printf("\n");
printf("Afisare postordine: ");
afisarePostordine(rad);
printf("\n");
printf("Afisare inordine: ");
afisareInordine(rad);
printf("\n");
printf("\nInaltime arbore: %d ",inaltimeArbore(rad));
return 0;
}
Aplicatie SUPLIMENTARA
Determinati inaltimea arborelui urmator:
/*
1
3 4 2 5
9 6 7
8
11 10
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXIM 11
// 1 2 3 4 5 6 7 8 9 10 11
int primulFiu[] = {2, -1, 8, -1, 5, 7, -1, 10, -1, -1, -1};
int frateDreapta[] = {-1, 4, 3, 1, -1, 6, -1, -1, -1, -1, 9};
typedef struct
{
int fii[20];
int numarFii;
}fiiNodului;
fiiNodului getFii(int cheie)
{
fiiNodului result;
result.numarFii=0;
if(primulFiu[cheie]==-1)
return result;
result.fii[result.numarFii++]=primulFiu[cheie];
while(frateDreapta[result.fii[result.numarFii - 1]] != -1)
{
result.fii[result.numarFii] = frateDreapta[result.fii[result.numarFii - 1]];
result.numarFii++;
}
return result;
}
int inaltime(int cheie)
{
fiiNodului fii = getFii(cheie);
if (fii.numarFii==0)
return 1;
int i, nivele=0;
for (i = 0; i < fii.numarFii; i++){
int inaltimeFiu=inaltime(fii.fii[i]);
if(inaltimeFiu>nivele)
nivele=inaltimeFiu;
}
return nivele+1;
}
int main()
{
int result = inaltime(0);
printf("%d ", result);
return 0;
}