用c#构建一个简单、高性能的树数据结构 [英] Build a simple, high performance Tree Data Structure in c#

问题描述

我需要创建一个树型产品目录.

I need to create a product catalog, in tree type.

每个树节点用一个ID(字符串)表示，树数据上的函数只有2个:

every tree node presents by a ID(string), the functions on the tree data only 2:

1. getChild(string ID)，给一个ID，得到children(不需要包含childs的children)，如果ID为空，获取所有根节点
2. getParent(string ID)，如果有则返回父ID，如果是root则返回null

1. getChild(string ID), give a ID, get children (no need include childrens' children), if ID is null, get all root nodes
2. getParent(string ID), return parent ID if have, or null if is root

既然一旦树决定了，就不会改变，所以我认为把所有代码都放在静态中会是最好的.所以我开始尝试使用字典

Since once the tree decided, will not change, so I think put all code in static will be best. So I start to try use Dictionary

"id": {parent:ID, child:[id2, id3, id4....]}

因为有大约 1000+ 个目录，我发现我很快就把自己搞砸了，静态数据中有很多错误，最终结果可用.另外，现在我只写了几十个，代码看起来一团糟.

Since theres about 1000+ catalog, I found I quickly mess myself up, lots of mistake in the static data, and make final result on usable. Also, now I only wrote dozens and the code is looking like mess.

请建议一种创建这种高性能简单目录树的方法.谢谢

Please advice a way create this simple catalog tree with high performance. Thanks

推荐答案

用它创建一个类.

更新:

class TreeNode : IEnumerable<TreeNode>
{
    private readonly Dictionary<string, TreeNode> _children =
                                        new Dictionary<string, TreeNode>();

    public readonly string ID;
    public TreeNode Parent { get; private set; }

    public TreeNode(string id)
    {
        this.ID = id;
    }

    public TreeNode GetChild(string id)
    {
        return this._children[id];
    }

    public void Add(TreeNode item)
    {
        if (item.Parent != null)
        {
            item.Parent._children.Remove(item.ID);
        }

        item.Parent = this;
        this._children.Add(item.ID, item);
    }

    public IEnumerator<TreeNode> GetEnumerator()
    {
        return this._children.Values.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    public int Count
    {
        get { return this._children.Count; }
    }
}

静态定义的用法相当简单:

Usage will be fairly simple to statically define:

var tree = new TreeNode("Root")
               {
                   new TreeNode("Category 1")
                       {
                           new TreeNode("Item 1"),
                           new TreeNode("Item 2"),
                           new TreeNode("Item 3"),
                       },
                   new TreeNode("Category 2")
                       {
                           new TreeNode("Item 1"),
                           new TreeNode("Item 2"),
                           new TreeNode("Item 3"),
                           new TreeNode("Item 4"),
                       }
               };

编辑

更多功能，让创作更轻松...

Some more functionality for even easier creation...

public static TreeNode BuildTree(string tree)
{
    var lines = tree.Split(new[] { Environment.NewLine },
                           StringSplitOptions.RemoveEmptyEntries);

    var result = new TreeNode("TreeRoot");
    var list = new List<TreeNode> { result };

    foreach (var line in lines)
    {
        var trimmedLine = line.Trim();
        var indent = line.Length - trimmedLine.Length;

        var child = new TreeNode(trimmedLine);
        list[indent].Add(child);

        if (indent + 1 < list.Count)
        {
            list[indent + 1] = child;
        }
        else
        {
            list.Add(child);
        }
    }

    return result;
}

public static string BuildString(TreeNode tree)
{
    var sb = new StringBuilder();

    BuildString(sb, tree, 0);

    return sb.ToString();
}

private static void BuildString(StringBuilder sb, TreeNode node, int depth)
{
    sb.AppendLine(node.ID.PadLeft(node.ID.Length + depth));

    foreach (var child in node)
    {
        BuildString(sb, child, depth + 1);
    }
}

用法:

var tree = TreeNode.BuildTree(@"
Cat1
 Sub1
  Item1
  Item2
  Item3
 Sub2
  Item1
  Item2
Cat2
 Sub1
 Sub2
  Item1
  Item2
 Sub3
  Item1
Cat3
Cat4");

这篇关于用c#构建一个简单、高性能的树数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！