Arbre binaire C) Recherche
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.
Avez-vous remarqué que le "display" a été légèrement modifié ?
Bonne lecture ...
CodeS-SourceS: Arbre binaire A) Insertion et Parcours
CodeS-SourceS: Arbre binaire B) Affichage (simple)
WikipediA: Binary search tree
Developez.com: Introduction aux arbres
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
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.