Arbre binaire C) Recherche

Soyez le premier à donner votre avis sur cette source.

Vue 1 129 fois - Téléchargée 111 fois

Télécharger le projet
Commenter

Description

Bonjour,

Ce troisième article sur les arbres binaires augmente notre objet TreeNode avec les opérations de recherche et de nombre de nœuds.
Et chaque fois à l'aide d'une routine récursive et d'une autre itérative.

Le nombre de nœuds (fonctions SizeRecur, Size) peut également être maintenu (lors d'insertions et d'extractions) dans l'objet BinaryTree.

La recherche (fonctions SearchRecur, Search) est habituellement l'une des opérations les plus utilisées dans l'exploitation d'un arbre binaire de recherche.
 

TreeNode.h 

//// 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 *obj) {left=0; right=0; object=obj;} // constructor: obj != 0

  bool InsertRecur(TreeNode *nod) { // recursif
    int cmp=object->Compare(nod->object);
    if (cmp<0) {
      if (nod->left) return Insert(nod->left);
      else {nod->left=this; return true;}
    } else if (cmp>0) {
      if (nod->right) return Insert(nod->right);
      else {nod->right=this; return true;}
    }
    return false; // cmp==0
  }

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

  void TraversalRecur(void (*Do)(TreeNode*)) { // recursif
    if (left) left->TraversalRecur(Do);
    Do(this);
    if (right) right->TraversalRecur(Do);
  }

  void Traversal(void (*Do)(TreeNode*)) { // non recursif (itératif) avec stack
    std::stack<TreeNode*> stk;
    TreeNode *tn=this;
    do {
      while (tn) {stk.push(tn); tn=tn->left;}
      if (stk.empty()) return;
      tn=stk.top(); stk.pop();
      Do(tn);
      tn=tn->right;
    } while (1);
  }

  TreeNode *SearchRecur(TreeObj *obj) { // recursif
    int cmp=obj->Compare(object);
    if (cmp<0)
      {if (left) return left->SearchRecur(obj); else return 0;}
    if (cmp>0)
      {if (right) return right->SearchRecur(obj); else return 0;}
    return this;
  }

  TreeNode *Search(TreeObj *obj) { // itératif
    int cmp;
    TreeNode *nod=this;
    do {
      cmp=obj->Compare(nod->object);
      if (cmp<0) {
        if (nod->left) nod=nod->left; else return 0;
      } else if (cmp>0) {
        if (nod->right) nod=nod->right; else return 0;
      }
    } while (cmp!=0);
    return nod;
  }
  
  int SizeRecur() { // recursif
    return 1+((left)?left->SizeRecur():0)+((right)?right->SizeRecur():0);
  }

  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->left;}
      if (stk.empty()) return siz;
      nod=stk.top(); stk.pop();
      ++siz;
      nod=nod->right;
    } while (1);
  }
};
La routine int Size() est basée sur void Traversal(void (*Do)(TreeNode*)).
 
 

Résultat de BinaryTree.cpp

En compilant et en exécutant BinaryTree.cpp, on obtient sur la console: 

        ┌─ A
        │   └─ Eeee
    ┌─ Ii
    │   │   ┌─ J
    │   └─ Kk
 ─ Mm
    │       ┌─ Nn
    │   ┌─ Ppp
    └─ Rrrr
        └─ Xx

nbE=10, SizeRec=10, Size=10

================================

Insert (48 objets):
HQ H M AYL LF XF RCV C GG WK
NQDU WF FOZV RTK PR P G RP RVYS MWCY
Y C PEV KEF MZ IMKK SVW R NZK CXF
TL GYP FAD OO FXZ CO JUV VABO GPO YLF
BNPL VRVI YA YEH Q QRQP X J

        ┌─ AYL
        │   │   ┌─ BNPL
        │   └─ C
        │       │           ┌─ CO
        │       │       ┌─ CXF
        │       │       │   └─ FAD
        │       │   ┌─ FOZV
        │       │   │   │   ┌─ FXZ
        │       │   │   └─ G
        │       └─ GG
        │           │   ┌─ GPO
        │           └─ GYP
    ┌─ H
 ─ HQ
    │           ┌─ IMKK
    │           │   │   ┌─ J
    │           │   └─ JUV
    │       ┌─ KEF
    │   ┌─ LF
    └─ M
        │           ┌─ MWCY
        │           │   └─ MZ
        │       ┌─ NQDU
        │       │   │       ┌─ NZK
        │       │   │       │   └─ OO
        │       │   │   ┌─ P
        │       │   │   │   └─ PEV
        │       │   └─ PR
        │       │       │   ┌─ Q
        │       │       │   │   └─ QRQP
        │       │       └─ R
        │   ┌─ RCV
        │   │   │           ┌─ RP
        │   │   │       ┌─ RTK
        │   │   │       │   └─ RVYS
        │   │   │       │       └─ SVW
        │   │   │       │           └─ TL
        │   │   │       │               └─ VABO
        │   │   │       │                   └─ VRVI
        │   │   │   ┌─ WF
        │   │   └─ WK
        │   │       └─ X
        └─ XF
            └─ Y
                │   ┌─ YA
                │   │   └─ YEH
                └─ YLF

nbE=47, SizeRecur=47, Size=47

Search:
"HQ" Recur: OK, Iterat: OK
"XF" Recur: OK, Iterat: OK
"NQDU" Recur: OK, Iterat: OK
"P" Recur: OK, Iterat: OK
"Y" Recur: OK, Iterat: OK
"IMKK" Recur: OK, Iterat: OK
"TL" Recur: OK, Iterat: OK
"CO" Recur: OK, Iterat: OK
"BNPL" Recur: OK, Iterat: OK
"QRQP" Recur: OK, Iterat: OK
"LOOV" Recur :--, Iterat: --
"O" Recur :--, Iterat: --
"U" Recur :--, Iterat: --
"WH" Recur :--, Iterat: --
"S" Recur :--, Iterat: --
"CB" Recur :--, Iterat: --
"COKS" Recur :--, Iterat: --

Avez-vous remarqué que le "display" a été légèrement modifié ?
 
Bonne lecture ...
 

Liens:


CodeS-SourceS: Arbre binaire A) Insertion et Parcours
CodeS-SourceS: Arbre binaire B) Affichage (simple)
WikipediA: Binary search tree
Developez.com: Introduction aux arbres

 
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)