Initial commit

1 files changed, 235 insertions, 0 deletions

diff --git a/sem_4/Algo/TP5/Arbo.cpp b/sem_4/Algo/TP5/Arbo.cpp
new file mode 100644
index 0000000..18305d8
--- /dev/null
+++ b/sem_4/Algo/TP5/Arbo.cpp
@@ -0,0 +1,235 @@
+#include "Arbo.h"
+
+/******* Liste doublement chainee Début *******/
+
+Cellule::Cellule (ContCellule A){
+  fils=A;
+  Apres=NULL;
+}
+
+
+
+
+ListeCellules Cellule::EstDansListeP(ContCellule A){
+  if (fils==A) return this;
+  if (Apres==NULL) return NULL;
+  return Apres->EstDansListeP(A);
+}
+
+
+
+ListeCellules Cellule::AjouterSuccesseur(ContCellule A){
+  if (!EstDansListeP(A)) {
+    ListeCellules ptCell=new Cellule(A);
+    ptCell->Apres=this;
+    return ptCell;
+  }
+  return this;
+}
+
+
+
+ListeCellules Cellule::RetirerSuccesseur(ContCellule A){
+  if (fils==A) return Apres;
+  if (!Apres) return this;
+  Apres=Apres->RetirerSuccesseur(A); return this;
+}
+
+
+
+
+/******* Liste doublement chainee Fin *******/
+
+
+/************Arborescence Debut*************/
+
+
+Sommet::Sommet(Valeur v){
+  racine=v;
+  ListeSuccesseurs= NULL;
+}
+
+
+ListeCellules Sommet::EstSuccesseurP(Arbo A){
+  if (ListeSuccesseurs){
+    return (ListeSuccesseurs->EstDansListeP(A));  // à completer et decommenter
+  }
+  return NULL;
+}
+
+
+
+void Sommet::AjouterSuccesseur(Arbo A){
+  if ( ListeSuccesseurs && !(ListeSuccesseurs->EstDansListeP(A))){
+    ListeSuccesseurs = ListeSuccesseurs->AjouterSuccesseur(A);
+  }
+  else {
+    ListeSuccesseurs = new Cellule (A);
+  }
+  return;
+}
+
+
+
+void Sommet::RetirerSuccesseur(Arbo A){
+  if (ListeSuccesseurs &&  ListeSuccesseurs->EstDansListeP(A)) {
+    ListeSuccesseurs= ListeSuccesseurs->RetirerSuccesseur(A);  // à completer et decommenter
+  }
+  return;
+}
+
+ostream& operator<<(ostream& os, Sommet& S){
+  os<<S.racine<<" ";
+  return os;
+}
+
+/************Arborescence Fin*************/
+
+/************Traversee recursive Debut*************/
+
+void TraverseePrefixeRec(Arbo A){
+  if (!A) { return;};
+  cout<< *A;
+  for (ListeCellules L=A->ListeSuccesseurs; L!=NULL;L=L->Apres){
+    TraverseePrefixeRec(L->fils);
+  } ;  // à completer et decommenter
+  return;
+}
+
+/************Traversee recursive Fin*************/
+
+/**********Pile Début*********/
+
+Pile::Pile(){
+  Sommet=NULL;
+}
+
+
+bool Pile::VideP(){
+  return Sommet==NULL;
+}
+
+
+void Pile::Empiler(ContCellule A){
+  Cellule* ptCellule=new Cellule(A);
+  ptCellule->Apres=Sommet;
+  Sommet=ptCellule;
+  return;
+}
+
+
+ContCellule Pile::Depiler(){
+  Cellule* ptCellule=Sommet;
+  Sommet=Sommet->Apres;
+  return ptCellule->fils;
+}
+
+/**********Pile Fin*********/
+
+/************Traversee  prefixe iterative Debut*************/
+
+void TraverseePrefixeIt(Arbo A){
+  Pile* P=new Pile;
+  P->Empiler(A);
+  while (!(P->VideP())){
+    Arbo tmp = P->Depiler();
+    cout<< *tmp;
+    for (ListeCellules L = tmp->ListeSuccesseurs; L!=NULL; L=L->Apres){
+      P->Empiler(L->fils);
+    }
+  }
+  cout<<endl;
+  //  while // à completer et decommenter
+}
+
+/************Traversee  prefixe iterative Fin*************/
+
+
+/**********File Début*********/
+
+File::File(){
+  Sortie=NULL; Entree=NULL;
+}
+
+
+bool File::VideP(){
+  return Sortie==NULL;
+}
+
+
+void File::Enfiler(ContCellule A){
+  Cellule* ptCellule=new Cellule(A);
+  if (Entree) Entree->Apres=ptCellule;
+  Entree=ptCellule;
+  if (! Sortie) Sortie=ptCellule;
+  return;
+}
+
+
+ContCellule File::Defiler(){
+  Cellule* ptCellule=Sortie;
+  Sortie=Sortie->Apres;
+  return ptCellule->fils;
+}
+
+/**********File Fin*********/
+
+/************Traversee Largeur Debut*************/
+
+void TraverseeLargeur(Arbo A){
+  File * f= new File;
+  f->Enfiler(A);
+  while (!f->VideP()){
+    A = f->Defiler();
+    cout<<(*A);
+    for (ListeCellules tmp = A->ListeSuccesseurs; tmp != NULL; tmp=tmp->Apres){
+      f->Enfiler(tmp->fils);
+    }
+
+  }
+}  // à completer
+
+/************Traversee Largeur Fin*************/
+
+
+int main(){
+
+  Arbo A0 = new Sommet(0);
+  Arbo A1 = new Sommet(1);
+  Arbo A2 = new Sommet(2);
+  Arbo A3 = new Sommet(3);
+  Arbo A4 = new Sommet(4);
+  Arbo A5 = new Sommet(5);
+  Arbo A6 = new Sommet(6);
+
+  A3->AjouterSuccesseur(A6);
+  A1->AjouterSuccesseur(A5);
+  A3->AjouterSuccesseur(A4);
+  A2->AjouterSuccesseur(A3);
+  A0->AjouterSuccesseur(A2);
+  A0->AjouterSuccesseur(A1);
+
+  cout<<" rec A0  ";
+  TraverseePrefixeRec(A0);
+  cout<< endl;
+  cout<<" iter A0  ";
+  TraverseePrefixeIt(A0);
+  cout<< endl;
+  cout<<" largeur  ";
+  TraverseeLargeur(A0);
+  cout<< endl;
+
+
+  A3->RetirerSuccesseur(A4);
+  A3->RetirerSuccesseur(A6);
+  //Alors, pourquoi ? pourquoi essaie t'on de retirer A5 et A2 (respectivement
+  //fils de A1 et de A0 ?) il y a comme un soucis...
+  cout<<"rec A0  apres retrait   ";
+  TraverseePrefixeRec(A0);
+  cout<< endl;
+  cout<<" iter A0  ";
+  TraverseePrefixeIt(A0);
+  cout<< endl;
+  return 1;
+}
+//g++ -Wall Arbo.cpp -o prog