代码之家 › 专栏 › 技术社区 › A.Learn

转换树中的表

tree data-structures c#

A.Learn · 技术社区 · 6 年前

在我的程序中将平面db实体转换为树数据结构,是否还有改进的余地。

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

2 回复 | 直到 6 年前

Aldert 6 年前

创建了一个通用方法,表对象需要遵循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;
    }
}

jdweng 6 年前

使用递归代码尝试以下解决方案:

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