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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
| public class Demo {
public static void main(String[] args) {
new Demo();
}
public Demo() {
// jeu de test
List<Integer> actions1 = new ArrayList<>();
actions1.add(5);
actions1.add(4);
List<Integer> actions2 = new ArrayList<>();
actions2.add(7);
actions2.add(4);
actions2.add(5);
// création de l'arbre
TreeNode tree = buildTree("X", actions1, "Y", actions2);
// Pseudo trace de l'arbre à la va-vite
traceTree(tree);
}
private void traceTree(TreeNode racine) {
int n=0;
List<String> level = new ArrayList<>();
do {
level.clear();
traceTreeLevel(racine, n, level);
if ( !level.isEmpty() ) {
for(int i=0; i<level.size(); i++) {
System.out.print('\\');
for(int j=0; j<=level.get(i).length(); j++) {
System.out.print(' ');
}
}
System.out.println();
System.out.println(level);
}
n++;
}
while( !level.isEmpty() );
}
private void traceTreeLevel(TreeNode parent, int n, List<String> level) {
if( n==0 ) {
level.add(parent.toString());
}
else {
for(int i=0; i<parent.getChildCount(); i++) {
TreeNode node = parent.getChildAt(i);
traceTreeLevel(node, n-1, level);
}
}
}
/**
* Construit un arbre
*
* @param acteur1
* @param actions1
* @param acteur2
* @param actions2
* @return
*/
public TreeNode buildTree(String acteur1, List<Integer> actions1, String acteur2, List<Integer> actions2) {
// à la racine, pas d'acteur et pas d'actions pour y aller
return buildTree(null, null, acteur1, actions1, acteur2, actions2);
}
/**
*
* @param parent noeud parent
* @param actions actions pour aller au nouveau noeud
* @param acteur1
* @param actions1
* @param acteur2
* @param actions2
* @return
*/
private TreeNode buildTree(DefaultMutableTreeNode parent, List<Integer> actions, String acteur1, List<Integer> actions1, String acteur2, List<Integer> actions2) {
if ( actions1.isEmpty() && actions2.isEmpty() ) {
return null; // ? que faire dans ce cas ?
}
DefaultMutableTreeNode nodeActeur1 = createNode(acteur1, actions); // on créé le noeud de l'acteur 1
if ( parent!=null ) {
parent.add(nodeActeur1);
}
buildTree(nodeActeur1, acteur1, actions1, acteur2, actions2);
return nodeActeur1;
}
// création des sous-noeuds d'un noeud parent
private void buildTree(DefaultMutableTreeNode parent, String acteur1, List<Integer> actions1, String acteur2, List<Integer> actions2) {
// actions choisies par chacun des acteurs, au fur et à mesure
List<Integer> choixActions = new ArrayList<Integer>();
for(Integer action1 : actions1) {
choixActions.add(action1);
// on créé les sous-noeuds
// on créé les listes d'actions disponibles sans les choix faits pour cette itération
List<Integer> newActions1 = newActionList(actions1, choixActions);
List<Integer> newActions2 = newActionList(actions2, choixActions);
if ( newActions1.isEmpty() && newActions2.isEmpty() ) {
// on créé une feuille si les 2 listes d'actions sont vides
parent.add(createNode("feuille", actions1));
}
else {
// récursion : création node niveau inférieur
buildTree(parent, choixActions, acteur2, newActions2, acteur1, newActions1);
}
}
}
// création d'un noeud à partir d'une chaîne de caractères qui représente l'acteur, suivi de la liste des actions sélectionnées pour la branche arrivant sur ce noeud
private DefaultMutableTreeNode createNode(String acteur1,
List<Integer> actions) {
StringBuilder sb=new StringBuilder();
sb.append('(');
sb.append(acteur1);
if ( actions!=null ) {
sb.append("-[");
boolean first=true; // pour gérer les virgules de séparation
for(Integer action : actions) {
if ( first ) {
first=false;
}
else {
sb.append(", ");
}
sb.append(action);
}
sb.append("]");
}
sb.append(")");
DefaultMutableTreeNode node = new DefaultMutableTreeNode(sb.toString());
return node;
}
/**
* Créé une nouvelle liste contenant tous les éléments qui sont dans actions, sauf ceux qui sont dans l'autre liste
*/
private List<Integer> newActionList(List<Integer> actions,
List<Integer> actionsToDelete) {
List<Integer> newActions = new ArrayList<>(actions);
newActions.removeAll(actionsToDelete);
return newActions;
}
} |
Construire un arbre
Répondre avec citation
Envoyé par dinobogan
La plupart des réponses à vos questions sont déjà dans les 
) :
Partager