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

Question

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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 ??

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");
    }
}

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

• итератор
• идет поиск
• Ява/С#

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

Answer 6

В целом отличный Библиотека общих коллекций C5 имеет несколько различных древовидных структур данных, включая наборы, пакеты и словари.Исходный код доступен, если вы хотите изучить детали их реализации.(Я использовал коллекции 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

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

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

Обратите внимание: это отличается от неуниверсальной реализации: вам не нужно приводить «узел» в «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
}

Answer 11

Я создаю Класс узла это может быть полезно для других людей.Класс имеет такие свойства, как:

• Дети
• Предки
• Потомки
• Братья и сестры
• Уровень узла
• Родитель
• Корень
• И т. д.

Существует также возможность преобразовать плоский список элементов с идентификатором и ParentId в дерево.Узлы содержат ссылки как на дочерние, так и на родительские узлы, что делает итерацию узлов довольно быстрой.

Answer 12

Поскольку об этом не упоминается, я бы хотел, чтобы вы обратили внимание на теперь выпущенную кодовую базу .net:в частности код для SortedSet который реализует красно-черное дерево:

https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/generic/sortedset.cs

Однако это сбалансированная древовидная структура.Поэтому мой ответ — это скорее ссылка на то, что я считаю единственной собственной древовидной структурой в основной библиотеке .net.

Answer 13

Я завершил код, которым поделился @Berezh.

  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;
        }

        public IEnumerator<TreeNode<T>> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return (IEnumerator)GetEnumerator();
        }
    }
    public class TreeNodeEnum<T> : IEnumerator<TreeNode<T>>
    {

        int position = -1;
        public List<TreeNode<T>> Nodes { get; set; }

        public TreeNode<T> Current
        {
            get
            {
                try
                {
                    return Nodes[position];
                }
                catch (IndexOutOfRangeException)
                {
                    throw new InvalidOperationException();
                }
            }
        }


        object IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }


        public TreeNodeEnum(List<TreeNode<T>> nodes)
        {
            Nodes = nodes;
        }

        public void Dispose()
        {
        }

        public bool MoveNext()
        {
            position++;
            return (position < Nodes.Count);
        }

        public void Reset()
        {
            position = -1;
        }
    }

Answer 14

Вот дерево

public class Tree<T> : List<Tree<T>>
{
    public  T Data { get; private set; }

    public Tree(T data)
    {
        this.Data = data;
    }

    public Tree<T> Add(T data)
    {
        var node = new Tree<T>(data);
        this.Add(node);
        return node;
    }
}

Вы даже можете использовать инициализаторы:

    var tree = new Tree<string>("root")
    {
        new Tree<string>("sample")
        {
            "console1"
        }
    };

Answer 15

Вот мой собственный:

class Program
{
    static void Main(string[] args)
    {
        var tree = new Tree<string>()
            .Begin("Fastfood")
                .Begin("Pizza")
                    .Add("Margherita")
                    .Add("Marinara")
                .End()
                .Begin("Burger")
                    .Add("Cheese burger")
                    .Add("Chili burger")
                    .Add("Rice burger")
                .End()
            .End();

        tree.Nodes.ForEach(p => PrintNode(p, 0));
        Console.ReadKey();
    }

    static void PrintNode<T>(TreeNode<T> node, int level)
    {
        Console.WriteLine("{0}{1}", new string(' ', level * 3), node.Value);
        level++;
        node.Children.ForEach(p => PrintNode(p, level));
    }
}

public class Tree<T>
{
    private Stack<TreeNode<T>> m_Stack = new Stack<TreeNode<T>>();

    public List<TreeNode<T>> Nodes { get; } = new List<TreeNode<T>>();

    public Tree<T> Begin(T val)
    {
        if (m_Stack.Count == 0)
        {
            var node = new TreeNode<T>(val, null);
            Nodes.Add(node);
            m_Stack.Push(node);
        }
        else
        {
            var node = m_Stack.Peek().Add(val);
            m_Stack.Push(node);
        }

        return this;
    }

    public Tree<T> Add(T val)
    {
        m_Stack.Peek().Add(val);
        return this;
    }

    public Tree<T> End()
    {
        m_Stack.Pop();
        return this;
    }
}

public class TreeNode<T>
{
    public T Value { get; }
    public TreeNode<T> Parent { get; }
    public List<TreeNode<T>> Children { get; }

    public TreeNode(T val, TreeNode<T> parent)
    {
        Value = val;
        Parent = parent;
        Children = new List<TreeNode<T>>();
    }

    public TreeNode<T> Add(T val)
    {
        var node = new TreeNode<T>(val, this);
        Children.Add(node);
        return node;
    }
}

Выход:

Fastfood
   Pizza
      Margherita
      Marinara
   Burger
      Cheese burger
      Chili burger
      Rice burger

Answer 16

Большинство деревьев формируются на основе данных, которые вы обрабатываете.

Скажем, у вас есть person класс, который включает в себя детали кого-то parents, не могли бы вы иметь структуру дерева как часть вашего «класса домена» или использовать отдельный класс дерева, который содержал ссылки на объекты вашего человека?Подумайте о простой операции, например, получение всех grandchildren из person, должен ли этот код находиться в personкласс, или должен ли пользователь person Класс должен знать о отдельном классе дерева?

Другой пример — дерево разбора в компиляторе…

Оба эти примера показывают, что понятие дерева является частью домен данных и использование отдельного дерева общего назначения как минимум удваивает количество создаваемых объектов, а также снова усложняет программирование API.

Нам нужен способ повторно использовать стандартные операции с деревьями без необходимости повторной реализации их для всех деревьев и в то же время без необходимости использовать стандартный класс дерева.Boost пытался решить проблему такого типа для C++, но я еще не увидел какого-либо эффекта для адаптации .NET.

Answer 17

Я добавил полное решение и пример с использованием класса NTree выше, а также добавил метод «AddChild»...

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

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

        public void AddChild(T data)
        {
            var node = new NTree<T>(data) { Parent = this };
            children.AddFirst(node);
        }

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

        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, string t, ref NTree<T> r)
        {
            visitor(node.data, node, t, ref r);
            foreach (NTree<T> kid in node.children)
                Traverse(kid, visitor, t, ref r);
        }
    }
    public static void DelegateMethod(KeyValuePair<string, string> data, NTree<KeyValuePair<string, string>> node, string t, ref NTree<KeyValuePair<string, string>> r)
    {
        string a = string.Empty;
        if (node.data.Key == t)
        {
            r = node;
            return;
        }
    }

с использованием

 NTree<KeyValuePair<string, string>> ret = null;
 tree.Traverse(tree, DelegateMethod, node["categoryId"].InnerText, ref ret);

Answer 18

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

Answer 19

Вот моя реализация BST

class BST
{
    public class Node
    {
        public Node Left { get; set; }
        public object Data { get; set; }
        public Node Right { get; set; }

        public Node()
        {
            Data = null;
        }

        public Node(int Data)
        {
            this.Data = (object)Data;
        }

        public void Insert(int Data)
        {
            if (this.Data == null)
            {
                this.Data = (object)Data;
                return;
            }
            if (Data > (int)this.Data)
            {
                if (this.Right == null)
                {
                    this.Right = new Node(Data);
                }
                else
                {
                    this.Right.Insert(Data);
                }
            }
            if (Data <= (int)this.Data)
            {
                if (this.Left == null)
                {
                    this.Left = new Node(Data);
                }
                else
                {
                    this.Left.Insert(Data);
                }
            }
        }

        public void TraverseInOrder()
        {
            if(this.Left != null)
                this.Left.TraverseInOrder();
            Console.Write("{0} ", this.Data);
            if (this.Right != null)
                this.Right.TraverseInOrder();
        }
    }

    public Node Root { get; set; }
    public BST()
    {
        Root = new Node();
    }
}

Answer 20

Если вам нужна реализация структуры данных с корневым деревом, которая использует меньше памяти, вы можете написать свой класс Node следующим образом (реализация C++):

class Node {
       Node* parent;
       int item; // depending on your needs

       Node* firstChild; //pointer to left most child of node
       Node* nextSibling; //pointer to the sibling to the right
}