Иерархическая c # сортировка рекурсивно

Question

У меня есть структура данных, набранная так:

 class Something {
   public string Name { get; set; }
   public List<Something> Children {get; set;}

   public Something() {
     Children = new List<Something>();
   }
 }

Пример данных:

    var one = new Something();
    one.Name = "B";

    var two = new Something();
    two.Name = "A";

    var three = new Something();
    three.Name = "C";

    one.Children.Add(new Something { Name = "F"});
    one.Children.Add(new Something { Name = "E"});
    one.Children.Add(new Something { Name = "D"});

    three.Children.Add(new Something { Name = "F"});
    three.Children.Add(new Something { Name = "E"});
    three.Children.Add(new Something { Name = "D"});

    var data = new List<Something>();
    data.Add(one);
    data.Add(two);
    data.Add(three);

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

Пока у меня есть это:

public static List<Something> SortTree(List<Something> node) {
  if (node == null) {
    return null;
  }

  return node
    .OrderBy(x => x.Name)
    .Select(y => {
       if (y.Children.Count() > 0) {
         var t = y.Children;
         SortTree(t.ToList());
       }

       return y;
    })
    .ToList();
  }

Вызов SortTree(data) возвращает данные только сРодительский уровень отсортирован.

Спасибо за помощь.

Answer 1

Если вы хотите что-то сделать рекурсивно, вы не можете писать свой собственный цикл.По крайней мере, насколько мне известно (что далеко не завершено), вы не можете продолжать просто использовать linq.Вы должны написать цикл сортировки самостоятельно.

В этот момент рекурсивно вызывается "SortTree (current);"становится тривиальным

Answer 2

В случае, если у вас есть сетка (а не просто дерево ) с циклами (дочерний элемент является родительским для себя), у вас будут проблемы с рекурсией ,Другая возможная проблема (тот же переполнение стека ) - это когда слишком глубокий ("Глубина дерева произвольная ").Я предлагаю немного модифицированный BFS алгоритм

public static List<Something> SortTree(List<Something> node) {
  Queue<List<Something>> agenda = new Queue<List<Something>>();

  agenda.Enqueue(node);

  HashSet<List<Something>> alreadySorted = new HashSet<List<Something>>() { null };

  while (agenda.Any()) {
    var current = agenda.Dequeue();

    if (alreadySorted.Add(current)) {
      current.Sort((left, right) => string.Compare(left.Name, right.Name));

      foreach (var child in current)
        agenda.Enqueue(child.Children);
    }
  }

  return node;
}

Answer 3

В вашей строке

SortTree(t.ToList());

вы напрямую отбрасываете результат, поскольку фактически никогда не обновляете поле Children.

Возможно, вы хотите что-то вроде

y.Children = SortTree(y.Children.ToList());

Хотя я бы попытался изменить ваш SortTree() на метод, который не возвращает значение.