Как использовать древовидную структуру данных в C #

Question

Я нашел реализацию для дерева на этом вопросе . К сожалению, я не знаю, как его использовать. Также я внес изменения в него, поскольку LinkedList не имеет метода Add:

delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
    T data;
    List<NTree<T>> children;

    public NTree(T data)
    {
        this.data = data;
        children = new List<NTree<T>>();
    }

    public void AddChild(T data)
    {
        children.Add(new NTree<T>(data));
    }

    public NTree<T> GetChild(int i)
    {
        return children[i];
    }

    public void Traverse(NTree<T> node, TreeVisitor<T> visitor)
    {
        visitor(node.data);
        foreach (NTree<T> kid in node.children)
            Traverse(kid, visitor);
    }
}

У меня есть класс с именем tTable, и я хочу сохранить в этом дереве его детей и их внуков (...). Мне нужно найти непосредственных детей, а не пересечь все дерево. Мне также может понадобиться найти детей по некоторым критериям. Допустим, у tTable есть только имя, и я хочу найти детей с именами, соответствующими некоторым критериям. Конструктор tTables присваивает имени значение согласно int-значению (каким-либо образом).

Как использовать Traverse (написать делегат), если у меня есть такой код;

int i = 0;
Dictionary<string, NTree<tTable>> tableTreeByRootTableName = 
                  new Dictionary<string, NTree<tTable>>();
tTable aTable = new tTable(i++);
tableTreeByRootTableName[aTable.Name] = new NTree(aTable);
tableTreeByRootTableName[aTable.Name].AddChild(new tTable(i++));
tableTreeByRootTableName[aTable.Name].AddChild(new tTable(i++));

tableTreeByRootTableName[aTable.Name].GetChild(1).AddChild(new tTable(i++));

Answer 1

Этот код будет проходить по дереву и добавлять все узлы, соответствующие указанному имени. Это C # 3x, для 2.0 вам понадобится анонимный делегат.

NTree<tTable> tree = new NTree<tTable>(table);

string nameToMatch = "SomeName";
LinkedList<tTable> matches = new LinkedList<tTable>();

tree.Traverse(tree, data => {
  if (data.Name == nameToMatch) {
    matches.AddLast(data);
  }
});

Answer 2

Чтобы получить какую-либо выгоду от использования деревьев над списками или хеш-таблицами, необходимо установить правила, определяющие, какие узлы являются дочерними по отношению к родительским узлам, а не другими родителями, и, возможно, порядок, в котором встречаются дочерние элементы. Например, дерево бинарного поиска гарантирует, что левые дочерние элементы меньше , чем текущий узел, а правые дочерние элементы больше , чем текущий узел. Это правило позволяет бинарному дереву поиска получать O (log n) времени поиска. Точно так же куча гарантирует, что корень больше, чем его дочерние элементы, что обеспечивает отличную производительность сортировки (наихудший случай O (n log n)).

Ваша проблема недостаточно указана, чтобы предоставить какое-либо преимущество использования дерева над другой структурой данных.