0

Есть дерево вида

                               a
                              /|\
                             b c d
                            /\    \
                           e  f     g

Как можно получить список дочерних элементов по какому-то элементу (Передали в ф-цию "a", а получили массив из [b,c,d,e,f,g]. Передали "b" получили [e,f]) Элемент имеет идентификатор родителя, а так же является ли он "контейнером"

 protected void fetchChildElements(Elem parentElem, List<Elem> childElems, List<Elem> allElem) {
        for (Elem childElem : allElem) {
            String parentElemId = childElem.getParentElemId();
            if (parentElemId != null && parentElemId.equals(parentElem.getId())) {
                if (childElem.getElemCategory() == DeviceCategory.CONTAINER) {
                    fetchChildElements(childElem, childElems, allElem);
                }
                childElems.add(childElem);
            }
        }
    }
3
  • А стандартный обход в глубину чем вам не угодил? Или у элемента нету ссылок на дочерние элементы?
    – VladD
    Commented 17 июн. 2021 в 9:26
  • @VladD Да, родитель не знает о дочерних
    – mesfex
    Commented 17 июн. 2021 в 9:58
  • Но у вас есть список всех элементов? Похоже, вам нужна топологическая сортировка.
    – VladD
    Commented 17 июн. 2021 в 11:26

1 ответ 1

4

Ну например так.

Давайте построим отображение элемента в его родителя. Это можно сделать один раз, и обновлять таблицу при каждом изменении дерева. Или просто использовать вместо функции String getParentElemId() функцию Elem getParentElem().

Получится вот что:

Map<String, String> mapToParent = 
    Arrays.stream(allElements)
          //.collect(Collectors.toMap(Elem::getId, Elem::getParentId)); // WTF Java?
          .collect(HashMap::new,
                   (m, elem) -> m.put(elem.getId(), elem.getParentId()),
                   HashMap::putAll);

Теперь чтобы проверить каждый элемент, достаточно пройтись по цепочке родителей, и искать в ней нужное:

String rootId = "b";
Arrays.stream(allElements)
      .filter(elem -> {
          String curr = elem.getId();
          while (curr != null && !curr.equals(rootId)) curr = mapToParent.get(curr);
          return curr != null; })
      .forEach(elem -> System.out.println(elem.getValue()));

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.