0

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

このコードを非再帰に変更できますか?

乾杯

4

3 に答える 3

1

はい、挿入関数を非再帰的に定義できます。

ただし、これを行うには、挿入関数で、再帰的に定義される BST の順序内トラバーサル イテレータを定義する必要があります。

順序通りのトラバーサルを非再帰的に定義する方法があると思いますが、実装によっては非常に非効率になる可能性があります。

BST 自体は基本的に再帰的に定義されており、挿入関数を再帰的に定義することは常に効率的です。（本当に必要な場合は、疑似コードを書くこともできますが、それは意味がないと思いますし、インオーダートラバーサルイテレータの実装の詳細については知りません）

これを回答として選択することを忘れないでください:-)

于 2013-04-20T07:37:34.447 に答える