Arbre binaire A) Insertion et Parcours

Télécharger le projet
Commenter

Description

Bonjour,

Voici une série d'articles évolutifs et personnels consacrés aux arbres (de recherche) binaires.

Un arbre binaire (Binary Tree) est une structure qui permet des opérations rapides sur de grands ensembles d'objets totalement ordonnés.
Chaque objet (this) doit donc pouvoir être comparé à un autre objet obj à l'aide d'une fonction "int Compare(NodeObj *obj)":
‥ return < 0 : this < obj.
‥ return = 0 : this = obj.
‥ return > 0 : this > obj.

Commençons par les deux opérations élémentaires d'insertion (Insert) et de parcours (Transversal) avec des codes récursifs ou non récursifs.

Les codes récursifs sont en général plus démonstratifs et plus simples à programmer, alors que les autres (dits itératifs) peuvent être plus rapides.

A part pour quelques opérations simples (tels que Insert ou Search), il est nécessaire d'utiliser une pile (stack) pour pouvoir obtenir un code non récursif:
 

Insert et Transversal 

//// TreeNode.h

struct TreeObj {
  virtual int Compare(TreeObj *obj)=0;
}; // return <0: this < obj;  return 0: this == obj;  return >0: this > obj

struct TreeNode {
  TreeNode *left,*right;
  TreeObj *object;

  TreeNode(TreeObj *o) {left=0; right=0; object=o;} // constructeur: o != 0

  bool InsertRec(TreeNode *p) { // récursif
    int c=object->Compare(p->object);
    if (c<0) {
      if (p->left) return Insert(p->left); else {p->left=this; return true;}
    } else if (c>0) {
      if (p->right) return Insert(p->right); else {p->right=this; return true;}
    }
    return false; // c==0
  }

  bool Insert(TreeNode *p) { // non récursif (itératif): p != 0
    int c;
    do {
      c=object->Compare(p->object);
      if (c<0) {
        if (p->left) p=p->left; else {p->left=this; return true;}
      } else if (c>0) {
        if (p->right) p=p->right; else {p->right=this; return true;}
      }
    } while (c);
    return false;
  }

  void TraversalRec(void (*Do)(TreeNode*)) { // récursif
    if (left) left->TraversalRec(Do);
    Do(this);
    if (right) right->TraversalRec(Do);
  }

  void Traversal(void (*Do)(TreeNode*)) { // non récursif (itératif) avec stack
    std::stack<struct TreeNode*> stk;
    TreeNode *n=this;
    do {
      while (n) {stk.push(n); n=n->left;}
      if (stk.empty()) return;
      n=stk.top(); stk.pop();
      Do(n);
      n=n->right;
    } while (1);
  }
};
Dans le cas de Transversal, la pile s'utilise avec stack<struct TreeNode*>.

Pour des routines strictement itératives (c.-à-d. sans stack du tout), on peut ajouter un pointeur parent dans la structure TreeNode (en plus de TreeNode *left,*right;) ou alors utiliser la méthode Morris.

Introduisons l'objet BinaryTree pour montrer comment "utiliser" les routines de base Insert et Transversal: 
//// BinaryTree.h

struct BinaryTree {
  TreeNode *root=0;

  bool Insert(TreeObj *obj) {
    TreeNode *nod=new TreeNode(obj);
    if (root) return nod->Insert(root);
    root=nod; return true;
  }

  bool InsertRec(TreeObj *obj) { // récursif
    TreeNode *nod=new TreeNode(obj);
    if (root) return nod->InsertRec(root);
    root=nod; return true;
  }

  void Traversal(void (*Do)(TreeNode*)) { // non récursif
    if (root) root->Traversal(Do);
  }

  void TraversalRec(void (*Do)(TreeNode*)) {
    if (root) root->TraversalRec(Do);
  }
};


Le programme BinaryTree.cpp> donne l'output représenté dans l'image de capture.
 
 
Bonne lecture ...
 

Liens

WikipédiA: Arbre binaire
WikipédiA: Arbre binaire de recherche
Stanford: Binary Trees
Algorithmes et programmes sur les arbres binaires
François DENIS: Arbres binaires de recherche
 
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)