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
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.