Как отсортировать вложенные друг в друга объекты?
Имеется следующий тип.
class SomeType { public int Id; public string Name; public int ParentSomeTypeId } |
class SomeType { public int Id; public string Name; public int ParentSomeTypeId }
В условный метод приходит список вот таких объектов, где некоторые из них могут могут быть дочерними по отношению к другим.
Прошу подсказать самый оптимальный способ отсортировать такой список, что бы без родителя был самым первым и дальше по убыванию, к дочерним. Что бы самым последним был объект без дочерних элементов.
Дополнительно:
Как вариант - можно пройтись по этому дереву/лесу и каждому элементу посчитать две метрики:
1. Глубина (удалённость от корня)
2. "Высота" (удалённость от листьев)
И потом отсортировать по глубине от меньшего у большему. Если глубина у двух узлов одинаковая, то добавить "высоту" по убыванию. Если и высота одинаковая - смотреть на id/имя/порядковый номер.
Ответы:
сортировка "дерева" не имеет смысла, если вы не делаете проекцию на массив/коллекцию..
если делаете, то совет Василий Банников, самодостаточен..
есть отдельная тема "балансировка деревьев"... применимо ли?... зависит от способа построения и типа дерева
В голову приходит схема сортировки тройки (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. "дальше по убыванию, к дочерним" не совсем понял, что имеется ввиду
Судя по вашему сегодняшнему вопросу, в котором вы пытаетесь решать эту задачу дальне вам нужно сделать эту работу на уровне БД.
Если так, то для этого многие (хоть и не все, но, к примеру, в MS SQL Server и в PostgreSQL она AFAIK есть) СУБД имеют функциональность reursive CTE.
Попробуйте поискать решение в этом направлении.
Опишите проблему, и специалист поможет с настройкой, исправлением ошибки или доработкой сайта. Подберём понятный план работ без лишней переписки.
Пока нет других ответов. Будьте первым, кто поможет автору.
Ответить на вопрос
Для того чтобы отсортировать вложенные объекты друг в друга, можно воспользоваться алгоритмом обхода дерева в глубину (Depth-First Search, DFS). Этот алгоритм позволяет обойти все вершины графа (или в данном случае объекты) в глубину, начиная с корневого объекта.
Пример реализации сортировки вложенных объектов на PHP с использованием алгоритма DFS:
function dfs($node, &$result) { $result[] = $node->value; foreach ($node->children as $child) { dfs($child, $result); } } // Пример структуры объектов $node1 = new stdClass(); $node1->value = 1; $node1->children = []; $node2 = new stdClass(); $node2->value = 2; $node2->children = []; $node3 = new stdClass(); $node3->value = 3; $node3->children = []; $node1->children = [$node2, $node3]; $result = []; dfs($node1, $result); print_r($result);
В данном примере создаются три объекта $node1, $node2 и $node3, где $node1 содержит $node2 и $node3 в качестве дочерних объектов. Функция dfs() рекурсивно обходит все дочерние объекты начиная с $node1 и добавляет их значения в массив $result. После завершения работы функции, массив $result содержит значения всех объектов в порядке обхода.
Таким образом, используя алгоритм DFS, можно отсортировать вложенные объекты друг в друга и получить нужную структуру данных.