Arbre binaire G) Bibliothèque logicielle itérative

Télécharger le projet
Commenter

Description

Bonjour,

Le même programme que sous "Arbre binaire F) Bibliothèque logicielle récursive" est utilisé pour la bibliothèque concernant les arbres binaires, basés sur des algorithmes itératifs:
qui contient également des codes des routines suivantes:
‥ Insert
‥ Traversal
‥ Search
‥ Size
‥ Height
‥ Extract

Fichier TreeNode.h: 
//// TreeNode.h (itérative)

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
    TreeNode *nod=this;
    do {
      int cmp=strcmp(name,nod->key);
      if (cmp<0) {
        if (nod->petit) nod=nod->petit;
        else {nod->petit=new TreeNode(name); return nod->petit;}
      } else if (cmp>0) {
        if (nod->grand) nod=nod->grand;
        else {nod->grand=new TreeNode(name); return nod->grand;}
      } else return 0; // cmp==0: double
    } while (1);
  }

  void Traversal(void (*Do)(TreeNode*)) { // itératif avec stack
    std::stack<TreeNode*> stk;
    TreeNode *nod=this;
    do {
      while (nod) {stk.push(nod); nod=nod->petit;}
      if (stk.empty()) return;
      nod=stk.top(); stk.pop();
      Do(nod);
      nod=nod->grand;
    } while (1);
  }
  
  TreeNode *Search(char name[]) { 
    TreeNode *nod=this;
    do {
      int cmp=strcmp(name,nod->key);
      if (cmp<0) {if (nod->petit) nod=nod->petit; else return 0;}
      else if (cmp>0) {if (nod->grand) nod=nod->grand; else return 0;}
      else return nod;
    } while (1);
  }
 
  int Size() { // non recursif (itératif) avec stack
    std::stack<TreeNode*> stk;
    TreeNode *nod=this;
    int siz=0;
    do {
      while (nod) {stk.push(nod); nod=nod->petit;}
      if (stk.empty()) return siz;
      nod=stk.top(); stk.pop();
      ++siz;
      nod=nod->grand;
    } while (1);
  }

  int Height() {
    std::queue<TreeNode *> que;
    que.push(this);
    int n,hgt=0;
    while (n=que.size()) {
      while (n>0) {
        TreeNode *nod=que.front();
        que.pop();
        if (nod->petit) que.push(nod->petit);
        if (nod->grand) que.push(nod->grand);
        n--;
      }
      hgt++;
    }
    return hgt;
  }

  TreeNode *Extract(TreeNode **adr,char name[]) { // this sans importance
    if (*adr==0) return 0;
    do {
      TreeNode *nod=*adr;
      int cmp=strcmp(name,nod->key);
      if (cmp<0) {
        if (nod->petit) {adr=&(nod->petit); nod=nod->petit;} else return 0;
      } else if (cmp>0) {
        if (nod->grand) {adr=&(nod->grand); nod=nod->grand;} else return 0;
      } else { // name==nod->key: nod (pointé par *adr) est à extraire
        TreeNode *sml=nod->petit,*big=nod->grand;
        if (sml) {
          if (big) { // deux enfants petit and grand
            if (sml->grand) { // cherche pgn, plus grand noeud du sous-arbre sml
              TreeNode *pcd=sml,*pgn=sml->grand;
              while (pgn->grand) {pcd=pgn; pgn=pgn->grand;}
              pcd->grand=pgn->petit; pgn->petit=sml; pgn->grand=big; *adr=pgn;
            } else {sml->grand=big; *adr=sml;}
          } else *adr=sml; // 1 enfant petit
        } else *adr=big; // 1 enfant grand ou pas d'enfants
        return nod; // return nod, le TreeNode* extrait
      }
    } while (1);
  } // l'appel initial recommandé:  root->Extract(&root,name)
};

Le même 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)
d: display
s nom: search nom
e nom: extract nom

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

Par exemple, pour obtenir l'image de capture, on "tape" au clavier (à l'ouverture) rrrri haha rrrrtd↲;
puis e yfd td↲;
et finalement e haha td↲.

Pour la fonction Extract, j'ai d'abord repris le code de ExtractNode proposé dans Arbre binaire E) Extraction.
 
 
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)
CodeS-SourceS: Arbre binaire E) Extraction
CodeS-SourceS: Arbre binaire F) Bibliothèque logicielle récursive
 
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)