Сортировка корневых узлов для деревьев алгоритма

Question

Я пытаюсь выяснить алгоритм для решения этой проблемы:

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

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

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

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

Так что я по сути сортирую деревья самостоятельно, а не все узлы. Узлы, не являющиеся корневыми, должны NOT быть отсортированы. Таким образом, вы можете сказать, является ли родительский узел «нулевым», то он является корневым узлом.

ПРИМЕЧАНИЕ: Программирование в Javascript/Угловая

Answer 1

Похоже, вы могли бы написать функцию сравнения, чтобы сделать это для вас. Вы не говорите, что язык вы используете, но я думаю, что вы можете почерпнуть суть его от этого:

int Compare(Node node1, Node node2) 
{ 
    if (node1.Parent == null and node2.Parent == null) 
    { 
     // two root nodes. Compare their names. 
     return node1.Name.CompareTo(node2.Name); 
    } 

    if (node1.Parent == null) 
    { 
     // node1 is a root node and node2 isn't. 
     // node1 sorts first. 
     return -1; 
    } 

    if (node2.Parent == null) 
    { 
     // node2 is a root node and node1 isn't. 
     // node2 sorts first. 
     return 1; 
    } 

    // neither is a root node, so they're considered equal. 
    return 0; 
} 

Это было бы уладить это так, что у вас есть:

root1 
root2 
root3 
(other roots) 
all children 

Теперь, если вы хотите отсортировать массив таким образом, чтобы у вас было:

root1 
child of root1 
child of root1 
child of root1 
root2 
child of root2 
child of root2 
root3 
... 

Затем вы изменяете это сравнение. Сравнение корневых узлов остается неизменным. Когда вы сравниваете два дочерних узла, вы сравниваете имена своих родительских узлов. При сравнении корневого узла с дочерним элементом вы сравниваете имя корневого узла с именем родителя ребенка. О, и вы должны иметь специальный случай, когда дочерний узел сравнивается с его собственным родителем.