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

Question

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

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

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

Answer 1

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

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 2

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

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

• Дети
• Предки
• 1010 * Наследники *
• 1012 * Siblings *
• Уровень узла
• Родитель
• Root
• 1020 * Etc. *

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

Answer 4

Вот дерево

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 5

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

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

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

Answer 6

Я добавил полное решение и пример, используя класс 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 7

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

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

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

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

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

Answer 8

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

Answer 9

Вот моя реализация 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 10

Если вам нужна реализация структуры данных с корневым деревом, которая использует меньше памяти, вы можете написать свой класс 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
}