給定一棵任意有序的樹，我如何找到任意一組元素的第一個和最後一個元素？

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