Arbre binaire E) Extraction

Télécharger le projet
Commenter

Description

Bonjour,

L'extraction figure plus rarement parmi les opérations proposées avec les arbres binaires, car elle est plus compliquée même avec une programmation récursive.

A la place du terme habituel "supprimer" (en: delete), j'aime mieux utiliser "extraire" (ou "retirer").
En effet, un nœud n'est pas forcément détruit, mais peut très bien être extrait d'un arbre, puis inséré dans un autre.

Pour éviter qu'un nœud soit introduit dans plusieurs arbres, on pourrait ajouter et traiter une variable booléenne "isInserted" dans la structure TreeNode.

Code de la fonction ExtractRecur dans la structure TreeNode: 
struct TreeObj {
  virtual int Compare(TreeObj *obj)=0;
  // return <0: this < obj; 0: this == obj; >0: this > obj
  virtual char *Key()=0; // For tests
};

struct TreeNode {
  TreeNode *petit,*grand;
  TreeObj *object;

  // ...

  bool ExtractRecur(TreeNode **adr,TreeObj *obj) { // récursif
    cmp=obj->Compare(object);
    if (cmp<0) return (petit)?petit->ExtractRecur(&petit,obj):false;
    else if (cmp>0) return (grand)?grand->ExtractRecur(&grand,obj):false;
    else { // cmp==0: this est à extraire
      if (petit) {
        if (grand) { // deux enfants petit and grand
          if (petit->grand) { // cherche plus grand noeud du sous-arbre petit
            TreeNode *pcd=petit,*pgn=petit->grand;
            while (pgn->grand) {pcd=pgn; pgn=pgn->grand;}
            pcd->grand=pgn->petit; pgn->petit=petit; pgn->grand=grand; *adr=pgn;
          } else {petit->grand=grand; *adr=petit;}
        } else *adr=petit; // 1 enfant petit
      } else if (grand) *adr=grand; // 1 enfant grand
      else *adr=0; // pas d'enfants
      return true;
    }
  }
};
Le code itératif ExtractNode est assez "ressemblant".

Aussi les termes left (gauche) et right (droite) ont été remplacés par petit et grand, car selon la représentation de l'arbre (ici horizontale), les mots gauche et droite perdent leur sens et devraient être haut et bas.

Avec la version gratuite de Microsoft Visual Studio Express, il suffit de créer un nouveau projet vide et d'y ajouter dans "Fichiers sources" l'élément existant BinaryTree.cpp.
Les 4 fichiers xyz.h n'ont pas besoin d'être ajoutés explicitement, mais doivent simplement figurer dans le même dossier que BinaryTree.cpp.
Lancez la compilation et l'exécution pour faire apparaitre à la console d'autres situations (que celles de l'image de capture).
 
Bonne lecture ...
 
 

Liens:

CodeS-SourceS: Arbre binaire A) Insertion et Parcours
CodeS-SourceS: Arbre binaire B) Affichage (simple)
CodeS-SourceS: Arbre binaire C) Recherche
CodeS-SourceS: Arbre binaire D) Equilibrage (Balancing)
 
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)