Древовидная структура данных в C #

Question

Я искал древовидную или графическую структуру данных в C #, но, по-моему, ее нет. Обширный анализ структур данных с использованием C # 2.0 объясняет немного, почему. Есть ли удобная библиотека, которая обычно используется для обеспечения этой функциональности? Возможно, через шаблон стратегии для решения вопросов, представленных в статье.

Я чувствую себя немного глупо, реализуя свое собственное дерево, так же, как я реализую свой собственный ArrayList.

Я просто хочу общее дерево, которое может быть несбалансированным. Подумайте о дереве каталогов. C5 выглядит изящно, но их древовидные структуры кажутся реализованными в виде сбалансированных красно-черных деревьев, которые лучше подходят для поиска, чем для представления иерархии узлов.

Answer 1

Я не хочу это признавать, но в итоге я написал свой собственный класс дерева, используя связанный список. На несвязанной ноте я только что обнаружил эту круглую вещь, которая, будучи прикрепленной к вещи, которую я называю «осью», облегчает транспортировку товаров.

Answer 2

Мой лучший совет: не существует стандартной древовидной структуры данных, потому что есть так много способов ее реализовать, что невозможно охватить все базы одним решением. Чем конкретнее решение, тем менее вероятно, что оно применимо к любой конкретной проблеме. Меня даже раздражает LinkedList - что, если я хочу круглый список ссылок?

Базовая структура, которую вам нужно реализовать, будет набором узлов, и вот несколько вариантов, с которых можно начать. Предположим, что класс Node является базовым классом всего решения.

Если вам нужно перемещаться только по дереву, то классу Node необходим список дочерних элементов.

Если вам нужно перемещаться вверх по дереву, то классу Node нужна ссылка на его родительский узел.

Создайте метод AddChild, который позаботится обо всех мелочах этих двух точек и любой другой бизнес-логике, которая должна быть реализована (дочерние ограничения, сортировка дочерних элементов и т.

Answer 3

delegate void TreeVisitor<T>(T nodeData);

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

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

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

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

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

Простая рекурсивная реализация ... <40 строк кода ... Вам просто нужно сохранить ссылку на корень дерева вне класса, или обернуть его в другой класс, возможно переименовать в TreeNode ?? </p>

Answer 4

Вот мой, который очень похож на Аарона Гейджа , на мой взгляд, немного более обычный. В моих целях у меня не было проблем с производительностью List<T>. При необходимости было бы достаточно просто переключиться на LinkedList.

---

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

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

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

        public TreeNode<T> Parent { get; private set; }

        public T Value { get { return _value; } }

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

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

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

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

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

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

Answer 5

Еще одна древовидная структура:

public class TreeNode<T> : IEnumerable<TreeNode<T>>
{

    public T Data { get; set; }
    public TreeNode<T> Parent { get; set; }
    public ICollection<TreeNode<T>> Children { get; set; }

    public TreeNode(T data)
    {
        this.Data = data;
        this.Children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> AddChild(T child)
    {
        TreeNode<T> childNode = new TreeNode<T>(child) { Parent = this };
        this.Children.Add(childNode);
        return childNode;
    }

    ... // for iterator details see below link
}

Пример использования:

TreeNode<string> root = new TreeNode<string>("root");
{
    TreeNode<string> node0 = root.AddChild("node0");
    TreeNode<string> node1 = root.AddChild("node1");
    TreeNode<string> node2 = root.AddChild("node2");
    {
        TreeNode<string> node20 = node2.AddChild(null);
        TreeNode<string> node21 = node2.AddChild("node21");
        {
            TreeNode<string> node210 = node21.AddChild("node210");
            TreeNode<string> node211 = node21.AddChild("node211");
        }
    }
    TreeNode<string> node3 = root.AddChild("node3");
    {
        TreeNode<string> node30 = node3.AddChild("node30");
    }
}

БОНУС
Смотрите полноценное дерево с:

• итератор
• поиск
• Java / C #

https://github.com/gt4dev/yet-another-tree-structure

Answer 6

В целом превосходная библиотека C5 Generic Collection имеет несколько различных древовидных структур данных, включая наборы, пакеты и словари. Исходный код доступен, если вы хотите изучить детали их реализации. (Я использовал коллекции C5 в рабочем коде с хорошими результатами, хотя я не использовал ни одну из древовидных структур специально.)

Answer 7

См. http://quickgraph.codeplex.com/

QuickGraph предоставляет общие ориентированные / ненаправленные графовые структуры данных и алгоритмы для .Net 2.0 и выше. QuickGraph поставляется с такими алгоритмами, как поиск по глубине, поиск по дыханию, поиск A *, кратчайший путь, k-кратчайший путь, максимальный поток, минимальное связующее дерево, наименьшие общие предки и т. Д. QuickGraph поддерживает MSAGL, GLEE и Graphviz для рендеринг графиков, сериализация в GraphML и т. д.

Answer 8

Если вы хотите написать свой собственный, вы можете начать с этого документа, состоящего из шести частей, подробно описывающего эффективное использование структур данных C # 2.0 и как анализировать реализацию ваших структур данных в C #. В каждой статье есть примеры и установщик с образцами, за которыми вы можете следить.

«Обширный анализ структур данных с использованием C # 2.0» , Скотт Митчелл

Answer 9

У меня есть небольшое расширение для решений.

Используя рекурсивное обобщенное объявление и производный подкласс, вы можете лучше сконцентрироваться на своей фактической цели.

Обратите внимание, это отличается от не универсальной реализации, вам не нужно приводить 'node' в 'NodeWorker'.

Вот мой пример:

public class GenericTree<T> where T : GenericTree<T> // recursive constraint  
{
  // no specific data declaration  

  protected List<T> children;

  public GenericTree()
  {
    this.children = new List<T>();
  }

  public virtual void AddChild(T newChild)
  {
    this.children.Add(newChild);
  }

  public void Traverse(Action<int, T> visitor)
  {
    this.traverse(0, visitor);
  }

  protected virtual void traverse(int depth, Action<int, T> visitor)
  {
    visitor(depth, (T)this);
    foreach (T child in this.children)
      child.traverse(depth + 1, visitor);
  }
}

public class GenericTreeNext : GenericTree<GenericTreeNext> // concrete derivation
{
  public string Name {get; set;} // user-data example

  public GenericTreeNext(string name)
  {
    this.Name = name;
  }
}

static void Main(string[] args)  
{  
  GenericTreeNext tree = new GenericTreeNext("Main-Harry");  
  tree.AddChild(new GenericTreeNext("Main-Sub-Willy"));  
  GenericTreeNext inter = new GenericTreeNext("Main-Inter-Willy");  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Tom"));  
  inter.AddChild(new GenericTreeNext("Inter-Sub-Magda"));  
  tree.AddChild(inter);  
  tree.AddChild(new GenericTreeNext("Main-Sub-Chantal"));  
  tree.Traverse(NodeWorker);  
}  

static void NodeWorker(int depth, GenericTreeNext node)  
{                                // a little one-line string-concatenation (n-times)
  Console.WriteLine("{0}{1}: {2}", String.Join("   ", new string[depth + 1]), depth, node.Name);  
}  

Answer 10

Попробуйте этот простой пример.

public class TreeNode<TValue>
{
    #region Properties
    public TValue Value { get; set; }
    public List<TreeNode<TValue>> Children { get; private set; }
    public bool HasChild { get { return Children.Any(); } }
    #endregion
    #region Constructor
    public TreeNode()
    {
        this.Children = new List<TreeNode<TValue>>();
    }
    public TreeNode(TValue value)
        : this()
    {
        this.Value = value;
    }
    #endregion
    #region Methods
    public void AddChild(TreeNode<TValue> treeNode)
    {
        Children.Add(treeNode);
    }
    public void AddChild(TValue value)
    {
        var treeNode = new TreeNode<TValue>(value);
        AddChild(treeNode);
    }
    #endregion
}