建立在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（字符串ID），给一个ID，让孩子（无需包括儿童'
   子女），如果ID为空，让所有根节点


2. 的getParent（字符串ID），回报如果父ID拥有或空，如果是root

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

推荐答案

只要一个类出来的。

< STRONG>更新：

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屋！