Arbre binaire B) Affichage (simple)

Soyez le premier à donner votre avis sur cette source.

Vue 348 fois - Téléchargée 42 fois

Description

Bonjour,

L'affichage d'un petit arbre binaire (avec sa structure) sert le plus souvent à illustrer les conséquences d'une opération.

Comme nous verrons plus loin, il est utile (ou nécessaire) de parcourir un arbre itérativement que lorsque la hauteur (longueur maximale des branches) est grande.
Cette hauteur peut être immense lorsque le nombre d'éléments est énorme ou lorsque l'arbre est mal équilibré.

Le fait d'avoir peu d'éléments nous permet ici de nous contenter d'une version récursive pour notre affichage sur la console.

Analysons l'arbre binaire obtenu après les 10 insertions:
"Mm" ,"Rrrr", "Ppp", "Ii, "Kk", "A", "J", "Nn", "Xx", "Eeee".
Essayez avec le lien USFCA: Binary Search Tree: on obtient l'image USFCA.jpg.
 

Affichage

L'affichage horizontal proposé correspondant aux insertions ci-dessus, ressemble à:
lev = 0  1  2  3
i
0        ┌─ A
1        │  └─ Eeee
2     ┌─ Ii
3     │  │  ┌─ J
4     │  └─ Kk
5   ─ Mm
6     │     ┌─ Nn
7     │  ┌─ Ppp
8     └─ Rrrr
9        └─ Xx
10 = nbE
On y constate que:
‥ à chaque ligne i correspond un élément
‥ les éléments sont ordonnés de haut en bas
‥ la clé (ou le nom) de l'élément peut être de longueur variable
 

Display.h

Après une quinzaine d'heures de tâtonnements et de mises au point (je ne suis plus très rapide !), voici le code obtenu:
//// Display.h
const int MaxEle=256,CarParLin=81;

struct Affichage {
  int nbE,lev,Lev[MaxEle],Prn[MaxEle];
  TreeNode *Arr[MaxEle];

  Affichage(TreeNode *root) {
    if (root) {nbE=0; lev=0;} else return;
    Recur(root); 
    char lin[MaxEle*CarParLin],*ln=lin,*l,*ll;
    memset(lin,' ',nbE*CarParLin);
    for (int i=0; i<nbE; ++i,ln+=CarParLin) {
      l=ln+3*Lev[i];
      if (Lev[i]) {
        int n=Prn[i]-i;
        ll=l;
        if (n>0) {*l=218; // '┌'
          for (int k=1; k<n; ++k) {ll+=CarParLin; *ll=179;} // '│'
        } else {*l=192; // '└'
          for (int k=1; k<-n; ++k) {ll-=CarParLin; *ll=179;} // '│'
        }
      }
      *++l=196; // '─'
      Object *o=(Object*)Arr[i]->object;
      strcpy_s(l+2,32,o->key);
    }
    ln=lin;
    for (int i=0; i<nbE; ++i,ln+=CarParLin) printf("%sn",ln);
  }

  int Recur(TreeNode *nod) { // nod != 0
    if (nbE>=MaxEle) return 0;
    if (nod->left) {++lev; Prn[Recur(nod->left)]=nbE; --lev;}
    int num=nbE++;
    Arr[num]=nod; Lev[num]=lev;
    if (nod->right) {++lev; Prn[Recur(nod->right)]=num; --lev;}
    return num;
  }
};

 

Output

Le programme BinaryTree.cpp génère l'output suivant:
      ┌─ A
      │  └─ Eeee
   ┌─ Ii
   │  │  ┌─ J
   │  └─ Kk
 ─ Mm
   │     ┌─ Nn
   │  ┌─ Ppp
   └─ Rrrr
      └─ Xx

NbE = 10
======================================

      ┌─ 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


Modification par rapport à l'article A) Insertion et Parcours:
Les fichiers BinaryTree.h, TreeNode.h n'on pas été changés.
<grasBinaryTree.cpp</gras> a été adapté et j'en ai extrait la structure struct Object:TreeObj{…} pour en faire Object.h.
 
 
Bonne lecture ...
 

Liens:

CodeS-SourceS: Arbre binaire A) Insertion et Parcours
USFCA: Binary Search Tree
 

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Commenter la réponse de William VOIROL

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.