java - 将(二叉搜索树)的递归插入更改为非递归？

Question

我正在尝试将 BST 的递归插入方法更改为非递归(可能是 While 循环)改变的原因是因为我想看看它是否可能。

这是插入代码:

public void insert(String value)
{
    //The node is stored in the root
    root = insert(value,root);
}


private Character insert(String value,Character current)
{   
    if(current == null)
    {
        //Add the root if the tree empty 
     current = new Character(value);
    }
    else
        //If the value that we want to insert < root value, then keep going to left till 
        //it's empty then inserted at left end. Done by recursion 
        if(value.compareTo(current.getElement())<=-1)
        {
            current.setLeft(insert(value,current.getLeft()));
        }
        else
            //If the value that we want to insert > root value, then keep going to right till 
            //it's empty then inserted at right end. Done by recursion 
            if(value.compareTo(current.getElement())>=1)
            {
                current.setRight(insert(value,current.getRight()));
            }
            else
            {
                //Else, the number we want to insert in already in the tree
                System.out.println("Duplicate numbers inserted" + current.getElement());
            }
    //returning the node tree so that we store it in the root 
    return current;
}

我可以将此代码更改为非递归吗？

干杯

Answer 1

是的，但是您需要稍微改变数据结构才能使其正常工作。该节点必须知道其左子节点和右子节点。

算法如下:

current = root;
while(current != null){
   if(value.compareTo(current.getElement())<=-1)
   {
        current = current.left_child;
   }else if(value.compareTo(current.getElement())>=1){
        current = current.right_child;
   }else{
        // Duplication
   }
}

其实之前有一些很好的例子，你可能想先看看:

• Write a non-recursive traversal of a Binary Search Tree using constant space and O(n) run time
• Nonrecursive/Iterative Binary Search Tree in C (Homework)