2 
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 迭代器。

请指导我。

4

2 回答 2

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

演示。

于 2014-10-28T19:03:29.750 回答
0

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

但是我放弃了这个逻辑，因为它的执行效果并不好，它比递归对应物花费了更多时间。

于 2014-11-09T09:14:55.490 回答