Преобразование таблицы в дерево

Question

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

Интерфейс для класса сущностей ДБ

public interface IDbEntityNode
    {
         int Id { get; set; }
         int ParentId { get; set; }
    }

Пример db Класс сущности

 public class ExceptionCategory :IDbEntityNode
    {
        public  int Id { get; set; }
        public  int ParentId { get; set; }
        public string Data { get; set; }      
        public ExceptionCategory(string data, int id, int parentId)
        {
            Id = id;
            ParentId = parentId;
            Data = data;
        }
    }

Общий класс, который содержит структуру узла дерева

public class GenericNode<T> 
    {
        public T NodeInformation { get; set; }
        public GenericNode<T> Parent { get; set; }
        public List<GenericNode<T>> Children { get; set; } = new List<GenericNode<T>>();
    }

Метод, который покрывает плоский список деревом

public static List<GenericNode<T>> CreateGenericTree<T>(List<T> flatDataObject,Func<T,bool> IsRootNode) where T : IDbEntityNode            
        {
            var lookup = new Dictionary<int, GenericNode<T>>();
            var rootNodes = new List<GenericNode<T>>();
            var noOfElements = flatDataObject.Count;
            for (int element = 0; element < noOfElements; element++)
            {
                GenericNode<T> currentNode;
                if (lookup.TryGetValue(flatDataObject[element].Id, out currentNode))
                {
                    currentNode.NodeInformation = flatDataObject[element];
                }
                else
                {
                    currentNode = new GenericNode<T>() { NodeInformation = flatDataObject[element] };
                    lookup.Add(flatDataObject[element].Id, currentNode);
                }

                if (IsRootNode(flatDataObject[element])) 
                {
                    rootNodes.Add(currentNode);
                }
                else
                {
                    GenericNode<T> parentNode;
                    if (!lookup.TryGetValue(flatDataObject[element].ParentId, out parentNode))
                    {   
                        parentNode = new GenericNode<T>();
                        lookup.Add(flatDataObject[element].ParentId, parentNode);
                    }
                    parentNode.Children.Add(currentNode);
                    currentNode.Parent = parentNode;
                }
            }

            return rootNodes;
        }

Исполнение:

private static void Main(string[] args)
        {
            List<IDbEntityNode> flatDataStructure = new List<IDbEntityNode>
            {
                new ExceptionCategory("System Exception",1,0),
                new ExceptionCategory("Index out of range",2,1),
                new ExceptionCategory("Null Reference",3,1),
                new ExceptionCategory("Invalid Cast",4,1),
                new ExceptionCategory("OOM",5,1),
                new ExceptionCategory("Argument Exception",6,1),
                new ExceptionCategory("Argument Out Of Range",7,6),
                new ExceptionCategory("Argument Null",8,6),
                new ExceptionCategory("External Exception",9,1),
                new ExceptionCategory("Com",10,9),
                new ExceptionCategory("SEH",11,9),
                new ExceptionCategory("Arithmatic Exception",12,1),
                new ExceptionCategory("DivideBy0",13,12),
                new ExceptionCategory("Overflow",14,12),
            };

            var tree = CreateGenericTree(flatDataStructure, IsRootNode);
        }
 private static bool IsRootNode(IDbEntityNode dbEntity)
        {
            bool isRootNode = false;
            if (dbEntity.ParentId == 0 )
                isRootNode = true;
            return isRootNode;              
        }

Answer 1

Попробуйте следующее решение, используя рекурсивный код:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        public static List<IDbEntityNode> flatDataStructure = null;
        public static Dictionary<int?, List<IDbEntityNode>> dict = null;
        static void Main(string[] args)
        {
            flatDataStructure = new List<IDbEntityNode>
            {
                new ExceptionCategory("System Exception",1,0),
                new ExceptionCategory("Index out of range",2,1),
                new ExceptionCategory("Null Reference",3,1),
                new ExceptionCategory("Invalid Cast",4,1),
                new ExceptionCategory("OOM",5,1),
                new ExceptionCategory("Argument Exception",6,1),
                new ExceptionCategory("Argument Out Of Range",7,6),
                new ExceptionCategory("Argument Null",8,6),
                new ExceptionCategory("External Exception",9,1),
                new ExceptionCategory("Com",10,9),
                new ExceptionCategory("SEH",11,9),
                new ExceptionCategory("Arithmatic Exception",12,1),
                new ExceptionCategory("DivideBy0",13,12),
                new ExceptionCategory("Overflow",14,12),
            };

            dict = flatDataStructure.GroupBy(x => x.ParentId, y => y)
                .ToDictionary(x => x.Key, y => y.ToList());

            GenericNode<IDbEntityNode> root = new GenericNode<IDbEntityNode>();
            root.Parent = null;
            int rootId = 0;
            root.NodeInformation.Id = rootId;
            root.NodeInformation.name = "root";
            root.NodeInformation.ParentId = null;
            CreateGenericTree(root);
        }
        public static void CreateGenericTree<T>(GenericNode<T> parent) where T : IDbEntityNode, new()
        {
            if (dict.ContainsKey(parent.NodeInformation.Id))
            {
                List<IDbEntityNode> children = dict[parent.NodeInformation.Id];
                foreach (IDbEntityNode child in children)
                {
                    GenericNode<T> newChild = new GenericNode<T>();
                    if (parent.Children == null) parent.Children = new List<GenericNode<T>>();
                    parent.Children.Add(newChild);
                    newChild.NodeInformation.Id = child.Id;
                    newChild.NodeInformation.ParentId = parent.NodeInformation.Id;
                    newChild.NodeInformation.name = child.name;
                    newChild.Parent = parent;

                    CreateGenericTree(newChild);
                }
            }
        }

    }
    public class GenericNode<T> where T : new()
    {
        public T NodeInformation = new T();
        public GenericNode<T> Parent { get; set; }
        public List<GenericNode<T>> Children { get; set; }
    }
    public class IDbEntityNode
    {
        public int Id { get; set; }
        public int? ParentId { get; set; }
        public string name { get; set; }
    }
    public class ExceptionCategory : IDbEntityNode
    {
        public string Data { get; set; }
        public ExceptionCategory(string data, int id, int parentId)
        {
            Id = id;
            ParentId = parentId;
            Data = data;
        }
    }
}

Answer 2

Созданный общий подход, объекты таблицы должны следовать интерфейсу dbSet, а объекты TreeNode должны следовать ITreeNode. Я использовал binarySerach, чтобы сделать это максимально быстро. Нет необходимости в рекурсии. Логика гарантирует, что вам не нужно иметь элементы в определенном порядке. Я не выдавал ошибку, когда из цикла, когда еще есть неназначенные объекты, это может быть легко добавлено.

    using System.Collections.Generic;

public interface ITreeNode
{
    string ParentId { get; set; }
    string Id { get; set; }
    dbItem item { get; set; }
    List<ITreeNode> Nodes { get; set; }
}

public class TreeNode : ITreeNode
{
    public TreeNode()
    { }

    public string ParentId { get; set; }
    public string Id { get; set; }
    public dbItem item { get; set; }
    public List<ITreeNode> Nodes { get; set; }
}

public class dbItem
{
    public string ParentId { get; set; }
    public string Id { get; set; }
    public string Name { get; set; }
}
class app
{


    static void Main()
    {
        List<dbItem> dbSet = new List<dbItem>();

        dbSet.Add(new dbItem() { Id = "5", ParentId = "1", Name = "Jan" });
        dbSet.Add(new dbItem() { Id = "25", ParentId = "1", Name = "Maria" });
        dbSet.Add(new dbItem() { Id = "1", Name = "John" });
        dbSet.Add(new dbItem() { Id = "8", ParentId = "2", Name = "Cornelis" });
        dbSet.Add(new dbItem() { Id = "2", Name = "Ilse" });
        dbSet.Add(new dbItem() { Id = "3", Name = "Nick" });
        dbSet.Add(new dbItem() { Id = "87", ParentId = "5", Name = "Rianne" });
        dbSet.Add(new dbItem() { Id = "67", ParentId = "3000", Name = "Rianne" });
        dbSet.Add(new dbItem() { Id = "3000", Name = "Max" });

        List<TreeNode> result = BuildTree<TreeNode>(dbSet);

    }

    private class ParentComparer<T> : IComparer<ITreeNode> where T: ITreeNode
    {
        public int Compare(ITreeNode x, ITreeNode y)
        {
            if (x.ParentId == null) return -1; //have the parents first
            return x.ParentId.CompareTo(y.ParentId);
        }
    }
    private class IdComparer<T> : IComparer<ITreeNode> where T : ITreeNode
    {
        public int Compare(ITreeNode x, ITreeNode y)
        {
           return x.Id.CompareTo(y.Id);
        }
    }

    static private List<T> BuildTree<T> (List<dbItem> table) where T: ITreeNode, new()
    {
        //temporary list of tree nodes to build the tree
        List<T> tmpNotAssignedNodes = new List<T>();
        List<T> tmpIdNodes = new List<T>();
        List<T> roots = new List<T>();

        IComparer<T> pc = (IComparer<T>) new ParentComparer<T>();
        IComparer<T> ic = (IComparer<T>) new IdComparer<T>();

        foreach (dbItem item in table)
        {
            T newNode = new T() { Id = item.Id, ParentId = item.ParentId, item = item };
            newNode.Nodes = new List<ITreeNode>();
            T dummySearchNode = new T() { Id = item.ParentId, ParentId = item.ParentId };

            if (string.IsNullOrEmpty(item.ParentId))
                roots.Add(newNode);
            else
            {
                int parentIndex = tmpIdNodes.BinarySearch(dummySearchNode, ic);//Get the parent
                if (parentIndex >=0)
                {
                    T parent = tmpIdNodes[parentIndex];
                    parent.Nodes.Add(newNode);
                }
                else
                {
                    parentIndex = tmpNotAssignedNodes.BinarySearch(dummySearchNode, pc);
                    if (parentIndex < 0) parentIndex = ~parentIndex;
                    tmpNotAssignedNodes.Insert(parentIndex, newNode);
                }
            }

            dummySearchNode.ParentId = newNode.Id;

            //Cleanup Unassigned
            int unAssignedChildIndex = tmpNotAssignedNodes.BinarySearch(dummySearchNode, pc);

            while (unAssignedChildIndex >= 0 && unAssignedChildIndex < tmpNotAssignedNodes.Count)
            {
                if (dummySearchNode.ParentId == tmpNotAssignedNodes[unAssignedChildIndex].ParentId)
                {
                    T child = tmpNotAssignedNodes[unAssignedChildIndex];
                    newNode.Nodes.Add(child);
                    tmpNotAssignedNodes.RemoveAt(unAssignedChildIndex);
                }
                else unAssignedChildIndex--;
            }
            int index = tmpIdNodes.BinarySearch(newNode, ic);
            tmpIdNodes.Insert(~index, newNode);

        }


        return roots;
    }
}