Как получить все узлы корневого узла верхнего уровня в n-арном дереве?

avatar
JavaUser
9 августа 2021 в 02:45
78
0
0

У меня есть древовидная структура, представленная ниже. У него есть узлы, являющиеся частью группы, а группа может иметь подгруппу. Структура представлена ​​в XML следующим образом. Если передать какой-либо узел в этой структуре, нам нужно вернуть узел верхнего уровня в этой структуре. Например, просто если мы передаем Node3 id 1004, алгоритм должен вернуть Node1, Node2, Node3. Если мы передаем Node5 id 1008, то алгоритм должен возвращать все узлы GroupB <Node4,Node5,Node6>, а не только <Node5,Node6>. Предложите какой-нибудь эффективный алгоритм для получения корневого узла.

GroupA
   -- Node1
   -- Node2
   -- Node3
GroupB
   --Node4
   --SubGroupB
        --Node5
        --Node6
GroupC
   --Node7

XML representation
      <GroupA>
          <id>1001</id>
          <Node1><id>1002</id></Node1>
          <Node2><id>1003</id></Node2>
          <Node3><id>1004</id></Node3>
      <GroupB>
          <id>1005</id></id>
          <Node4><id>1006</id></Node4>
          <sub-group>
             <id>1007</id>
             <Node5><id>1008</id></Node5>
             <Node6><id>1009</id></Node6>
          </sub-group>
      <GroupC>
          <id>1007</id>
          <Node7><id>1010</id></Node6>
Источник
Michael Katt
9 августа 2021 в 05:31
0

Вы ввели id как элемент. Поэтому id также будет узлом. Я бы определил id как атрибут.

trincot
10 августа 2021 в 08:24
0

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

Ответы (0)