如何从树中构造一棵没有递归的树

我有一棵芒果项目，并且对于每个项目我想应用一种处理将它们变成苹果，我该如何编写一个方法（在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); 


}

来源

2017-01-13 Philippe Simo

在大多数情况下，您可以用循环和某种堆栈来替换递归调用，例如，看看[这里]（https://blogs.msdn.microsoft.com/ericlippert/2005/08/01/recursion-part-two-unrolling-a-recursive-function-with-an-explicit-stack/）。毕竟，递归方法调用也是这样做的：他们只是在调用堆栈上再次调用同一个方法，并附带一些参数信息等。 – Thomas

我不确定递归是什么意思。您可以使用堆分配的数据结构来处理递归而不是系统堆栈，从而将递归过程编写为迭代循环。如果没有任何种类的递归过程，你就无法做到这一点，因为这需要树的每个节点都不会有多于一个孩子，因此也就是一个链表。 – Sylwester

如果你使用'Tree'结构，恐怕你不得不使用递归，隐藏或显式。例如，如果你使用'TreeSet'，你可能会得到它的迭代器，并用'while'循环遍历所有的元素。但是在迭代器中，会有多次对'TreeMap.successor（条目 t）'方法的递归调用 –

因为我不是在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: 
}

它不应该是芒果而不是Mangoe，假设magnifera indica意思？

来源

2017-01-13 15:27:44 Codor

如何从树中构造一棵没有递归的树

回答

相关问题