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

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