Учитывая произвольно упорядоченное дерево, как мне найти первый и последний элемент произвольного множества его элементов?

Question

У меня есть дерево, построенное из TreeItems. Каждый TreeItem имеет следующие методы:

TreeItem   TreeItem::getParent()
TreeItem[] TreeItem::getChildren()
int        TreeItem::indexOf(TreeItem childItem)

У меня также есть неупорядоченный набор TreeItems из этого дерева. Я хочу быстро найти первый элемент и последний элемент этого набора.

Какие-нибудь умные идеи?

Answer 1

Выберите один из элементов дерева в вашем наборе (я предполагаю, что данный набор является поддеревом), затем сначала найдите родителя этого набора:

while (element.getParent()!=null)
  element = element.getParent();
parent = element;

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

TreeItem TreeItem::getLastChild()
{
 children = getChildren();
 if (children == null)
   return parent;

 int maxIndex = 0;

   // find child with maximum index
   .....

  return foundedChild.getLastChild();
}