Itérer sur tous les éléments d'un arbre

***alexandre*** · 05/12/2007, 12h35

Hello,

J ai un petit soucie d algorithme pour parcourir chaque élément d un arbre.

Chaque element d un arbre possède une liste d'enfants.

Je pensais faire :

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
 
	private boolean exist(MdfElementTreeItem item) {
		boolean result = false;
		MdfElementTreeItem root = getRoot(item);
		List children = root.getMdfElementTreeItems();
		for (int i = 0; i < children.size();i++) {
			MdfElementTreeItem element = (MdfElementTreeItem) children.get(i);
			List childrenChild = element.getMdfElementTreeItems();
			for (int j = 0; j < childrenChild.size();j++) {
				MdfElementTreeItem childElement = (MdfElementTreeItem) children.get(j);
				if (element.equals(childElement)) {
					return true;
				}
			}
			exist (element);
		}
		return result;
	}

cela l air correct ?

**Patriarch24** · 05/12/2007, 13h27

Il existe plusieurs algo pour parcourir un arbre (BFS, DFS). Pour savoir si ton code fonctionne, testes-le et poses des questions si tu en as !

**LGnord** · 05/12/2007, 13h55

Tu utilises java 4?

Sinon:

Code :

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

1
2
3
4
 
boolean result = false;
...
return result;

Je ne vois aucune affectation sur result. Tu vas donc toujours retourner false.

Code :

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

1
2
 
exist (element);

Tu n'utilises jamais le résultat de ta recursion.

De là penser qu'il manque:

Code :

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

1
2
 
result = exist (element);

est un pas que je me permets de franchir (sans pour autant garantir la correction de l'algorithme).

***alexandre*** · 05/12/2007, 13h56

hello,

voici mon implémentation

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
 
	/**
         * Does our children list already contain the specified tree item ?
         * 
         * @param item 
         *                      The item to search
         * @param children
         *                      The children list
         * @return boolean The result
         */
	private boolean exist(MdfElementTreeItem item) {
		boolean result = false;
		MdfElementTreeItem root = getRoot(item);
		List children = root.getMdfElementTreeItems();
		return existInChildren (children,item);
	}
 
	/**
         * Gets the root MdfElementTreeItem.
         * 
         * @param item
         *                      The element
         * @return MdfElementTreeItem The root element
         *              
         */
	private MdfElementTreeItem getRoot(MdfElementTreeItem item) {
		MdfElementTreeItem elt = item;
		while (elt.getParent() != null) {
			elt = elt.getParent();
			if (elt instanceof MdfListTreeItem) {
				return elt;
			}
		}
		return elt;
	}
	/**
         * Does our item exist in the children list ?
         * 
         * @param children
         *                      The children list
         * @param item
         *                      The item to search
         * @return boolean True if exist
         */
	private boolean existInChildren(List children, MdfElementTreeItem item) {
		boolean result = false;
		for (int i = 0; i < children.size();i++) {
			MdfElementTreeItem element = (MdfElementTreeItem) children.get(i);
			List childrenChild = element.getMdfElementTreeItems();
			for (int j = 0; j < childrenChild.size();j++) {
				MdfElementTreeItem elementChild = (MdfElementTreeItem) childrenChild.get(j);
				if (elementChild.equals(item)) {
					result =  true;
				}
				return existInChildren(childrenChild,item);	
			}			
		}
		return result;
	}

malheureusement j ai un problème de traitement infini :/

**LGnord** · 05/12/2007, 14h03

Question bète :
l'argument que tu donnes est bien un arbre? Ce n'est pas un graphe?

***alexandre*** · 05/12/2007, 14h13

c est un element d un arbre il a cette tete

edit : en fait je crois que c est un graphe et non un arbre, je le represente graphiquement sous forme d arbre mais si tu veux tu peux avoir

le noeud A qui contient les éléments B C D
le noeud B qui contient une reference sur A

ce qui pose probleme lors de la recherche d un element car il y a des references circulaires a qui contient b qui contient A qui contient B

je ne sais pas comment résoudre ce problème ... si quelqu un a une idée

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
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
174
175
176
177
178
179
 
public abstract class MdfElementTreeItem implements Comparable, IAdaptable {
 
	/** The wrapped MDF element */
	private MdfModelElement mdfElement;
 
	/** The parent MdfElementTreeItem. */
	private MdfElementTreeItem parent;
 
	/** The child MdfElementTreeItems. */
	private List children;
 
	/** A filter to filter child nodes. */
	private MdfElementFilter filter = null;
 
	/** the fully qualified  name of the wrapped MDF element */
	private MdfPath path;
 
	/**
         * @return The mdf model filter of this node
         */
	public final MdfElementFilter getFilter() {
		return this.filter;
	}
 
	/**
         * Sets the mdf model filter of this node
         * @param newFilter the new filter
         */
	public final void setFilter(MdfElementFilter newFilter) {
		this.filter = newFilter;
	}
 
	/**
         * Creates a new MdfElementTreeItem.
         * 
         * @param mdfElement
         *            The MDf element wrapped by this item
         * @param parent
         *            The parent MdfElementTreeItem
         */
	public MdfElementTreeItem(MdfModelElement mdfElement, MdfElementTreeItem parent) {
		super();
		this.mdfElement = mdfElement;
		this.parent = parent;
		this.filter = (parent != null) ? parent.getFilter() : null;
	}
 
	/**
         * Creates a new root MdfElementTreeItem.
         * 
         * @param mdfElement
         *            The MDf element wrapped by this item
         */
	public MdfElementTreeItem(MdfModelElement mdfElement) {
		this(mdfElement, null);
	}
 
	/**
         * Gets the parent WidgetTreeItem.
         * 
         * @return WidgetTreeItem The parent WidgetTreeItem or null if this item is thr root element
         */
	public MdfElementTreeItem getParent() {
		return this.parent;
	}
 
	/**
         * @return the wrapped MDF model element
         */
	public final MdfModelElement getMdfModelElement() {
		return this.mdfElement;
	}
 
	/**
         * This methods realises a simple filter, that return false
         * if the mdf model element represents an abstract definition,
         * otherwise it return true
         * @param mme a mdf model element
         * @return True to indicate the mme is accepted (not abstract)
         */
	protected boolean accept(MdfModelElement mme) {
		if (filter == null) {
			return true;
		}
		return filter.accept(mme);
	}
 
	/**
         * Constructs the list of children mdf model elements<p> 
         * This method shall be implemented by concrete subclasses.
         * @param children the list of children mdf element
         */
	protected abstract void getChildren(List children);
 
 
	/**
         * @return the fully qualified name of this MDF model element
         */
	public final MdfPath getPath() {
		if (this.path == null) {
			ArrayList qNames = new ArrayList();
			MdfElementTreeItem ti = getParent();
			while ( ti != null && ti.getMdfModelElement() != null) {
				MdfName qName = ti.getMdfModelElement().getQualifiedName(); 
				qNames.add(0, qName);
				ti = ti.getParent();
			}
			qNames.add(getMdfModelElement().getQualifiedName());
			this.path =  new MdfPath(qNames);
		} return this.path;
	}
 
	/**
         * 
         * @param element
         * @return
         */
	private String makeKey(MdfModelElement element) {
		StringBuffer key = new StringBuffer(64);
    	key.append(element.getClass().getName());
 
    	if (element instanceof MdfProperty) {
    		MdfProperty prop = (MdfProperty)element;
    		key.append(! prop.isRequired());
    		key.append(prop.getMultiplicity() > 0);
    	}
    	key.append(element.getName());
 
		return  key.toString();
	}
 
	/**
         * Compares to MDF element name
         */
	public int compareTo(Object other) {
		String keyLeft = makeKey(getMdfModelElement());
		String keyRight = makeKey(((MdfElementTreeItem)other).getMdfModelElement());
		return keyLeft.compareTo(keyRight);
	}	
 
	/**
         * Gets the child MdfElementTreeItems. These wrap the contents of the MDF Element. 
         * 
         * @return List of MdfElementTreeItems
         */
	public final List getMdfElementTreeItems() {
		if (children == null) {
			children = new ArrayList();
			getChildren(children);
		}
		return children;
	}
 
	/* (non-Javadoc)
	 * @see org.eclipse.core.runtime.IAdaptable#getAdapter(java.lang.Class)
	 */
	public Object getAdapter(Class adapter) {
		if (adapter.equals(MdfModelElement.class)) {
			return getMdfModelElement();
		} else if (adapter.equals(MdfPath.class)) {
			return getPath();
		}
		return null;
	}
 
	/**
         * Invalidate the MdfElementTreeItem. This forces the children to be recreated.
         */
	public void invalidate() {
		children = null;
	}
 
	public boolean canDragAndDrop() {
		return true;
	}
 
 
}