如何轉換下面的遞歸函數爲循環迭代

Question

Iterator words = treeSearch.getItems().iterator(); 

int addCount = 0; 
while (words.hasNext()) 
{ 
    numWords++; 
    rootNode = add(objectToReference, addCount++, (ITreeSearch) words.next(), 0, rootNode); 
} 


//Add to the Tree 
private TernaryTreeNode add(Object storedObject, int wordNum, ITreeSearch treeSearch, int pos, TernaryTreeNode parentNode) throws NoSearchValueSetException 
{ 

    if (parentNode == null) 
    { 
     parentNode = new TernaryTreeNode(treeSearch.getNodeValue(pos)); 
    } 


    if (parentNode.lessThan(treeSearch, pos)) 
    { 
     parentNode.left = add(storedObject, wordNum, treeSearch, pos, parentNode.left); 
    } 
    else if (parentNode.greaterThan(treeSearch, pos)) 
    { 
     parentNode.right = add(storedObject, wordNum, treeSearch, pos, parentNode.right); 
    } 
    else 
    { 
     if (pos < treeSearch.getNumberNodeValues()) 
     { 
      parentNode.mid = add(storedObject, wordNum, treeSearch, pos + 1, parentNode.mid); 
     } 
     else 
     { 
      numberOfObjectsStored++; 
      parentNode.addStoredData(storedObject); 
     } 
    } 

return parentNode; 
} 

這是我在我的三叉樹，我使用插入人的名稱代碼片段（可以甲肝多個字的名字，像米歇爾·亞當斯，蒂娜約瑟夫喬治等）。我想將上面的遞歸轉換爲for循環/ while迭代器。

請指導我。

Answer 1

通過迭代替換遞歸的一般思路是創建一個狀態變量，並通過遵循遞歸程序中遵循的相同規則在循環中更新它。這意味着當你在遞歸程序中選擇一個左子樹時，你更新狀態來引用左子樹;當您轉到右側子樹時，狀態會更改爲引用右側子樹，依此類推。

下面是如何改寫經典插入二叉樹沒有遞歸的例子：

public TreeNode add(TreeNode node, int value) { 
    // Prepare the node that we will eventually insert 
    TreeNode insert = new TreeNode(); 
    insert.data = value; 
    // If the parent is null, insert becomes the new parent 
    if (node == null) { 
     return insert; 
    } 
    // Use current to traverse the tree to the point of insertion 
    TreeNode current = node; 
    // Here, current represents the state 
    while (true) { 
     // The conditional below will move the state to the left node 
     // or to the right node, depending on the current state 
     if (value < current.data) { 
      if (current.left == null) { 
       current.left = insert; 
       break; 
      } else { 
       current = current.left; 
      } 
     } else { 
      if (current.right == null) { 
       current.right = insert; 
       break; 
      } else { 
       current = current.right; 
      } 
     } 
    } 
    // This is the original node, not the current state 
    return node; 
} 

Demo.

Answer 2

由於dasblinkenlight ..

這是我的用於替換上述遞歸邏輯函數爲三元樹。

Iterator words = treeSearch.getItems().iterator(); 

    while (words.hasNext()) 
    { 
     for (int i = 0; i < word.getNumberNodeValues(); i++) 
     { 
      add_Non_Recursive(objectToReference, word, i); 
     } 
    } 

    //Add to Tree 
    private void add_Non_Recursive(Object storedObject, ITreeSearch treeSearch, int pos) throws NoSearchValueSetException 
    { 
     TernaryTreeNode currentNode = rootNode; 

     // Start from a node(parentNode). If there is no node, then we create a new node to insert into the tree. 
     // This could even be the root node. 
     if (rootNode == null) 
     { 
      rootNode = new TernaryTreeNode(treeSearch.getNodeValue(pos)); 
     } 
     else 
     { 
      while (currentNode != null) 
      { 
       if (currentNode.lessThan(treeSearch, pos)) 
       { 
        if (currentNode.left == null) 
        { 
         currentNode.left = new TernaryTreeNode(treeSearch.getNodeValue(pos)); 
         currentNode = null; 
        } 
        else 
        { 
         currentNode = currentNode.left; 
        } 
       } 
       else if (currentNode.greaterThan(treeSearch, pos)) 
       { 
        if (currentNode.right == null) 
        { 
         currentNode.right = new TernaryTreeNode(treeSearch.getNodeValue(pos)); 
         currentNode = null; 
        } 
        else 
        { 
         currentNode = currentNode.right; 
        } 
       } 
       else 
       { 
        if (currentNode.mid == null) 
        { 
         currentNode.mid = new TernaryTreeNode(treeSearch.getNodeValue(pos)); 
         currentNode = null; 
        } 
        else 
        { 
         currentNode = currentNode.mid; 
        } 
       } 
      } 
     } 
    } 

但是我放棄了這個邏輯，因爲它在表演中表現不是很好，它比遞歸的對手花費了更多的時間。