Discussion :

[GLDavid]

Bonjour

En C#, j'ai implémenté un n-ary tree. L'idée derrière est d'utiliser cette structure pour un inventaire.
Voici sa représentation:

Code C# :

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
using System;
using System.Collections.Generic;
 
namespace db.Collections
{
    [Serializable]
    public abstract class ATree<ANode>
    {
        protected ATree()
        {
            Nodes = new List<ANode>();
        }
        protected ATree(ANode root):this(){
            Root = root;
        }
        public ANode Root{get;protected set;}
        public ICollection<ANode>Nodes{get;}
    }
}

Un noeud est définit tel que:

Code C# :

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
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace db.Collections
{
    [Serializable]
    public abstract class ANode
    {
        protected ANode() => Children = new LinkedList<ANode>();
        protected ANode(object id) : this() => Id = id;
        public object Id{get;set;}
        public ICollection<ANode>Children{get; protected set;}
        public ANode Parent{get; protected set;}
        public void AddChild(ANode node) 
        {
            Children.Add(node);
            node.Parent = this;
        }
        public abstract ANode FindNode(object toFind, ANode node);
        public abstract bool IsSameId(object id);
        /// <summary>
        /// Find all parents of current ANode.
        /// </summary>
        /// <return>IEnumerable<ANode> as all list of parents from origin to current ANode</return>
        public IEnumerable<ANode>GetNodePath(){
            ICollection<ANode>parents = new List<ANode>();
            ANode current = this;
            while(current.Parent!=null){
                parents.Add(current.Parent);
                current = current.Parent;
            }
            return parents.Reverse();
        }
    }
}

Mon problème est que je ne suis pas satisfait de ma méthode de recherche d'un noeud:

Code C# :

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
using System;
using System.Linq;
using System.Threading.Tasks;
 
namespace db.Collections
{
    [Serializable]
    public class Node : ANode
    {
        public Node(object id):base(id){}
 
        public override ANode FindNode(object toFind, ANode node)
        {
            if(node!=null)
                return node;
            if(IsSameId(toFind))
                return this;
            return !Children.Any() ? null : Children.Select(child => child.FindNode(toFind, null)).FirstOrDefault(found => found != null);
        }
 
        public override bool IsSameId(object id)
        {
            return Id!=null&&id!=null && string.Compare(Id.ToString(), id.ToString(), StringComparison.Ordinal) == 0;
        }
    }
}

Je ne vois pas quelle(s) optimisation(s) je pourrais apporter. A moins que vous ayez d'autres idées?
Merci d'avance,

@++

[tbc92]

Je vais peut-être dire de grosses bétises, mais ce n'est pas grave.
Dans mon esprit, un tree , c'est un arbre, et quand on alimente un arbre, dans la version de base,on se débrouille pour que chaque branche se décompose en 2 sous-branches , la droite et la gauche. Et on sait parfaitement ce qu'on met dans la sous-branche de droite et dans la sous-branche de gauche. Si par malchance, la moitié des branches sont vides, tant pis.

Si par principe, chaque parent a un seul enfant ... ce n'est plus un arbre, mais ça ressemble plutôt à une chaîne.
Et même dans ce cas, si on a des maillons les uns derrière les autres, si l'ordre des maillons a un sens, on doit pouvoir utiliser ça pour aller vite ; par contre (c'est ta configuration ?) si l'ordre des maillons est aléatoire, on ne peut que lire séquentiellement tous les maillons pour trouver le maillon cherché.