algorithm - 给定一个任意排序的树，我如何找到任意一组元素的第一个和最后一个元素？

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();
}