[Fermé] Arbre binaire de recherche en C (aide)

Ouaip mais dans le main() les 4 valeurs test ne sont jamais égales donc ca vient pas de la ♠

Au cas ou voila la fonction findKey et InOrder (affiche les noeuds en ordre croissant grace aux propriété des arbres binaires de recherche).

bool findKey(int i, struct tree *T)
{
//Completer la fonction pour qu'elle retourne true si i est dans l'arbre T, et false sinon.

struct tree *pTree;
if (T->root == NULL){
return false;
}
else {
if (T->root->value == i){
return true;
}
else if (T->root->value > i){
pTree->root = T->root->lChild;
findKey(i,pTree);
}
else{
pTree->root = T->root->rChild;
findKey(i,pTree);
}
}
}

void inOrder(struct tree *T)
{
//Completer la fonction pour obtenir un parcour recursif "en-ordre" de l'arbre T.
//(O(n) puisque passe par chaque noeud.
struct tree *pTree;
if (T->root->lChild != NULL){
pTree->root = T->root->lChild;
inOrder(pTree);

}
printf("%d",T->root->value);
if (T->root->rChild != NULL){
pTree->root = T->root->rChild;
inOrder(pTree);
}

}

Merci pour ton aide en tout cas, je galère un peu a paufiner tout ca...

Ceci dit je viens de modifier légèrement ma fonction insert en prenant compte le problème d'égal.

Ca m'a permis d'afficher une source de problème :

J'ai rajouté une 3 ème condition ou la console affiche "Element déjà présent" quand c'est égal, sauf qu'elle ne le fait pas et qu'elle le rajoute quand même à l'arbre (je vérifie avec des printf chaque fois qu'un élément est "ajouté".

En gros si je lui demande de rajouter 52915

Il va m'afficher "52915" et pas "5291 élément déjà présent" comme si il avait pas retenu...

Je pense que j'ai trouvé l'erreur.

Tu fais :

pTree = T;

au début de ta fonction puis tu fais :

pTree->root = T->root->rChild;

c'est-à-dire que tu modifies T puisque pTree pointe vers T.

Il te suffit de rajouter pTree = constructNewTree() au dessus des lignes :

pTree->root = T->root->rChild;
pTree->root = T->root->lChild;

btw, la ligne pTree = T; ne sert à rien.

A confimer mais je crois que tu viens de gagner un nouveau fan JivJav je viens de le faire dans les fonctions insert et find et ca marche

Si tu pouvais m'expliquer un peu pourquoi, j'ai du mal a suivre le comment de la chose... Je suis un peu perdu au milieu de ces pointeurs qui vont dans tous les sens.

Je vais tâcher de finir le reste par même histoire de pas trop te faire perdre ton temps mais si j'ai un mini soucis je re ici si ca ne te dérange pas

nope, ça me dérange pas.

Je vais essayer de t'expliquer le problème de manière claire.

Dans le main, tu as :

insertKey(1,T); // avec T un pointeur

Puis dans insertKey(), on trouve :

struct tree *pTree; // tu définis un pointeur, ok
pTree = T; // Tu affectes à ce pointeur l'adresse de l'arbre crée dans le main. pTree et T pointe donc tous les deux vers la même chose.
pTree->root = T->root->lChild; // Et là, tu changes le root de ton arbre en lui affectant en fait le demi-arbre gauche. Toute la partie droite de l'arbre initiale est donc zappée.

Au lieu d'avoir

-----5
----2-9
---1

tu te retrouves donc avec

----2
---1

Ah, ça me rappelle ma jeunesse

Sinon je suis sidéré qu'on enseigne encore le C, mais bon.

Allez c'est ma tournée :

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> 


struct node {
  struct node *lChild;
  struct node *rChild;
  int value;
};

struct tree {
  struct node *root;
};



struct node* constructNewNode(int i) {
  /* cree une nouvelle instance de node */
  struct node* n = (struct node *)malloc(sizeof(struct node));
  n->value = i;
  n->lChild = n->rChild = NULL;
  return n;
}



struct node* nodeInsert(int i, struct node* n) {
  if (i < n->value) 
    /* si la feuille gauche est non nulle, on insere dessus, sinon on la cree */
    return ( n->lChild != NULL ? nodeInsert(i, n->lChild) : (n->lChild = constructNewNode(i)) );
  else 
    /* si la feuille droite est non nulle, on insere dessus, sinon on la cree */
    return ( n->rChild != NULL ? nodeInsert(i, n->rChild) : (n->rChild = constructNewNode(i)) );
}


struct node* nodeFindKey(int i, struct node* n)
{
  if (n != NULL) {
    if (i == n->value)
      return n;
    else if (i < n->value)
      return nodeFindKey(i, n->lChild);
    else
      return nodeFindKey(i, n->rChild);
  }
  else 
    return NULL;
}


void nodeDeleteKey(struct node* n) {
  if (n != NULL) {
    nodeDeleteKey(n->lChild);
    nodeDeleteKey(n->rChild);
    free(n);
  }
}


struct tree* constructNewTree() {

  struct tree *T = malloc(sizeof(struct tree));
  T->root = NULL;

  return T;
}


void insertKey(int i, struct tree* T) {
  if (T->root == NULL) 
    T->root = constructNewNode(i);
  else
    nodeInsert(i, T->root);
}


bool findKey(int i, struct tree *T) {
  return ( nodeFindKey(i, T->root) != NULL );
}


void deleteKey(int i, struct tree *T) {
  struct node* temp = T->root; 
  struct node* prev = T->root; 

  while (1)  { 
    if (temp == NULL) 
      return; 
    else if (temp->value == i) { 
      bool isLeft = (prev->lChild == temp);
      /* cas ou une seule feuille vide */
      if (temp->lChild == NULL && isLeft) {  
        prev->lChild = temp->rChild; 
        free(temp); 
        return;
      } 
      if (temp->rChild == NULL && isLeft) { 
        prev->lChild = temp->lChild; 
        free(temp); 
        return; 
      } 
      if (temp->lChild == NULL && !isLeft) { 
        prev->rChild = temp->rChild; 
        free(temp); 
        return; 
      } 
      if (temp->rChild == NULL && !isLeft) { 
        prev->rChild = temp->lChild; 
        free(temp); 
        return; 
      } 
      /* le cas ou les 2 feuilles ne sont pas vides */
      while (temp->lChild != NULL && temp->rChild != NULL) { 
        temp->value = temp->rChild->value; 
        prev = temp; 
        temp = temp->rChild; 
      } 
      if (temp->rChild == NULL) prev->rChild = temp->lChild; 
      if (temp->lChild == NULL) prev->rChild = temp->rChild; 
      free(temp); 
      return; 
    } 
    
    prev = temp; 
    
    if (temp->value < i) 
      temp = temp->rChild; 
    else 
      temp = temp->lChild; 
  } 
} 


void nodeInOrder(struct node* n) {
  if (n != NULL) {
    nodeInOrder(n->lChild);
    printf("%d ", n->value);
    nodeInOrder(n->rChild);
  }
}


void inOrder(struct tree *T) {
  nodeInOrder(T->root);
  printf("\n");
}



void deleteTree(struct tree *T) {
  nodeDeleteKey(T->root);
  free(T);
  T = NULL;
}


int main() {
  struct tree* T;

  printf("Debut\n");

  T = constructNewTree();

/*
  insertKey(5, T);
  insertKey(2, T);
  insertKey(9, T);
  insertKey(1, T);
*/

  insertKey(10, T);
  insertKey(7, T);
  insertKey(8, T);
  insertKey(9, T);
  insertKey(5, T);
  insertKey(4, T);
  insertKey(6, T);
  insertKey(14, T);
  insertKey(11, T);
  insertKey(18, T);

  inOrder(T);

  deleteKey(6, T);
  inOrder(T);

  deleteTree(T);
  
  printf("Fin \n\n");
  return 0;
}

tu sais il n'y pas non plus que de l'orientée objet chika

Message original de Overdozz
tu sais il n'y pas non plus que de l'orientée objet chika

Non, la preuve

Mais le C est un des langages les moins tolérants, donc pour enseigner la programmation sans trop de bugs je préconise plutôt pascal, ada, modula par exemple, du genre fortement typé, avant de noyer les jeunes avec des concepts comme les pointeurs et autres références. Pourquoi pas directement des tableaux de pointeurs sur fonctions. A noter qu'un ingé sur 5 est infoutu de définir correctement ce qu'est un pointeur...

Après, l'objet je ne suis ni pour ni contre, bien au contraire

J'essaye juste d'éviter le lisp (LISP: a Lot of Idiotics and Stupid Parenthesis), ou le prolog ♠_biggrin:

prolog c'est marrant

Why using C ?

Ok Jivjav j'ai capté !

Merci Chika pour tout ce beau code, par contre jusqu'ici j'ai réussi a éviter de rajouter des fonctions à côté et je crois que c'est ce que le prof préconise (même si il accepte les deux) donc je vais tenter de finir la dernière fonction sans ca.

Me reste DeleteKey qui est une des plus chiantes parait (à cause des changements de branche quand tu supprimes un noeud du milieu etc.., vais me baser sur le code de Chika et les conseils de Jiv pour essayer de pondre ca ce soir

(puis me reste encore deux parties dans le projet FML , c'est ca de faire en quasi dernière minute un projet donné y a 3 semaines )

mouais, j'ai appris avec C et je le vis bien ^^

Ca reste possible, mais ça ne convient pas à tout le monde.

Sans compter que dans ce cas, autant enseigner le php, c'est un peu plus utile aujourd'hui que le C.

Putain le cas ou le noeud à supprimer a deux enfants est juste horrible a faire de manière récursive et sans rajouter de fonctions. J'ai mal au crâneeeeeeee.

Voilà comment je ferais dans le cas où il y a 2 fils.

Tu remplace la valeur du nœud à supprimer par la valeur du nœud situé le plus à droite dans le sous-arbre de gauche, c'est-à-dire la plus grande des valeurs parmi les valeurs qui sont inférieures à la valeur à supprimer. En terme de code, ça donne un truc comme ça :

void deleteKey(int i, struct tree *T)
{
//Completer la fonction pour qu'elle supprime l'element i dans l'arbre T.

// Ici tu cherches le noeud correspondant à la clé i et tu fais la suppression dans les cas faciles

// Pour le cas où le noeud possède 2 fils

struct node* last = noeud->lChild;
while (last->rChild != NULL) {
last = last->rChild;
}

// last contient le noeud qui doit remplacer noeud
// On stocke la valeur de ce noeud
int val = last->value;

// Il faut ensuite supprimer last
struct tree *nTree = constructNewTree();
nTree->root = last;
deleteKey(val, nTree);
free(nTree);

// On change la value de noeud
noeud->value = val;

}

ça devrait marcher je pense

Yop , ca marche pas trop selon les cas (parfois ca supprime mais ca rajoute un doublon d'un autre, parfois boucle infinie, parfois ca fait rien)

Je crois que je me suis planté dans toute ma manière de concevoir la fonction

Ici pour le côté mémoire dans les cas faciles j'ai rajouté un pTreeParent qui continuent le noeud parent du pTree a chaque itération (en tout cas théoriquement mais pt qu'a chaque passage de fonction je le réinitialise fin je sais pas trop)

En gros ca donne çà : (la denrière partie c'est ton code ou j'ai changé le nom des variables)

Désolé

Le 1ere if , else if else, c'est pour voir si l'élément est dans le graphe, si oui ==> on arrive au else;

Ensuite les 3 premiers cas ce sont les miens , censés être faciles, puis le tien à la fin.

void deleteKey(int i, struct tree *T){
//Completer la fonction pour qu'elle supprime l'element i dans l'arbre T.
//utiliser findKey a la place mais il faudrait qu'elle renvoit "l'adresse"(position) de l'élement ou qu'elle mette déjà le pointeur pTree a la bonne place

struct tree *pTree;
struct tree *pTreeParent;
if (T->root->value > i){
pTree = constructNewTree();
pTreeParent = constructNewTree();
pTreeParent->root = T->root;
pTree->root = T->root->lChild;
deleteKey(i,pTree);
}
else if(T->root->value < i){
pTree = constructNewTree();
pTreeParent = constructNewTree();
pTreeParent->root = T->root;
pTree->root = T->root->rChild;
deleteKey(i,pTree);
}
else {

if (T->root->lChild == NULL && T->root->rChild == NULL){
if (T->root < pTreeParent->root){
pTreeParent->root->lChild = NULL;
}
else{
pTreeParent->root->rChild = NULL;

}
free(T);
}

else if (T->root->lChild != NULL && T->root->rChild == NULL){
if (T->root < pTreeParent->root){
pTreeParent->root->lChild = T->root->lChild;
}
else{
pTreeParent->root->rChild = T->root->lChild;

}
free(T);
}
else if (T->root->lChild == NULL && T->root->rChild != NULL){

if (T->root < pTreeParent->root){
pTreeParent->root->lChild = T->root->rChild;
}
else{
pTreeParent->root->rChild = T->root->rChild;

}
free(T);
}

else {

struct node* lastNode = T->root->lChild;
while (lastNode->rChild != NULL) {
lastNode = lastNode->rChild;
}
int valEnd = lastNode->value;

// Il faut ensuite supprimer last
struct tree *nTree = constructNewTree();
nTree->root = lastNode;
deleteKey(valEnd, nTree);
free(nTree);

// On change la value de noeud
T->root->value = valEnd;

}

}

}

Message original de chika78
Ca reste possible, mais ça ne convient pas à tout le monde.

Sans compter que dans ce cas, autant enseigner le php, c'est un peu plus utile aujourd'hui que le C.

Nah, C++ ou Java c'est mieux imo.

Php est trop user friendly, du coup on comprend rien à ce qu'il se passe derrière (ça fonctionne tout seul).

pTreeParent->root = T->root;
pTree->root = T->root->lChild;

Je parie que ce sont ces deux lignes là qui font foirer, j'ai encore fait la même connerie qu'avant !

Ou alors mon pTreeparent ne sert à rien puisqu'il se supprime a chaque appel récuursif de la fonction... Tain suis perdu

Une nouvelle version :

void deleteKey(int i, struct tree *T) {
  struct node* temp; 
  struct node* prev; 

  temp = prev  = T->root;
  
  while (temp != NULL)  { 
    if (temp->value == i) { 
      /* on a trouve la key a effacer */
      bool isLeft = (prev->lChild == temp);
      /* cas ou une seule feuille vide */
      if (temp->lChild == NULL) {
        if (isLeft) 
          prev->lChild = temp->rChild; 
        else
          prev->rChild = temp->rChild; 
      }
      else if (temp->rChild == NULL) {
        if (isLeft) 
          prev->lChild = temp->lChild; 
        else
          prev->rChild = temp->lChild; 
      }
      else {
        /* le cas ou les 2 feuilles ne sont pas vides */
        while (temp->lChild != NULL && temp->rChild != NULL) { 
          temp->value = temp->rChild->value; 
          prev = temp; 
          temp = temp->rChild; 
        } 
        
        if (temp->rChild == NULL) prev->rChild = temp->lChild; 
        if (temp->lChild == NULL) prev->rChild = temp->rChild; 
      }
      free(temp); 
      return; 
    } 
    
    prev = temp; 
    
    if (temp->value < i) 
      temp = temp->rChild; 
    else 
      temp = temp->lChild; 
  } 
} 

De fait, celle-ci marche, je vais tâcher de la comprendre , et essayer de voir aussi pourquoi la mienne ne marchait pas Merci Chika

Dommage que ce ne soit pas récursif, ca va faire un peu suspect tout à coup