在c#中构建一个简单,高性能的树数据结构

Question

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

每个树节点都以ID(字符串)表示,树数据上的函数只有2:

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

由于一旦树决定了,不会改变,所以我认为把所有代码放在静态中会是最好的.所以我开始尝试使用Dictionary

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

由于大约1000多个目录,我发现我很快搞砸了自己,在静态数据中出现了很多错误,并使最终结果可用.此外,现在我只写了几十个,代码看起来像混乱.

请建议以高性能创建这个简单的目录树.谢谢

Answer 1

只是做一个课程.

更新:

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

静态定义的用法非常简单:

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"),
                       }
               };

编辑

更多功能,更容易创建......

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");

Answer 2

我创建了一个可能有用的Node类.它很快并且具有一些额外的属性,例如:

• 祖先
• 后人
• 兄弟姐妹
• 节点的级别
• 亲
• 根
• 等等.