it-swarm-ru.tech

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

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

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

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

228
stimms

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

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

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

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

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

141
David Boike

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

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

112
Aaron Gage

Вот мой, который очень похож на Аарона Гейджа , на мой взгляд, немного более условно. В моих целях я не сталкивался с проблемами производительности с 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()));
        }
    }
}
49
Ronnie Overby

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

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

40
Grzegorz Dev

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

22
McKenzieG1

Смотрите http://quickgraph.codeplex.com/

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

10
nietras

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

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

7
user7116

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

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

Обратите внимание, что это отличается от не универсальной реализации, вам не нужно приводить '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);  
}  
6
Erik Nagel

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

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
}
4
Berezh

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

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

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

2
Alex Siepman

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

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

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

2
Meirion Hughes

Вот дерево

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"
        }
    };
2
Visar

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

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
2
moien

Я выполнил код, которым поделился @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;
        }
    }
2
Ashkan Sirous

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

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

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

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

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

1
Ian Ringrose

Я добавил полное решение и пример с использованием класса 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);
1
Dmitry

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

0
Denise Skidmore