Arborescence quelconque 3 branches

**Onelove** · 21/09/2014, 22h58

Salut, je dois realiser un prog avec un arbre quelconque à 3 branches. Je bloque sur l'ajout de nouveau noeud aux branches (gauche droite et centre) je ne vois pas comment déplacer le pointeur à ces branches pour l'ajout du noeud. J'adorerai avoir une petite explication. Voilà mon bout de code3 (ça ce passe dans la methde ajouter noeud). Merci d'avance dans tous les cas.

source cpp

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
#include "Noeud.h"
 
Arbre::Arbre()
{
    m_pRacine = m_pCourant = NULL;
    m_nbNoeud = 0;
}
 
int Arbre::ajouterPremierNoeud(int data)
{
    Noeud * pNouveau = new Noeud(data); //creation d'un nouveau noeud
 
    if(pNouveau==NULL) //si plus de memoire retourne 0
        return 0;
 
    pNouveau->m_pPere = m_pRacine; // m_pPere prend l'adresse de m_pRacine
    m_pRacine = pNouveau; //le pointeur m_pRacine recupere le neoud pNouveau
 
    m_nbNoeud++; //un nouveau noeud est nee
 
    return 1; //tout c'est bien passe retourne 1
}
 
int Arbre::ajouterNoeud(int data)
{
    if(m_nbNoeud==0)//si le nombre de noeud est egal a zeros alors le premier noeud est le sommet de laborescance
        return ajouterPremierNoeud(data); // cree le premier noeud et on quitte la methode
 
    if(pNouveau->m_pBrancheGauche==NULL) // si la branche de gauche est vide on remplis celle la
    {
        Noeud * pNouveau = new Noeud(data); //sinon on cree un nouveau noeud avec la donee
        if(pNouveau == NULL) // si plus de memoire
            return 0;
 
        m_nbNoeud++;
        return 1;
    }
 
    else if(pNouveau->m_pBrancheCentre==NULL) // si la branche de gauche est prise est celle du centre ne l'est pas on la remplis
    {
        Noeud * pNouveau = new Noeud(data); //sinon on cree un nouveau noeud avec la donee
        if(pNouveau == NULL) // si plus de memoire
            return 0;
 
        m_nbNoeud++;
        return 1;
    }
 
    else // sinon on remplis celle de droite
    {
        Noeud * pNouveau = new Noeud(data); //sinon on cree un nouveau noeud avec la donee
        if(pNouveau == NULL) // si plus de memoire
            return 0;
 
        m_nbNoeud++;
        return 1;
    }
}

.h

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
#ifndef NOEUD_H_INCLUDED
#define NOEUD_H_INCLUDED
#include <stdlib.h>
 
class Arbre;
 
class Noeud
{
   friend class Arbre;
 
   private :
 
       int m_data;                    // Les données génériques du noeud.
       Noeud * m_pPere;               // Le
       Noeud * m_pBrancheGauche;      //pointeur de la branche de gauche
       Noeud * m_pBrancheCentre;      //pointeur de la branche central
       Noeud * m_pBrancheDroite;      //pointeur de la branche de droite
 
       Noeud( int & data){ m_data = data; m_pBrancheGauche = m_pBrancheCentre = m_pBrancheDroite = m_pPere = NULL;} // Constructeur Initialisation.
};
 
class Arbre
{
    private:
 
    Noeud* m_pRacine;  //La racine de l'abre
    Noeud* m_pCourant; //L'endroit ou se trouve le pointeur
    int m_nbNoeud;     //Le nombre de noeud dans l'arborescance
 
    public:
        Arbre();
        inline ~Arbre();
 
 
        void detruire_arbre(Noeud * arbre);
        void viderArbre();
 
        int ajouterPremierNoeud( int data);
        int ajouterNoeud( int data);
 
        void parcours_prefixe();
        void parcours_infixe();
        void parcours_suffixe();
 
        int ajouterGauche();
        int ajouterCentre();
        int ajouterDroite();
};
 
#endif // NOEUD_H_INCLUDED

**ternel** · 22/09/2014, 09h52

Bonjour!

Pour commencer, il y a plusieurs fautes techniques dans ton code.

Le constructeur est mal compris.
La création d'un objet se passe en trois temps:

trouver la mémoire, sur la pile ou le tas. Cela n'est pas le problème du constructeur
écrire quelque chose dans cette mémoire (initialisation)
mettre l'objet en état de marche.

L'étape deux est faite pour tous les membres de l'objet, y compris les classes de bases (et la table des virtuelles...).
Elle est configurable via la liste d'initialisation du constructeur appelé.
Donner une valeur à un membre dans le corps du constructeur signifie laisser le compilateur mettre une valeur par défaut au membre, puis changer celle-ci.
Dans certain cas, c'est presque pareil (un int) mais dans plein d'autre ca change tout: ca coute plus cher, ca exigera des tas de modification dans la mémoire (vecteur un peu gros).
Et au pire, ca ne compilera même pas: les constantes et les références.

Regarde la faq sur ce point

La fonction publique détruireArbre(Noeud*) me semble très suspecte.
Quand l'utilisateur devrait-il l'utiliser?

Par ailleurs, ta classe Arbre n'a que des pointeurs vers des noeuds. Je t'invite à utiliser une déclaration anticipée pour ne pas déclarer la classe dans le header public.

Enfin, ton Arbre ne devrait pas avoir de membre "courant".
L'arbre étant une forme de donnée, toute l'algorithmie (et donc les parcours) devrait être extérieur. Cela peut vouloir dire créer une classe (éventuellement interne) d'itérateurs.

Par contre, du point de vue fonctionnel, je ne connais pas l'algorithme de remplissage d'un arbre ternaire.
Pourrais-tu nous en dire plus.

**ternel** · 22/09/2014, 10h20

Au passage, j'ai demandé arbre ternaire à google, il m'a donné en premier lien notre faq algorithmie.

Comme quoi

**Onelove** · 22/09/2014, 13h47

Merci,

mais mon soucis c'était plutôt de se déplacer dans un arbre. Ne me grande pas... j'ai pas pus m’empêcher d'utiliser un pointeur Courant

(n'ayant pas vue les itératifs en court... car on a sauté ce chapitre....)

mes classes

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
 
class Noeud
{
   friend class Arbre;
 
   private :
 
       int m_data;                    // Les données génériques du noeud.
       Noeud * m_pBrancheGauche;      //pointeur de la branche de gauche
       Noeud * m_pBrancheCentre;      //pointeur de la branche central
       Noeud * m_pBrancheDroite;      //pointeur de la branche de droite
 
       Noeud( int & data){ m_data = data; m_pBrancheGauche = m_pBrancheCentre = m_pBrancheDroite = NULL;} // Constructeur Initialisation.
};
 
class Arbre
{
    private:
 
    Noeud* m_pRacine;  //La racine de l'abre
    Noeud* m_pCourant; //L'endroit ou se trouve le pointeur
    int m_nbNoeud;     //Le nombre de noeud dans l'arborescance
 
    public:
        //CONSTRUCTEUR
        Arbre(){m_pRacine = m_pCourant = NULL; m_nbNoeud = 0;}
 
        //DESTRUCTEUR
        inline ~Arbre();
 
        // METHODES D'AJOUT
        // Permet d'ajouter un element par rapport au courant.
        int ajouterPremierNoeud(int data);
        int ajouterGauche(int data);
        int ajouterCentre(int data);
        int ajouterDroite(int data);
        int ajouterNoeud(int data);
 
        //METHODES DEPLACER POINTEUR
        //Permt de deplacer le pointeur courant
        int bougeBrancheGauche();
        int bougeBrancheCentre();
        int bougeBrancheDroite();
        int bougeRacine();
 
        //METHODES DE PARCOUR
        void afficher();
};

donc voilà j'ai plutôt décomposé m'a fonction d'ajout en 4 méthode que voici.

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
int Arbre::ajouterPremierNoeud(int data)//creer le sommet de l'arbre
{
	Noeud * nouveau = new Noeud(data); // On cree le noeud.
	if (nouveau == NULL) // Si plus de memoire on quitte la methode
		return 0;
 
    m_pRacine = m_pCourant = nouveau; //Le pointeur de la racine prend l'adresse du pointeur courant et on place le noeud.
    ++m_nbNoeud;
 
    return 1;
}
 
int Arbre::ajouterGauche(int data)
{
	Noeud * nouveau = new Noeud(data); // On cree le noeud.
	if (nouveau == NULL) // Si plus de memoire on quitte la methode
		return 0;
 
    m_pCourant->m_pBrancheGauche = nouveau;
 
	++m_nbNoeud; // un noeud en plus
	return 1;
}
 
//droite est centre c'est la même chose
[...]

methode de deplacement du pointeur courant

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
int Arbre::bougeBrancheGauche()
{
	if (m_pCourant == NULL || m_pCourant->m_pBrancheGauche == NULL)
		return 0;
 
	m_pCourant = m_pCourant->m_pBrancheGauche;
	return 1;
}
 
int Arbre::bougeRacine()
{
	if (m_nbNoeud == 0)
		return 0;
 
	m_pCourant = m_pRacine;
	return 1;
}

le main

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
    Arbre * arbre = new Arbre();
 
    arbre->ajouterPremierNoeud(1);
    arbre->ajouterGauche(2);
    arbre->ajouterCentre(3);
    arbre->ajouterDroite(4);
 
    arbre->bougeRacine();
    arbre->bougeBrancheGauche();
    arbre->ajouterGauche(5);
    arbre->ajouterCentre(6);
    arbre->ajouterDroite(7);
 
    arbre->bougeRacine();
    arbre->bougeBrancheCentre();
    arbre->ajouterGauche(8);
    arbre->ajouterCentre(9);
    arbre->ajouterDroite(10);
 
    arbre->bougeRacine();
    arbre->bougeBrancheDroite();
    arbre->ajouterGauche(11);
    arbre->ajouterCentre(12);
    arbre->ajouterDroite(13);

**ternel** · 22/09/2014, 14h25

Un itérateur est juste un type qui permet deux choses: accéder à la valeur courante, et déplacer la notion de "courante" à la valeur suivante.

Ces opérations sont habituellement les opérateurs * et ++.
On peut aussi donner ->

Dans ton cas, il suffit d'avoir une classe contenant une référence sur l'arbre, et le pointeur courant, et un moyen de représenter la fin du travail.
Un tel itérateur s'obtient alors de trois manières: begin(), end() et avec certaines fonctions de recherche.

Ca n'est pas du tout difficile à coder, et surtout ca rendra ta classe d'arbre plus simple à coder, car elle pourra s'appuyer dessus.

D'ailleurs, dans la STL de gcc, la map et le set sont tous deux des rb_tree, c'est à dire des "arbres rouge et noir", qui sont codés uniquement par leurs itérateurs. (Du moins, dans mon souvenir)

Essaie de coder autour de l'interface suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class ArbreIterator {
public:
    int operator*() const;
 
    ArbreIterator & left() {
        //...
        return *this;
    }
 
    ArbreIterator & right() {
        //...
        return *this;
    }
 
    ArbreIterator & center() {
        //...
        return *this;
    }
 
    ArbreIterator & up() {
        //...
        return *this;
    }
};

Il suffira alors de fournir une fonction racine() dans l'arbre, et le tour sera joué.