Arbre binaire F) Bibliothèque logicielle récursive

Télécharger le projet
Commenter

Description

Bonjour,

Après avoir présenté les différentes fonctions concernant les arbres binaires, en voici deux bibliothèques, basées sur des algorithmes récursifs et itératifs:
‥ Arbre binaire F) Algorithmes récursifs (le présent article)
‥ Arbre binaire G) Algorithmes itératifs

Elles contiennent les codes des routines suivantes:
‥ Insert
‥ Traversal
‥ Search
‥ Size
‥ Height
‥ Extract
Ainsi qu'un outil de représentation Display (pour de "petits" arbres).

Pour simplifier ce code et pour suivre la tendance générale, je supprime la structure Object:TreeObj en introduisant la clé key directement dans TreeNode.
Par contre, cette clé n'est pas un nombre entier, mais un texte (chaine de caractères).

Fichier TreeNode.h: 
int MAX(int a,int b) {return (a>b)?a:b;}

struct TreeNode {
  TreeNode *petit,*grand;
  char *key;

  TreeNode(char name[]) { // constructor
    int n=strlen(name)+1;
    petit=0; grand=0;
    key=new char[n]; strcpy_s(key,n,name);
  }

  TreeNode *Insert(char name[]) { // insert new TreNode(name) in this
    int cmp=strcmp(name,key);
    if (cmp<0) {
      if (petit) return petit->Insert(name);
      else {petit=new TreeNode(name); return petit;}
    }
    if (cmp>0) {
      if (grand) return grand->Insert(name);
      else {grand=new TreeNode(name); return grand;}
    }
    return 0; // cmp==0: double
  }

  void Traversal(void (*Do)(TreeNode*)) {
    if (petit) petit->Traversal(Do);
    Do(this);
    if (grand) grand->Traversal(Do);
  }

  TreeNode *Search(char name[]) {
    int cmp=strcmp(name,key);
    if (cmp<0) return (petit)?petit->Search(name):0;
    if (cmp>0) return (grand)?grand->Search(name):0;
    return this;
  }
  
  int Size() {
    return 1+((petit)?petit->Size():0)+((grand)?grand->Size():0);
  }

  int Height() {
    return 1+MAX((petit)?petit->Height():0,(grand)?grand->Height():0);
  }

  TreeNode *Extract(TreeNode **adr,char name[]) { // on doit avoir: (*adr)=this
    int cmp=strcmp(name,key);
    if (cmp<0) return (petit)?petit->Extract(&petit,name):0;
    else if (cmp>0) return (grand)?grand->Extract(&grand,name):0;
    else { // k==key: this est à extraire (cette partie du code est itérative)
      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 this;
    }
  } // l'appel initial doit être:  root->Extract(&root,name)
};

Le logiciel permet, avec la "vieille méthode console", de tester les fonctions de la "library" ou de toute autre bibliothèque logicielle d'arbres binaires que vous aurez crée.

La syntaxe des commandes tapés au clavier est:
i nom: insert nom
r: insert (nom aléatoire)
t: traversal (name list)
d: display
s nom: search nom
e nom: extract nom

‥ Les noms se terminent par '↲' (return) ou ' ' (sinon, les espaces sont ignorés).
‥ On peut entrer plusieurs commandes sur une même ligne.

Par exemple, pour obtenir ce qui correspond à l'image de capture, on "tape" au clavier (à l'ouverture) rrrrri haha rrrrr↲, puis d↲ et t↲.

Finalement, ce programme peut très utile pour tester et mettre au point ses propres routines d'arbres binaires.
 
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)