如何從樹中構造一棵沒有遞歸的樹

我有一棵芒果項目，並且對於每個項目我想應用一種處理將它們變成蘋果，我該如何編寫一個方法（在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

如何從樹中構造一棵沒有遞歸的樹

回答

相關問題