Arbre general (general tree)

**dahtah** · 29/08/2011, 09h07

Bonjour a tous,

Je suis debutant et en C, et en arbre. J'ai besoin de modeliser des donnees sous formes d'arbre general (general tree), c'est a dire que chaque noeud peut avoir potentiellement une infinite d'enfant. J'ai donc cree un arbre donc chaque noeud est une liste chainee (la liste de ses enfants).
Je rencontre pas mal de problemes:
1. J'arrive a parcourir l'arbre de maniere recursive vers le bas, mais je suis incapable de le remonter.
2. Le fait que je ne puisse pas remonter (point 1.) fait que je ne peux pas desallouer la memoire elegament (je desalloue le noeud pere avant le noeud enfant)
3. Je trouve que globallement ma conception n'est vraiment pas super (je pense qu'il faudrait introduire un pointeur sur le noeud de droite (sibling) pour simplifier l'implementation).
4. J'ai lu qu'un arbre general peut etre modelise sous forme d'arbre binaire. Je pense que cela doit etre une solution beacoup plus simple que d'avoir des listes chainees a chaque noeud. Un point que je ne comprends pas par contre est que l'arbre binaire va etre tres desequilibre vers la droite?

Voici le code que j'ai ecrit:

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
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
 
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include "gtree.h"
#include "llist.h"
 
static int nodeId = 0;
 
Root_t *newGT(void)
{
  Root_t *root = malloc(sizeof(Root_t));
  return root;
}
 
Node_t *addChildNode(Root_t *btRoot, Node_t *pNode, void *data)
{
  /*If tree is unitialised, or Node is null, return error*/
  if (btRoot == NULL)
    return NULL;
  /*Initialise memory for our Node as well as for our llist of children*/
  Node_t *nNode = calloc(1, sizeof(Node_t));
  if (nNode == NULL)
    return NULL;
  Head_t *pHead = newLList();
    if (pHead == NULL)
      return NULL;
  /*We are the first child*/
  if (btRoot->root == NULL)
  {
    /*Initialise the root of the tree to our first node*/
    btRoot->root = nNode;
    /*We are the first node so no children and no parent*/
    nNode->parent = NULL;
    /*Give ourselves an id*/
    nNode->id = nodeId++;
    /*Assign our empty child list*/
    nNode->child = pHead;
    nNode->data = data;
  /*Children already exist*/
  } else {
    if (pNode == NULL)
      return NULL;
    /*Set our parent node to the parameter one*/
    nNode->parent = pNode;
    nNode->id = nodeId++;
    /*We have no children yet*/
    nNode->child = pHead;
    nNode->data = data;
    /*Act on our parent node, and add ourselves to it's linked list of children*/
    addCell(pNode->child, (void *)nNode);
    printf("insert: %s\n, under: %s\n", (char *)nNode->data, (char *)nNode->parent->data );
  }
  return nNode;
}
 
int _intCmp(const int a, const Node_t *node)
{
  if (a == node->id)
    return 0;
  return -1;
}
 
void _traverseBranch(Node_t *pNode, actionFunc_t *action)
{
  action(pNode);
  /*If we have children, follow them*/
  if (pNode->child->first != NULL)
  {
    /*In this part we treat only nodes with children*/
    _traverseBranch((Node_t *)pNode->child->first->data, action);
  /*No children? Follow our right member*/
  } else {
    if (pNode->parent != NULL)
    {
      /*Dirty trick to fin ourself in the parent child list*/
      Cell_t *us = searchData(pNode->parent->child, (void *)pNode->id, (cmpFunc_t *)_intCmp);
      /*If we have a right sibling, follow it*/
      if (us->next != NULL)
        /*In this part we treat only first nodes with no children*/
        _traverseBranch((Node_t *)us->next->data, action);
      else
      {
        /*If we have no more siblings, we need to go to our parent*/
        Node_t *pParentNode = pNode->parent;
        /*We need to find the next node of our parent*/
        if (pParentNode->parent != NULL)
        {
          /*In this part we treat only last nodes with no children*/
          /*Yuck, but search the linked list to find our parents id*/
          Cell_t *pNextParentNode = searchData(pParentNode->parent->child, (void *)pParentNode->id, (cmpFunc_t *)_intCmp);
          if (pNextParentNode->next != NULL)
            _traverseBranch((Node_t *)pNextParentNode->next->data, action);
          /*Here we can't go up to our next parent since it doesn't exist and neither
           to our parent since we have already visited it*/
          else
            return;
        }
      }
    }
  }
}
 
void traverseTree(Root_t *pGtRoot, actionFunc_t* action)
{
  Head_t *children = pGtRoot->root->child;
  Cell_t *pCell = NULL, *pNextCell = NULL;
  /*Iterate over all first level nodes, and go down for each branch because my
   * recursive design sucks*/
  for (pCell = children->first; pCell != NULL; pCell = pNextCell)
  {
    _traverseBranch((Node_t *)pCell->data, action);
    pNextCell = pCell->next;
  }
}

et le code appelant:

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
25
26
27
28
29
30
31
void print(Node_t *pNode)
{
  printf("Node %i: %s\n", pNode->id, (char *)pNode->data);
}
 
/*
 * 
 */
int main(int argc, char** argv) {
  Root_t *btRoot = newGT();
  char *data = "Head";
  addChildNode(btRoot, NULL, (void *)data);
  Node_t *a = addChildNode(btRoot, btRoot->root, (void *)"Node A");
  Node_t *b = addChildNode(btRoot, btRoot->root, (void *)"Node B");
  Node_t *c = addChildNode(btRoot, btRoot->root, (void *)"Node C");
  Node_t *d = addChildNode(btRoot, b, (void *)"Child B-a");
  Node_t *e = addChildNode(btRoot, b, (void *)"Child B-b");
  Node_t *f = addChildNode(btRoot, b, (void *)"Child B-c");
  Node_t *g = addChildNode(btRoot, f, (void *)"Child B-c-1");
  Node_t *h = addChildNode(btRoot, f, (void *)"Child B-c-2");
  Node_t *i = addChildNode(btRoot, a, (void *)"Child A-a");
  Node_t *j = addChildNode(btRoot, a, (void *)"Child A-b");
  Node_t *k = addChildNode(btRoot, a, (void *)"Child A-c");
  Node_t *l = addChildNode(btRoot, a, (void *)"Child A-d");
  Node_t *m = addChildNode(btRoot, l, (void *)"Child A-d-1");
  Node_t *n = addChildNode(btRoot, j, (void *)"Child A-b-1");
  Node_t *o = addChildNode(btRoot, i, (void *)"Child A-a-1");
  Node_t *p = addChildNode(btRoot, i, (void *)"Child A-a-2");
  traverseTree(btRoot, (actionFunc_t *)print);
  return (EXIT_SUCCESS);
}

Bien sur, je compte generer le contenu dynamiquement. Ce n'est qu'un exemple ici.

Je joins aussi mes headers pour les courageux:

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
25
26
27
 
#ifndef BTREE_H
#define	BTREE_H
 
#include "llist.h"
 
struct Node_s {
  int id;
  void *data;
  struct Node_s *parent;
  Head_t *child;
//  struct Node_s *sibling;
};
typedef struct Node_s Node_t;
 
struct Root_s {
  struct Node_s *root;
};
typedef struct Root_s Root_t;
 
typedef void actionFunc_t(Node_t *pNode);
 
Root_t *newGT(void);
Node_t *addChildNode(Root_t *btRoot, Node_t *pNode, void *data);
void traverseTree(Root_t *pGtRoot, actionFunc_t *action);
 
#endif	/* BTREE_H */

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
25
 
#ifndef LLIST_H
#define	LLIST_H
 
#include "cmpFunc.h"
 
struct Cell_s {
  void *data;
  struct Cell_s *next;
};
typedef struct Cell_s Cell_t;
 
/*This will hold both the first and last cell of the linked list*/
struct Head_s {
  struct Cell_s *first;
  struct Cell_s *last;
};
typedef struct Head_s Head_t;
 
Head_t *newLList(void);
int addCell(Head_t *head, void *data);
Cell_t *searchData(Head_t *pHead, void *pData, cmpFunc_t *cmp);
void freeLlist(Head_t *pHead);
 
#endif	/* LLIST_H */

Code :

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

1
2
3
4
5
6
7
 
#ifndef CMPFUNC_H
#define	CMPFUNC_H
 
typedef int cmpFunc_t(const void *pData1, const void *pData2);
 
#endif	/* CMPFUNC_H */

Pour ceux qui ont lu jusqu'au bout, je cherche des examples d'arbres generaux en C, ou des bouquins interessants sur le sujet a la limite.
J'aimerai aussi avoir votre avis sur comment ameliorer ce code, de facon a ce que je puisse remonter l'arbre.

Merci.

**matafan** · 29/08/2011, 13h04

Je n'ai pas lu ton code en détail donc je vais répondre de manière générale :

- Le problème ce n'est pas de désallouer élégamment, c'est de désallouer correctement. Libérer le père et ensuite s'en servir pour accéder aux fils ce n'est pas juste un manque d'élégance, c'est simplement incorrect.

- Pour régler ton problème de libération, le plus simple est d'utiliser une fonction récursive. Tu libère le noeud après être remonté des noeuds fils.

- Plutôt qu'avoir une liste chainée de fils dans un noeud, il est généralement plus facile d'avoir un pointeur vers le fils ainé, et un pointeur vers le frère cadet.

**Sve@r** · 30/08/2011, 08h49

Envoyé par dahtah

Bonjour a tous,

Je suis debutant et en C, et en arbre. J'ai besoin de modeliser des donnees sous formes d'arbre general (general tree), c'est a dire que chaque noeud peut avoir potentiellement une infinite d'enfant. J'ai donc cree un arbre donc chaque noeud est une liste chainee (la liste de ses enfants).

Bonjour

Il y a plein de façons de modéliser des arbres. Tu en as choisi une qui, plus difficile à implémenter que les autres (mélange d'arbre et de liste chainée) correspond selon toi à ton problème donc ok.

Envoyé par dahtah

Je rencontre pas mal de problemes:
1. J'arrive a parcourir l'arbre de maniere recursive vers le bas, mais je suis incapable de le remonter.

La fonction récursive qui descend n'a pas besoin de le remonter. Une fois qu'elle arrive au bout, elle se termine. L'instance appelante de la fonction (celle qui est un niveau au dessus) reprend alors la main. On peut dire qu'à ce moment là, tu te trouves au dessus du dernier noeud donc que tu es remontée.
Maintenant si tu as besoin, en partant d'un noeud en bas de l'arbre, de remonter vers la racine alors il faut que ton noeud connaisse l'adresse de son père...

Envoyé par dahtah

2. Le fait que je ne puisse pas remonter (point 1.) fait que je ne peux pas desallouer la memoire elegament (je desalloue le noeud pere avant le noeud enfant)

Voir réponse de matafan. Ta fonction récursive doit
1) appeler la fonction enfant si possible
2) libérer le noeud courant
Le fait que l'enfant soit appelée avant la libération fera que les fils seront libérés avant les pères

Envoyé par dahtah

3. Je trouve que globallement ma conception n'est vraiment pas super (je pense qu'il faudrait introduire un pointeur sur le noeud de droite (sibling) pour simplifier l'implementation).

Ca c'est toi qui gère

Envoyé par dahtah

4. J'ai lu qu'un arbre general peut etre modelise sous forme d'arbre binaire. Je pense que cela doit etre une solution beacoup plus simple que d'avoir des listes chainees a chaque noeud. Un point que je ne comprends pas par contre est que l'arbre binaire va etre tres desequilibre vers la droite?

Un arbre binaire correspond à un problème précis (souvent un tri d'éléments) mais ne correspondra pas à ton problème où tu as dit que ton père pouvait avoir un nombre infini de fils (sous-entendu "de fils de premier niveau") car un arbre binaire n'a que 2 fils et 2 fils ne correspondent pas au prédicat "nombre infini de fils"...

Envoyé par dahtah

Pour ceux qui ont lu jusqu'au bout, je cherche des examples d'arbres generaux en C, ou des bouquins interessants sur le sujet a la limite.
J'aimerai aussi avoir votre avis sur comment ameliorer ce code, de facon a ce que je puisse remonter l'arbre.

Merci.

Si j'ai le temps, j'essaierai de taper un exemple aujourd'hui...

**dahtah** · 31/08/2011, 01h18

Merci de vos reponses respectives.

Envoyé par matafan

- Plutôt qu'avoir une liste chainée de fils dans un noeud, il est généralement plus facile d'avoir un pointeur vers le fils ainé, et un pointeur vers le frère cadet.

C'est bien ce dont je me suis rendu compte. C'est le point 3 que j'evoquais.

Envoyé par Sve@r

Il y a plein de façons de modéliser des arbres. Tu en as choisi une qui, plus difficile à implémenter que les autres (mélange d'arbre et de liste chainée) correspond selon toi à ton problème donc ok.

Oui, mais je pense modifier afin de retirer la liste chainee et d'introduire a la place pour chaque noeud un pointeur vers son frere de droite.

Envoyé par Sve@r

La fonction récursive qui descend n'a pas besoin de le remonter. Une fois qu'elle arrive au bout, elle se termine. L'instance appelante de la fonction (celle qui est un niveau au dessus) reprend alors la main. On peut dire qu'à ce moment là, tu te trouves au dessus du dernier noeud donc que tu es remontée.

C'est ce que j'ai fait dans le code poste pour eviter de remonter, mais cela me pose des problemes lors de la liberation de la memoire.

Envoyé par Sve@r

Maintenant si tu as besoin, en partant d'un noeud en bas de l'arbre, de remonter vers la racine alors il faut que ton noeud connaisse l'adresse de son père...

Oui, mais je dois connaitre le niveau de recursion egalement non? Car si je suis l'arbre jusqu'en bas, je suis au dernier enfant, et que je remonte a son parent, je dois etre capable de savoir si je descend, ou si je vais au frere de droite? Comment se fait la decision pour le dernier noeud parent de soit descendre, soit remonter, pour eviter la boucle infinie?
En fait dites moi si je me trompe, mais dans le cas de liberation memoire, il faut que les noeuds parents soient visite apres les noeuds enfants (post-order en quelque sorte), alors que pour les autres traitements cela tiens de l'algo.

Envoyé par Sve@r

Voir réponse de matafan. Ta fonction récursive doit
1) appeler la fonction enfant si possible
2) libérer le noeud courant
Le fait que l'enfant soit appelée avant la libération fera que les fils seront libérés avant les pères

Oui, c'est mon probleme atuel.

Envoyé par Sve@r

Un arbre binaire correspond à un problème précis (souvent un tri d'éléments) mais ne correspondra pas à ton problème où tu as dit que ton père pouvait avoir un nombre infini de fils (sous-entendu "de fils de premier niveau") car un arbre binaire n'a que 2 fils et 2 fils ne correspondent pas au prédicat "nombre infini de fils"...

J'ai lu ca sur wikipedia: Encoding_general_trees_as_binary_trees. Visiblement, les noeuds de premier niveau peuvent etre modeliser comme une suite d'enfant de droite d'un arbre binaire.

Envoyé par Sve@r

Si j'ai le temps, j'essaierai de taper un exemple aujourd'hui...

Merci. Je vais essayer de modifier mon arbre et de poster une version plus propre.
Peut etre poster une entree FAQ sur developpez serait pas mal, car a ma connaissance il y a peu d'exemple en C d'arbre generaux sur le net. La plupart des exemples concernent les arbres binaires.

**dahtah** · 31/08/2011, 09h12

Bon, j'ai eu quelques heures tranquilles au taf (et oui, ca arrive parfois), donc j'ai pu faire quelque chose de propre (sur du taf perso, j'avoue).
Pour ceux que ca interesse, j'ai vire les listes chainees d'enfants, et les ai remplacees par un pointeur sur le prochain frere. Ca rend les choses plus faciles et lisibles.
Pour gerer le choix du chemin lorsque j'arrive au dernier enfant et que je dois remonter, je tiens a jour le sens dans lequel je parcours l'arbre (haut/bas). En fonction de la direction, je vais soit vers l'enfant (bas), soit vers le pere (haut). Je sais pas si c'est la methode habituelle, mais ca marche.
Du coup, je peux visiter l'arbre en une fois, et agir sur les noeuds avant ou apres avoir visiter les enfants.
Bref, pour ceux qui veulent, voici le header:

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
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
 
/* 
 * File:   gtree.h
 *
 * Created on August 31, 2011, 8:31 AM
 */
 
#ifndef GTREE_H
#define	GTREE_H
 
/*Enum to hold our traversal tree methods
    pre: visit nodes before visiting children
    post: visit nodes after visiting children */
enum ORDER {
  pre,
  post
};
typedef enum ORDER ORDER_t;
 
/*Structure to hold put node information.
    id: A unique identifier for the node
    pNodeData: A pointer to the data help by the node. Void type to give data
               type control to the caller
    pParent: A pointer to the parent of the current node. Up.
    pSibling: A pointer to the next right node of our brother. Right.
    pFirstChild: A pounter to our first child. Down.*/
struct gtNode {
  unsigned int id;
  void *pNodeData;
  struct gtNode *pParent;
  struct gtNode *pSibling;
  struct gtNode *pFirstChild;
};
typedef struct gtNode gtNode_t;
 
/*Structure to hold the information on the root of our structure. This is to abstract
 the head of th tree.
    pRoot: A pointer to the first element of our tree. The first entry.*/
struct gtRoot {
  gtNode_t *pRoot;
};
typedef struct gtRoot gtRoot_t;
 
/*This callback function will be called on each visited node*/
typedef void nodeActionFunc_t(gtNode_t *pNode);
 
/*Create a new general tree.
    returns: a pointer to the root of the tree*/
gtRoot_t *newGT(void);
/*Traverse the hole tree, visiting each node.
    pGtRoot: A pointer to the root of the tree
    traversal: The traversal method to use.Defined in the ORDER enum. Can be pre 
               or post
    nodeAction: A Callabck function to be executed on each node
    returns: an error code. -1 on error, 0 on success*/
int traverseTree(gtRoot_t *pGtRoot, ORDER_t traversal, nodeActionFunc_t *nodeAction);
/*Add a child node to a specified node.
    pGtRoot: A pointer to the root of the tree
    pParentNode: A pointer to the parent of the node you wish to add
    pNodeData: A pointer to the data to be held by the node
    returns: the added node*/
gtNode_t *addChildNode(gtRoot_t *pGtRoot, gtNode_t *pParentNode, void *pNodeData);
/*Free the memory occupied by the tree
    pGtRoot: A pointer to the root of the tree.*/
void freeGt(gtRoot_t *pGtRoot);
 
#endif	/* GTREE2_H */

et voici l'implementation:

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
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
137
138
139
140
141
142
143
144
 
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include "gtree.h"
 
static unsigned int nodeId = 0;
 
/*Enum to track if we are going up or down the tree*/
enum DIRECTION {
  up,
  down
};
typedef enum DIRECTION DIRECTION_t;
DIRECTION_t path = down;
 
gtRoot_t *newGT(void)
{
  return calloc(1, sizeof(gtRoot_t));
}
 
void freeGt(gtRoot_t *pRoot)
{
  traverseTree(pRoot, post, (nodeActionFunc_t *)free);
  free(pRoot);
}
 
/*Private function to find the last node in a level. I think this can be simplified
 Will look into this later*/
gtNode_t *_findLastNode(gtNode_t *pFirstChild)
{
  if (pFirstChild == NULL)
    return NULL;
  gtNode_t *pNode = NULL, *pNextNode = NULL, *pLastNode = NULL;
  for (pNode = pFirstChild; pNode != NULL; pNode = pNextNode)
  {
    if (pNode != NULL)
      pLastNode = pNode;
    pNextNode = pNode->pSibling;
  }
  return pLastNode;
}
 
gtNode_t *addChildNode(gtRoot_t *pBtRoot, gtNode_t *pParentNode, void *pNodeData)
{
  gtNode_t *pNewNode = NULL;
  /*If the root structure is unitialised, exit with error*/
  if (pBtRoot == NULL)
    return NULL;
  /*If we fail to allocate memory for our new structure, exit with error*/
  if ((pNewNode = calloc(1, sizeof(gtNode_t))) == NULL)
    return NULL;
  /*If we are the first child of the tree, initialise everything to NULL*/
  if (pBtRoot->pRoot == NULL)
  {
    /*Register the new node to the root of the tree*/
    pBtRoot->pRoot = pNewNode;
    pNewNode->id = nodeId++;
    pNewNode->pParent = NULL;
    pNewNode->pSibling = NULL;
    pNewNode->pFirstChild = NULL;
    pNewNode->pNodeData = pNodeData;
  /*Tree already contains at least one element, so we need to add ourselves in*/
  } else {
    pNewNode->id = nodeId++;
    pNewNode->pParent = pParentNode;
    pNewNode->pSibling = NULL;
    pNewNode->pFirstChild = NULL;
    pNewNode->pNodeData = pNodeData;
    /*If our parent has no children nodes, it means the first one is us*/
    if (pParentNode->pFirstChild == NULL)
      pParentNode->pFirstChild = pNewNode;
    /*If our parent has already has childrens, we need to add ourself at the end
     of the list. We are the last sibling*/
    else
      _findLastNode(pParentNode->pFirstChild)->pSibling = pNewNode;
  }
  return pNewNode;
}
 
/*Just a wrapper of the traverseTree function to enable us to use the root of the
 tree as an entry point*/
int traverseTree(gtRoot_t *pGtRoot, ORDER_t traversal, nodeActionFunc_t *nodeAction)
{
  return traverseBranch(pGtRoot->pRoot, traversal, nodeAction);
}
 
int traverseBranch(gtNode_t *pNode, ORDER_t traversal, nodeActionFunc_t *nodeAction)
{
  if (pNode == NULL)
    return -1;
  /* Depeding on what we are asked to do, either act on the parent node before visiting
   children (pre-order), or act on the parent node after visiting the children
   (post-order) */
  switch (traversal) {
    /*When we are doing pre-order, act on the node on the first visit*/
    case pre:
      if (path == down)
        nodeAction(pNode);
      break;
    /*When we are doing post-order, act on the node on last visit, and print all
     nodes with no children*/
    case post:
      if ((path == up) || (pNode->pFirstChild == NULL))
        nodeAction(pNode);
      break;
    /*We should never get there, so exit on error*/
    default:
      return -1;
  }
  if (pNode->pFirstChild != NULL)
  {
    /*If we are going down the tree, we just visit the next child*/
    if (path == down)
    {
      traverseBranch(pNode->pFirstChild, traversal, nodeAction);
    /*If we are going up, we have 2 cases. If we have a sibling to our right,
     visit it, and possilby his children (so set the path to down). If we have no
     more siblings to our right, we must go up to our parent (so set path to up)*/
    } else {
      if (pNode->pSibling != NULL)
      {
        path = down;
        traverseBranch(pNode->pSibling, traversal, nodeAction);
      } else {
        path = up;
        traverseBranch(pNode->pParent, traversal, nodeAction);
      }
    }
  /*We have no children under our node*/
  } else {
    /*Let's follow our right sibling if we have one*/
    if (pNode->pSibling != NULL)
    {
      traverseBranch(pNode->pSibling, traversal, nodeAction);
    /*If we don't have a right sibling, then we must go up to ur parent (so set
      path to up) */
    } else {
      path = up;
      traverseBranch(pNode->pParent, traversal, nodeAction);
    }
  }
  return 0;
}

Et un example degueu d'utilisation:

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "gtree.h"
 
void print(gtNode_t *pNode)
{
  printf("Node %i: %s\n", pNode->id, (char *)pNode->pNodeData);
}
 
/*
 * 
 */
int main(int argc, char** argv) {
  gtRoot_t *btRoot = newGT();
  char *data = "Head";
  addChildNode(btRoot, NULL, (void *)data);
  gtNode_t *a = addChildNode(btRoot, btRoot->pRoot, (void *)"Node A");
  gtNode_t *b = addChildNode(btRoot, btRoot->pRoot, (void *)"Node B");
  gtNode_t *c = addChildNode(btRoot, btRoot->pRoot, (void *)"Node C");
  gtNode_t *d = addChildNode(btRoot, b, (void *)"Child B-a");
  gtNode_t *e = addChildNode(btRoot, b, (void *)"Child B-b");
  gtNode_t *f = addChildNode(btRoot, b, (void *)"Child B-c");
  gtNode_t *g = addChildNode(btRoot, f, (void *)"Child B-c-1");
  gtNode_t *h = addChildNode(btRoot, f, (void *)"Child B-c-2");
  gtNode_t *i = addChildNode(btRoot, a, (void *)"Child A-a");
  gtNode_t *j = addChildNode(btRoot, a, (void *)"Child A-b");
  gtNode_t *k = addChildNode(btRoot, a, (void *)"Child A-c");
  gtNode_t *l = addChildNode(btRoot, a, (void *)"Child A-d");
  gtNode_t *m = addChildNode(btRoot, l, (void *)"Child A-d-1");
  gtNode_t *n = addChildNode(btRoot, j, (void *)"Child A-b-1");
  gtNode_t *o = addChildNode(btRoot, i, (void *)"Child A-a-1");
  gtNode_t *p = addChildNode(btRoot, i, (void *)"Child A-a-2");
  gtNode_t *q = addChildNode(btRoot, c, (void *)"Just to check");
  traverseTree(btRoot, pre, (nodeActionFunc_t *)print);
  freeGt(btRoot);
  //traverseTree(btRoot, (actionFunc_t *)print);
  return (EXIT_SUCCESS);
}

Je suis tout de meme interesse si quelqu'un a une implementation d'un arbre general a poster. J'aimerai bien voir comment certain choix sont faits.

Merci a matafan et Sve@r de l'aide fournie.

Arbre general (general tree)

C

Discussions similaires

Partager

Partager