Soyez le premier à donner votre avis sur cette source.
Vue 3 387 fois - Téléchargée 256 fois
//// 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*)).
┌─ 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: --
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.