les arbres en C

Version imprimable

17/05/2014, 18h06
Salaah

les arbres en C
bonjour a tous ,
j'ais 2 question :
1 - comment afficher une arbres avec sa structure en langage C :
```
                                    a
                                  /   \
                                 b     c
                               /  \   /  \
                              d    e f    g
```
???
2 - comment remplie une tableau a deux dimmention avec tous les combinaison possibles ex: (a,b,c)

a b c

a c b

b a c

b c a

c a b

c b a

s'il vous plaît

1) Cela dépend si c'est un arbre binaire de recherche:
Mais regardes sur cette page Structures arborescentes

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Algorithme procédure parc_prof
Paramètres locaux
   arbrebinaire b
Début
   si B=arbre-vide alors
      /* Traitement de fin */
   sinon
      /* Traitement préfixe */
      parc_prof(g(b))
      /* Traitement infixe */
      parc_prof(d(b))
      /* Traitement suffixe */
   fin si
Fin algorithme procédure parc_prof

À la vue de ta première question je pense que celui qui t'a posé la deuxième question attend ce qu'on appelle une forêt :mrgreen:
C'est à dire plusieurs arbres, mais pas des arbres binaires de recherche.

Je donne un code qui répond quand même à ta question 2 ... mais en C++ avec la collection std::vector :mouarf:
Mais ne t'attends pas à un code optimisé :mrgreen:

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
#include<cstdlib>
 
#include<iostream>
#include<vector>
 
 
// Forward Declarations
void generate_all_combinations(std::vector<char>&, unsigned short&);
void generate_all_combinations(std::vector<char>&, std::vector<char>&, unsigned short&, unsigned short&);
void print(std::vector<char>&, std::vector<char>&, unsigned short&, unsigned short&);
 
 
void generate_all_combinations(std::vector<char>& list, unsigned short& nb_combinations) {
    std::vector<char> current_list;
    unsigned short size = list.size();
    nb_combinations = 0;
 
    generate_all_combinations(list, current_list, size, nb_combinations);
}
 
 
void generate_all_combinations(std::vector<char>& list, std::vector<char>& current_list, unsigned short& size, unsigned short& nb_combinations) {
    void (*func_action) (std::vector<char>&, std::vector<char>&, unsigned short&, unsigned short&) = NULL;
 
    if (size > 1) {
        func_action = (void (*) (std::vector<char>&, std::vector<char>&, unsigned short&, unsigned short&)) &generate_all_combinations;
    } else /* if (size == 1)*/ {
        func_action = &print;
    }
 
    char c = '\0';
 
//  for (unsigned short pos = 0; pos < size; pos++) {
//      c = list[pos];
//      list.erase(list.begin() + pos);
//      current_list.push_back(c);
//      size--;
//      func_action(list, current_list, size, nb_combinations);
////    Add at the same place
//      list.insert(list.begin() + pos, c);
//      current_list.pop_back();
//      size++;
//  }
 
    for(std::vector<char>::iterator it = list.begin(); it != list.end(); ++it) {
        c = (*it);
        list.erase(it);
        current_list.push_back(c);
        size--;
        func_action(list, current_list, size, nb_combinations);
//      Add at the same place
        list.insert(it, c);
        current_list.pop_back();
        size++;
    }
}
 
 
void print(std::vector<char>&, std::vector<char>& list, unsigned short&, unsigned short& nb_combinations) {
    std::vector<char>::iterator it = list.begin();
 
    if (it != list.end()) {
        std::cout << (*it);
 
        for(it++; it != list.end(); ++it) {
            std::cout << ", " << (*it);
        }
 
        std::cout << std::endl;
 
//      Update nb_combinations
        nb_combinations++;
    }
}
 
 
int main() {
    std::vector<char> list;
    list.push_back('a');
    list.push_back('b');
    list.push_back('c');
    list.push_back('d');
 
    unsigned short nb_combinations = 0;
    generate_all_combinations(list, nb_combinations);
 
    std::cout << "Number of combinations: " << nb_combinations << std::endl;
 
    return EXIT_SUCCESS;
}

Il y a bien plus simple pour trouver toutes les combinaisons : il suffit de permuter 2 éléments à chaque fois.

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
void next(int * tab, int size, int *step) {
	int a = (*step)++ % size;
	int b = (a+1) % size;
	int tmp = tab[a];
	tab[a] = tab[b];
	tab[b] = tmp;
}
 
void print(int * tab, int size) {
	for(int i=0; i<size; ++i) {
		char c = tab[i] + 'a';
		printf("%c", c);
	}
	printf("\n");
}
 
const int size = 3;
int tab[] = {0, 1, 2};
int nb = 1, n = size, step = 0;
for(int i=0; i<size; ++i) {
	nb *= n--;
}
for(int i=0; i<nb; ++i) {
	next(tab, size, &step);
	print(tab, size);
}

Pour dessiner le graphe, un parcours en largeur devrait le faire.

23/05/2014, 12h40
Salaah

remerciement

merci beaucoup a tous .
je vai les essai :) :D
merci