java如何从一棵树构造一棵树而无需递归

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

我怎么能用一个没有递归的方法重复这种行为呢

编辑： 我在考虑这个算法来解决这个问题：

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:
}

如果magnifera indica是指magnifera indica，它不应该是芒果而不是芒果