Алгоритм для удаления дочерних элементов из массива

Question

Мне нужно написать algorithm для моего проекта. Ниже приведена проблема

Дерево, подобное структуре, для которой открыта только одна функциональность, т.е. до **getAllChildNodes**, которая возвращает все дочерние объекты определенного узла. Теперь мне задан массив узлов, я должен сохранить только верхний родительский узел.

Пример: Допустим, есть 3 дерева

Tree 1 : P1 has two children C11 & C12 

Tree 2 : P2 has 1 children C21, and C21 has 2 child C22, C23 

Tree 3 : P3 has 2 Children C31 and C32 

Now if given an array say { C11, C21, C22 , P1, P3, C32} 
The expected result is { C21, P1 , P3 } 

Позвольте мне знать, если требуется больше информации с моей стороны.

Дополнительная информация: Я сделал это, сначала получив все дочерние элементы первого элемента массива, а затем сравним с остальными элементами массива и аналогично с каждым элементом. но это имеет большую сложность. i.e n * n * getAllChildNodes. Я здесь для лучшего предложения

Answer 1

Выберите i-й элемент массива и добавьте все его дочерние элементы в хэш-карту (используя заданную функцию). Сделайте это для i 1 до n (полный проход)

Loop i от 1 до n и для каждой итерации проверьте, присутствует ли элемент в hashmap.

Если он присутствует, удалить его из массива,

еще продолжают

Обратите внимание на порядок проверки, если элемент принадлежит к HashMap О (1), а также порядок добавления O (1) , avearage. Таким образом, алгоритм O (n * getAllChlidNodes) средний

Answer 2

Вы можете сделать это легко. сначала создайте метод isPresent(node), чтобы проверить, присутствует ли узел в массиве. Затем введите каждый узел, заданный для поиска его родителя.

if(isPresent(x->parent)) push(x->parent); 

Продолжите эту публикацию для получения полного списка. Теперь recursively проверить, есть ли у current listparents present. Как только вы начнете, вы получите его. Если есть какие-то родители, только pop() эти элементы. Надеюсь, это поможет :)

Answer 3

Если вы могли бы получить функцию сначала, как getParentNode (childNode), или создать карту/мультимагр дочернего элемента как ключа и родителя как значение, как шаг предварительной обработки, тогда проблема станет очень простой.

Если у вас есть getParentNode (childNode), просто пройдите через массив и подтолкните родителей к набору.

Если у вас есть карта/Multimap от ребенка как ключ и родителя в качестве значения в качестве предварительной стадии обработки затем применить Algo, как упомянуто adi