Создайте простую, высокопроизводительную древовидную структуру данных в c #

Question

Мне нужно создать каталог товаров, в виде дерева.

каждый узел дерева представлен идентификатором (строкой), функции только для данных дерева 2:

1. getChild(string ID), дайте удостоверение личности, получите детей (не нужно включать детский дети), если идентификатор равен нулю, получить все корневые узлы
2. getParent(string ID), вернуть родительский идентификатор, если есть, или нуль, если есть корень

Так как, как только дерево решится, оно не изменится, поэтому я думаю, что лучше будет поместить весь код в статический. Поэтому я начинаю пытаться использовать словарь

"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

Я создал класс узла , который может быть полезным.Это быстро и имеет некоторые дополнительные свойства, такие как:

• Предки
• Потомки
• Братья и сестры
• Уровень узла
• Родитель
• Корень
• И т. Д.

Answer 3

Вы можете написать простое двоичное дерево, я пишу псевдокод ниже:

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

}

Но если количество ваших данных очень велико, возможно, дерево AVL более эффективно