java - 如何将以下递归函数转换为 for 循环迭代

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

这是我的三叉树中的一段代码，我用它来插入一个人的名字(名字中可以有多个单词，比如 Michele Adams、Tina Joseph George 等)。我想将上面的递归转换为 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.