Как отсортировать вложенные друг в друга объекты?

Question

[CityzenUNDEAD]

Имеется следующий тип.

class SomeType
{
    public int Id;
    public string Name;
    public int ParentSomeTypeId
}

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

Comments

[Василий Банников]

Как вариант - можно пройтись по этому дереву/лесу и каждому элементу посчитать две метрики:
1. Глубина (удалённость от корня)
2. "Высота" (удалённость от листьев)

И потом отсортировать по глубине от меньшего у большему. Если глубина у двух узлов одинаковая, то добавить "высоту" по убыванию. Если и высота одинаковая - смотреть на id/имя/порядковый номер.

Answer 1

[#]

сортировка "дерева" не имеет смысла, если вы не делаете проекцию на массив/коллекцию..
если делаете, то совет Василий Банников, самодостаточен..
есть отдельная тема "балансировка деревьев"... применимо ли?... зависит от способа построения и типа дерева

Answer 2

[Сергей Соловьев]

В голову приходит схема сортировки тройки (id родителя; id потомка; название):
- id родителя - id узла-родителя, может быть null
- id потомка - id любого узла-потомка, может быть null
- название - это поле Name (скорее всего сортировка по нему нужна)

И тогда сравнение будет по соответствующим элементам тройки.
Причем, id родителя и id потомка могут быть null и в таком случае сравнение будет null first (т.е. null больше) и null last (т.е. null меньше) для id родителя и id потомка соответственно. А если равны, то уже по имени (Name) сравниваем.
Вроде бы условия соблюдаются:
- Без родителя первый: id родителя = null - больший вес при сравнении
- Самый последний - объект без дочерних элементов: id потомка = null - больший вес при сравнении
- Дальше по убыванию к дочерним: id - можно как числа сравнивать

P.S. "дальше по убыванию, к дочерним" не совсем понял, что имеется ввиду

Answer 3

[MVV]

Судя по вашему сегодняшнему вопросу, в котором вы пытаетесь решать эту задачу дальне вам нужно сделать эту работу на уровне БД.
Если так, то для этого многие (хоть и не все, но, к примеру, в MS SQL Server и в PostgreSQL она AFAIK есть) СУБД имеют функциональность reursive CTE.
Попробуйте поискать решение в этом направлении.