Как построить дерево из дерева без рекурсии

Question

У меня есть дерево элементов Манго, и для каждого элемента, который я хочу применить обработку, чтобы превратить их в Яблоки, как я могу написать метод (в Java будет приятно) который берет верхнюю часть элемента дерева манго и возвращает вершину яблок Дерево без рекурсии.

С рекурсией у меня есть что-то вроде этого:

Apple transform(Mangoe ma){  
    //Construct an apple from some modified mangoes properties 
    Apple ap = new Apple(...); 
    List<Apple> apChildren = new ArrayList<Apple>(); 
    for(Mangoe maChild:ma.getChildren()) 
     children.add(transform(maChild)); 
    ap.setChildren(children); 
    return ap; 
} 

Как я могу повторить это поведение с помощью метода без рекурсии ??

EDIT: я думал об этом алгоритме, чтобы решить эту проблему:

List<Mangoe> itemsToTreat = new ArrayList<Mangoe>(); 
itemsToTreat.add(ma); 

while(itemsToTreat!=null){ 
    //Apply treatment 
    //it's impossible to set the child of a created apple without recursion   

    //get the direct children of itemsToTreat 
    itemsToTreat = getDirectChildrenOfItemsToTreat(itemsToTreat); 


} 

Answer 1

Поскольку я не так свободно в Java на данный момент, я буду использовать некоторые Java-подобный псевдокод и некоторые пояснения. Проблема может быть решена с помощью определенных пользователем стеков следующим образом. Ключ состоит в том, чтобы хранить некоторую информацию, где хранить сгенерированные результаты, которые неявно выполняются в стеке вызовов в рекурсивной реализации; это делается со следующим вспомогательным классом, который хранит достаточно информации.

class AugmentedMangoe 
{ 
    public Mango iMangoe;  // Mangoe to convert 
    public Apple iParentApple; // place where to add it as child after conversion 

    public AugmentedMangoe(Mangoe iMangoe, Apple iParentApple) 
    { 
     iMangoe = iMangoe; 
     iParentApple = iParentApple; 
    } 
} 

Фактический итерационный процесс осуществляется через iStack моделирующих рекурсии.

Apple transform(Mangoe ma) 
{ 
    Apple Result = null; 
    Stack<AugmentedMangoe> iStack = new Stack<AugmentedMangoe>(); 
    iStack.push(new AugmentedMangoe(ma, null)); 
    while (iStack.hasElements()) 
    { 
     // get current Mangoe 
     Mangoe iCurrentMangoe = iStack.pop(); 

     // convert Mangoe to Apple and save it 
     Apple iCurrentApple = new Apple(iCurrentMangoe.iMangoe); 

     // store the converted root, which is done only in the first iteration 
     Result = null != Result ? Result : iCurrentApple; 

     // put children to the stack 
     for(Mangoe iChild:iCurrentMangoe.iMangoe.getChildren()) 
      iStack.push(new AugmentedMangoe(iChild, iCurrentApple)); 

     // if we have stored where to put the converted object to, put it there 
     if (null != iCurrentMangoe.iParentApple) 
      iCurrentMangoe.iParentApple.addChild(iCurrentApple); 
    } 
    return Result: 
} 

Если это не будет Mango вместо Mangoe, предполагается, что magnifera indica имеется в виду?