用c#构建一个简单、高性能的树数据结构

Build a simple, high performance Tree Data Structure in c#

提问by Eric Yin

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

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

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

每个树节点都由一个 ID（字符串）表示，树数据上的函数只有 2 个：

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

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

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....]}

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.

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

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

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

采纳答案by SimpleVar

Just make a class out of it.

就用它来上课吧。

UPDATED:

更新：

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

Edit

编辑

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

Usage:

用法：

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

回答by llj098

You can write a simple binary tree , I wrote some Pseudo code beloew:

你可以写一个简单的二叉树，我在下面写了一些伪代码：

class TreeNode {
    TreeNode Right;
    TreeNode Left;
    int id;
    //...
}

class BinTree {

    void Insert(TreeNode node)
    {
        while(true) {   
            if(node.id > target.id) {
                if(target.Right != null) {
                    target = target.Right;
                    continue;
                }
                else {
                    target.Right = node;
                    break;
                }
            }

            else if(node.id < target.id) {
                if(target.Left != null) {
                    target = target.Left;
                    continue;
                }
                else {
                    target.Left = node;
                    break;
                }   
            }

            else {
                throw new ArgumentException("Duplicated id");
            }
        }
    }


    TreeNode Search(int id)
    {
        TreeNode target = root;

        while(target != null) {
            if(id > target.id) {
                target = target.Right;
            }
            else if(id < target.id) {
                target = target.Left;
            }
            else {
                return target;
            }
        }

        return null;
    }

}

But if your data count is very large, maybe AVL tree is more efficient

但是如果你的数据量非常大，也许 AVL 树更有效

回答by Alex Siepman

I created a Node classthat could be helpfull. It is fast and has some extra properties, like:

我创建了一个可能有用的Node 类。它很快并且有一些额外的特性，比如：

• Ancestors
• Descendants
• Siblings
• Level of the node
• Parent
• Root
• Etc.

• 祖先
• 后代
• 兄弟姐妹
• 节点级别
• 家长
• 根
• 等等。