Parcours d'arbre binaire iteratif et postfixe

Version imprimable

21/09/2008, 19h29
coyotte507

Parcours d'arbre binaire iteratif et postfixe

Bonjour,

j'ai fait quelques recherches sur internet, mais je n'ai pas réussi à trouver ce que je voulais.

En itératif, j'ai vu les solutions pour un parcours "en profondeur" et "en largeur", mais pas de postfixe.

Chaque noeud possède un lien vers son père, et ses fils.

Je veux visiter chaque noeud, mais en commençant par les éléments les plus au fond (par exemple si visiter implique détruire le noeud en le désallouant etc, vaut mieux procéder dans cet ordre :mrgreen:)

C'est en itératif, donc pas de piles!

Je voudrais avoir le code de référence, s'il existe, permettant de faire ça... J'ai déjà un code dont je ne suis pas sûr qu'il soit optimisé.

Merci :!:
22/09/2008, 09h17
JeitEmgie

Citation:

Envoyé par coyotte507

Bonjour,

j'ai fait quelques recherches sur internet, mais je n'ai pas réussi à trouver ce que je voulais.

En itératif, j'ai vu les solutions pour un parcours "en profondeur" et "en largeur", mais pas de postfixe.

Chaque noeud possède un lien vers son père, et ses fils.

Je veux visiter chaque noeud, mais en commençant par les éléments les plus au fond (par exemple si visiter implique détruire le noeud en le désallouant etc, vaut mieux procéder dans cet ordre :mrgreen:)

C'est en itératif, donc pas de piles!

Je voudrais avoir le code de référence, s'il existe, permettant de faire ça... J'ai déjà un code dont je ne suis pas sûr qu'il soit optimisé.

Merci :!:

énoncé ambigu…
donnez un exemple…

une sortie en postfix peut-être simplement un parcours en profondeur dans lequel le père est sorti après ses enfants…

mais "visiter par les nœuds les plus profonds" veut vouloir dire aussi en parcours en strate indépendement du père… qui nécessitera sans doute une structure de données intermédiaire…

(a (b (c d) e (f g (i) h))) doit sortir :

c d b f i g h e a
h i g f d c e b a
i c d f g h b e a
i h g f d c e b a
...

?
22/09/2008, 16h35
coyotte507

Merci de ton aide,

C'est juste un parcours en postfixe itératif dont j'ai besoin, peu importe l'ordre dans lesquels les nœuds sont visités (mais bien sûr chaque noeud sera visité avant son père).

De plus on doit utiliser un espace constant, et ne pas modifier, même temporairement, les nœuds en question.

---------1-----------
-------2----3--------
-----4--5--6--7-----

peut afficher 4-5-3-6-7-3-1 par exemple, je reconnais que c'était un peu ambigu, en fait je n'ai pas besoin forcément d'afficher 7 avant 2 par exemple.

Le problème c'est que sur internet je ne trouve pas de parcours itératif en postfixe, alors que ça doit être tellement classique qu'un code reconnu comme "optimal" pour ce problème et ces contraintes existe forcément.

Citation:

Envoyé par coyotte507

Merci de ton aide,

C'est juste un parcours en postfixe itératif dont j'ai besoin, peu importe l'ordre dans lesquels les nœuds sont visités (mais bien sûr chaque noeud sera visité avant son père).

De plus on doit utiliser un espace constant, et ne pas modifier, même temporairement, les nœuds en question.

---------1-----------
-------2----3--------
-----4--5--6--7-----

peut afficher 4-5-3-6-7-3-1 par exemple, je reconnais que c'était un peu ambigu, en fait je n'ai pas besoin forcément d'afficher 7 avant 2 par exemple.

Le problème c'est que sur internet je ne trouve pas de parcours itératif en postfixe, alors que ça doit être tellement classique qu'un code reconnu comme "optimal" pour ce problème et ces contraintes existe forcément.

sans stack ou récursion, le parcours d'un arbre ne peut se faire qu'en stockant les informations d'état du parcours dans les nœuds eux-mêmes…

mais si en plus on ne peut pas le faire…

sinon en pseudo-code :
Code:

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 type Node { Node owner ; Array<Node> children ; /* 0 .. N-1 */ int curChildIdx ; /* c'est ici qu'on garde l'état du parcours de l'arbre */ } /* en assumant qu'un nœud sans fils a une array children de taille 0 (càd children n'est jamais null) */ cur_node = root_node ; cur_node.curChildIdx = -1 ; while (cur_node != null) { cur_node.curChildIdx += 1 ; if (cur_node.curChildIdx >= cur_node.children.size) { OUTPUT( cur_node ) ; cur_node = cur_node.owner ; } else { cur_node = cur_node.children[ cur_node.curChildIdx ] ; cur_node.curChildIdx = -1 ; } }

Pourtant...

Code:

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
 
using namespace std;
 
struct Noeud {
    Noeud *pere;
    Noeud *aine;
    Noeud *cadet;
    int cle;
 
    Noeud(int i, Noeud *pere) {
        cle = i;
        this->pere = pere;
        aine = cadet = NULL;
    }
};
 
void del(Noeud *n)
{
    delete n;
}
 
class ArbreBinaire
{
    public:
        Noeud *ancetre;
 
        ArbreBinaire()
        {
            ancetre = NULL;
        }
 
        ~ArbreBinaire()
        {
            map(&del);
            ancetre = NULL;
        }
 
        void map(void (*fonction)(Noeud *))
        {
            if (!ancetre) {
                return;
            }
            Noeud *ptr = ancetre;
            Noeud *lastptr = NULL;
            while (1)
            {
                //Descend le plus bas possible, en partant à gauche, ou à droite si à gauche c'est impossible
                while (1)
                {
                    if (ptr->aine != NULL && ptr->aine != lastptr)
                    {
                        ptr = ptr->aine;
                    } else if (ptr->cadet != NULL)
                    {
                        ptr = ptr->cadet;
                    } else {
                        break;
                    }
                }
 
                Noeud *pere = ptr->pere;
                lastptr = ptr;
                fonction(ptr);
                ptr = pere;
 
 
                //On remonte jusqu'à un père où on n'a pas visité la branche droite
                while (ptr != NULL && (ptr->cadet == lastptr || ptr->cadet == NULL))
                {
                    pere = ptr->pere;
                    lastptr = ptr;
                    fonction(ptr);
                    ptr = pere;
                }
 
                //On est remonté trop loin: on a tout visité
                if (ptr == NULL) {
                    break;
                }
            }
        }
 
        void Inserer(int i)
        {
            if (ancetre == NULL)
            {
                ancetre = new Noeud(i, NULL);
                return;
            }
 
            Noeud *ptr = ancetre;
            while (1)
            {
                if (ptr->cle > i) {
                    if (ptr->aine != NULL) {
                        ptr = ptr->aine;
                    } else {
                        ptr->aine = new Noeud(i, ptr);
                        break;
                    }
                } else
                {
                    if (ptr->cadet != NULL) {
                        ptr = ptr->cadet;
                    } else {
                        ptr->cadet = new Noeud(i, ptr);
                        break;
                    }
                }
            }
        }
};
 
void affiche(Noeud *n)
{
    cout << n->cle << " ";
}
 
int main()
{
    ArbreBinaire a;
 
    a.Inserer(20);
    a.Inserer(10);
    a.Inserer(30);
    a.Inserer(5);
    a.Inserer(15);
    a.Inserer(25);
    a.Inserer(35);
 
    a.map(&affiche);
    cout << endl;
 
    return 0;
}

La fonction ArbreBinaire::map sert à faire un parcours postfixe en iteratif pour appliquer une fonction à chaque noeud.

Je l'utilise dans le destructeur pour détruire chaque noeud, mais seulement après ses fils.

Je voulais savoir s'il existe un algo optimisé, mais apparemment non...

Merci quand même du temps passé!

22/09/2008, 18h54
JeitEmgie

Citation:

Envoyé par coyotte507

Pourtant...

le truc du lastptr ne marche bien que pour les arbres binaires…

mais pour un n-aire il faut rechercher à chaque remontée à quel index correspond le lastptr dont on remonte…
(le lastChldIndex ne sert en fait qu'à mettre en cache cette info…)

mais si vous devez être strictement "read-only", de fait cela reste une solution…
22/09/2008, 19h12
coyotte507

Citation:

Envoyé par JeitEmgie

le truc du lastptr ne marche bien que pour les arbres binaires…

mais pour un n-aire il faut rechercher à chaque remontée à quel index correspond le lastptr dont on remonte…
(le lastChldIndex ne sert en fait qu'à mettre en cache cette info…)

mais si vous devez être strictement "read-only", de fait cela reste une solution…

Pas sûr...

Je pense que pour un arbre n-aire, quand on remonte, si par exemple on remonte au père via la 3ème branche, on redescend par la quatrième :question:

C'est encore plus simple pour des arbres n-aires avec où chaque noeud possède un pointeur vers son père, son fils gauche et son frère droit, on peut directement passer au suivant ainsi.