2

二分木をいじっていたところ、なぜ最初の実装は機能したのに 2 番目の実装は機能しなかったのか興味がありました。私は何を見落としていますか？些細なことだと思いますが、まだ見逃しています。

1:

//just a wrapper around the insertTree method.
public void insertKey(int key){
    
    if(root==null) //a private 'Node' variable.
        root = new Node(key);
    else
        insertTree(key, root);
}

//recursive insert - working
private void insertTree(int key, Node node)
{
    if(key <= node.getKey())
    {
        if(node.left!=null)
            insertTree(key, node.left);
        else
            node.left = new Node(key); //explicitly setting left child
    }
    else
    {
        if(node.right!=null)
            insertTree(key, node.right);
        else
            node.right = new Node(key); //explicitly setting right child
    }
            
}

機能していないバリアント:

2:

private void insertTree(int key, Node node)
{  //if node is null, create a new node. Can be either node.left or node.right
       if(node==null)
       {
           node = new Node(key);
           return;
       }
       else
          if(key <= node.getKey())
             insertTree(key, node.left);
          else
             insertTree(key, node.right);
                                
}

left, rightノードは、パブリックメンバーと 1 つのint keyデータ メンバーを持つ単純なクラスです。派手なものはありません。そのため、#1 は問題なく機能し、inorder traversal によってソートされた出力が生成されます。現在、＃2は機能していないようです。ルートは初期化される唯一のものであり、その左/右の子は引き続き null です。では、パラメーターとして渡す場合node.left、再帰的なメソッド呼び出しで新しいノードが割り当てられないのはなぜですか? ここで何が欠けていますか？Java は参照渡し (つまり、参照の値) であるため、これでうまくいくと思いますが、ここでちょっとしたことを見逃しているのかもしれません。

4

2 に答える 2

3

これが機能しない理由はnode、最後の再帰呼び出しの変数が、insertTree実際にはその前の呼び出しと同じメモリ位置を参照していないnode.leftためです。関数 (/メソッド) を呼び出すと、スタック上にすべてのパラメーターの新しい格納場所が効果的に作成され、そこにパラメーター値がコピーされます。

したがって、insertTree2 番目のバリアントでは、単に new を作成し、その関数Nodeのローカル変数に割り当てます。nodeその割り当ては、他のメモリ位置には影響しません。それが戻ってくると、新しいNodeものは永遠に失われます。

「Java は参照渡しである」と述べていますが、それは正しくありません。Java は参照を値渡しします。

于 2012-12-31T03:02:49.470 に答える
0

二分木に要素を追加するために再帰を使用しないでください。再帰には、高価な暗黙のスタックが含まれます。ノードを追加するための正しい場所を見つけるために単純に反復する必要があります。さらに、繰り返しを使用する場合、作業を行うために 2 つのメソッドは必要ありません。1 つあれば十分です。次の非常に単純なコードを見てください: http://www.geekviewpoint.com/java/bst/add

于 2012-12-31T17:55:54.010 に答える