在树中转换表 [英] Converting table in tree

问题描述

我的程序中是否有任何改进的余地，可以将平面db实体转换为树数据结构。
我不想失去通用灵活性，因为我应该能够对任何其他DBEntity类使用相同的方法

Is there any scope for improvement in my program which converts flat db entity to a tree data structure. I don't want to loose the Generic flexibility as i should be able to use the same method for any other DBEntity class

数据库接口实体类

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

数据库实体类示例

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

推荐答案

创建了通用方法，表对象需要遵循dbSet接口，而TreeNode对象需要遵循ITreeNode。我使用binarySerach使其尽可能快。无需递归。逻辑确保您不需要按特定顺序放置物品。当仍然存在未分配的对象时，我没有抛出错误，这很容易添加。

Created a generic approach, table objects need to follow the dbSet interface and TreeNode objects need to follow the ITreeNode. I used binarySerach to make this as fast as possible. No recursion needed. The logic ensures that you do not need to have the items in a particular order. I did not throw an error when out of the loop when there are still unassigned objects, this can be easy added.

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

这篇关于在树中转换表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！