[recursivité] : parcours de structure arborescente

Version imprimable

28/06/2017, 10h44
aharel

1 pièce(s) jointe(s)

[recursivité] : parcours de structure arborescente

Bonjour,

Je suis en pleine galère sur le codage d'une méthode récursive qui doit calculer des valeurs sur une structure de données arborescente.
En gros j'ai une structure arborescente qui ressemble à ça :

Root
|- 00
|- 41
| |- 139
| |- 10 kg
| |- 20 kg
|
|- 140
|- 5 kg
|- 7 kg
|- 12 kg
Seuls les noeuds feuille contiennent une donnée de poids.
La méthode que je veux coder consiste à mettre à jour toute l'arborescence afin de mettre à jour la donnée Poids.

On devrait avoir :

Root (60 kg)
|- 00 (60 kg)
|- 41 (60 kg)Pièce jointe 289726
| |- 139 (36 kg)
| |- 10 kg
| |- 20 kg
|
|- 140 (24 kg)
|- 5 kg
|- 7 kg
|- 12 kg

Ci-joint mon appli de test.
28/06/2017, 15h25
Noxen

En vrac, dans le code de ton projet :
- le pluriel de child n'est pas childs mais children ;
- la propriété Childs est accessible en écriture, ce qui permet de contourner AddChild() => met le set en private ;
- la propriété Childs est une liste, ce qui permet d'ajouter une élément en contournant AddChild() => expose-la sous la forme d'un IEnumerable<T>, éventuellement en renvoyant une copie au lieu de la liste elle-même afin d'empêcher un cast (facile avec LinQ : return _children.ToArray();).

Pour répondre plus spécifiquement à ta question tu devrais avoir une classe pour tes nœuds et une autre pour tes feuilles ; ces deux classes peuvent éventuellement avoir une interface ou une classe parent en commun. Un nœud a une liste de nœuds et une liste de feuilles. La valeur des feuilles est portée par leur propriété poids, tandis que les nœuds calculeront leur poids à partir de leurs enfants. Ces différents éléments doivent informer leurs parents lorsque leur poids change, et doivent en informer l'extérieur => regarde du côté de l'interface INotifyPropertyChanged.

Salut,
un exemple de calcul récursif ascendant sur modification de la propriété poids.
Je n'ai qu'une seule classe Node qui peut avoir des enfants. Chaque noeud est définit par son propre poids et la somme des poids de ses enfants.

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
137
138
139
140
141
142
143
144
145
 
public static class Program
    {
        static void Main(string[] args)
        {
 
            var root = new Node("root");
            root.WeightChanged += root_WeightChanged;
 
            root.AddChild(new Node("c1", 10));
            root.AddChild(new Node("c2", 10));
            root.AddChild(new Node("c3", 10));
 
            root[2].m_Weight_kg += 3;
            root[2].AddChild(new Node("c3c1", 5));
            root[2].m_Weight_kg -= 3;
            root[2].RemoveChild(0);
 
            Console.ReadKey();
        }
 
        static void root_WeightChanged(Node obj)
        {
            //display
        }
    }
 
 
 
    public class Node
    {
        public readonly string m_Name;
 
        private double _Weight_kg = 0;
        public double m_Weight_kg
        {
            get
            {
                return this._Weight_kg;
            }
            set
            {
                this._Weight_kg = value;
                this.CalcWeight();
            }
        }
 
        private double _TotalWeight_kg;
        public double m_TotalWeight_kg
        {
            get
            {
                return this._TotalWeight_kg;
            }
            private set
            {
                this._TotalWeight_kg = value;
                this.OnWeightChanged();
            }
        }
 
        private double m_OldTotalWeight_kg = 0;
 
        private Node m_Parent = null;
 
        private List<Node> _Children = new List<Node>();
        public Node this[int pIndex]
        {
            get
            {
                return this.m_Children[pIndex];
            }
        }
 
        public event Action<Node> WeightChanged;
        private void OnWeightChanged()
        {
            if (this.WeightChanged != null)
            {
                this.WeightChanged(this);
            }
        }
 
 
        public Node(string pName)
        {
            this.m_Name = pName;
            this.m_Weight_kg = 0;
            this.WeightChanged += Node_WeightChanged;
        }
 
        public Node(string pName, double pWeight_kg)
        {
            this.m_Name = pName;
            this.m_Weight_kg = pWeight_kg;
            this.WeightChanged += Node_WeightChanged;
        }
 
 
        private void Node_WeightChanged(Node obj)
        {
            Debug.Write(string.Format("{0} changed {1} to {2}\n", obj.m_Name, obj.m_OldTotalWeight_kg, obj.m_TotalWeight_kg));
            this.m_OldTotalWeight_kg = this.m_TotalWeight_kg;
        }
 
        public void AddChild(Node pNode)
        {
            pNode.m_Parent = this;
            pNode.WeightChanged += pNode_Changed;
            this._Children.Add(pNode);
            this.CalcWeight();
        }
 
        private void pNode_Changed(Node obj)
        {
            this.CalcWeight();
        }
 
        public void RemoveChild(Node pNode)
        {
            pNode.m_Parent = null;
            pNode.WeightChanged += pNode_Changed;
            this._Children.Remove(pNode);
            this.CalcWeight();
        }
 
        public void RemoveChild(int pIndex)
        {
            var node = this._Children.ElementAt(pIndex);
            this.RemoveChild(node);
        }
 
        private void CalcWeight()
        {
            this.m_TotalWeight_kg = this._Weight_kg + this.m_Children.Sum(child => child.m_TotalWeight_kg);
        }
 
        public ReadOnlyCollection<Node> m_Children
        {
            get
            {
                return this._Children.AsReadOnly();
            }
        }
    }