Structure de données arborescente en C#

Question

Je cherchais une structure de données d'arbre ou de graphe en C#, mais je suppose qu'il n'y en a pas fournie. Un Examen Approfondi des Structures de Données Utilisant C# 2.0 en parle un peu. Y a-t-il une bibliothèque pratique couramment utilisée pour fournir cette fonctionnalité? Peut-être à travers un pattern stratégique pour résoudre les problèmes présentés dans l'article.

Je me sens un peu bête en implémentant mon propre arbre, tout comme je le ferais en implémentant ma propre ArrayList.

Je veux juste un arbre générique qui peut être déséquilibré. Pensez à un arbre de répertoires. C5 a l'air sympa, mais leurs structures d'arbre semblent être implémentées comme des arbres rouges-noirs équilibrés mieux adaptés à la recherche qu'à la représentation d'une hiérarchie de nœuds.

Answer 1

Je déteste l'admettre mais j'ai fini par écrire ma propre classe arborescente en utilisant une liste chaînée. Sur une note sans rapport, je viens de découvrir cette chose ronde qui, lorsqu'elle est attachée à une chose que j'appelle un 'essieu', permet un transport plus facile des marchandises.

Answer 2

Mon meilleur conseil serait qu'il n'y a pas de structure de données d'arbre standard car il existe tellement de façons de l'implémenter qu'il serait impossible de couvrir toutes les bases avec une seule solution. Plus une solution est spécifique, moins elle est susceptible de s'appliquer à un problème donné. Je suis même agacé par les LinkedList - que se passe-t-il si je veux une liste chaînée circulaire ?

La structure de base que vous devrez mettre en œuvre sera une collection de nœuds, et voici quelques options pour vous aider à démarrer. Supposons que la classe Node est la classe de base de l'ensemble de la solution.

Si vous devez seulement naviguer dans l'arbre, alors une classe Node a besoin d'une liste d'enfants.

Si vous devez naviguer dans l'arbre, alors la classe Node a besoin d'un lien vers son nœud parent.

Construisez une méthode AddChild qui prend en charge tous les détails de ces deux points et toute autre logique métier qui doit être implémentée (limites d'enfants, tri des enfants, etc.)

Answer 3

delegate void TreeVisitor(T nodeData);

class NTree
{
    private T data;
    private LinkedList> children;

    public NTree(T data)
    {
         this.data = data;
        children = new LinkedList>();
    }

    public void AddChild(T data)
    {
        children.AddFirst(new NTree(data));
    }

    public NTree GetChild(int i)
    {
        foreach (NTree n in children)
            if (--i == 0)
                return n;
        return null;
    }

    public void Traverse(NTree node, TreeVisitor visitor)
    {
        visitor(node.data);
        foreach (NTree kid in node.children)
            Traverse(kid, visitor);
    }
}

Implémentation récursive simple... < 40 lignes de code... Vous devez simplement conserver une référence à la racine de l'arbre à l'extérieur de la classe, ou l'encapsuler dans une autre classe, peut-être la renommer en TreeNode ??

Answer 4

Voici le mien, qui est très similaire à celui d'Aaron Gage, juste un peu plus conventionnel, à mon avis. Pour mes besoins, je n'ai rencontré aucun problème de performance avec List. Il serait assez facile de passer à un LinkedList si nécessaire.

---

namespace Overby.Collections
{
    public class TreeNode
    {
        private readonly T _value;
        private readonly List> _children = new List>();

        public TreeNode(T value)
        {
            _value = value;
        }

        public TreeNode this[int i]
        {
            get { return _children[i]; }
        }

        public TreeNode Parent { get; private set; }

        public T Value { get { return _value; } }

        public ReadOnlyCollection> Children
        {
            get { return _children.AsReadOnly(); }
        }

        public TreeNode AddChild(T value)
        {
            var node = new TreeNode(value) {Parent = this};
            _children.Add(node);
            return node;
        }

        public TreeNode[] AddChildren(params T[] values)
        {
            return values.Select(AddChild).ToArray();
        }

        public bool RemoveChild(TreeNode node)
        {
            return _children.Remove(node);
        }

        public void Traverse(Action action)
        {
            action(Value);
            foreach (var child in _children)
                child.Traverse(action);
        }

        public IEnumerable Flatten()
        {
            return new[] {Value}.Concat(_children.SelectMany(x => x.Flatten()));
        }
    }
}

Answer 5

La généralement excellente C5 Generic Collection Library dispose de plusieurs structures de données basées sur des arbres différentes, y compris des ensembles, des sacs et des dictionnaires. Le code source est disponible si vous souhaitez étudier les détails de leur implémentation. (J'ai utilisé les collections C5 dans du code de production avec de bons résultats, bien que je n'ai pas spécifiquement utilisé l'une des structures d'arbre.)