Javaバイナリ検索ツリー - 再帰ボイドコピー方法

Question

私の割り当てのためにバイナリ検索ツリーのための再帰的コピー方法を最初から作成する必要があります。このメソッドは、指定されたBinarySearchTreeオブジェクトの各項目を呼び出し元のBinarySearchTreeオブジェクトにコピーする必要があります。問題は、メソッドがvoidでなければならないということだけです。このトピックで調べたすべてが、これを行うために異なる戻り値の型を使用しているようです。

私はこのようなものから始める方法も本当に分かりません。私が持っているのは、メソッドの空のシェルとラッパーです。プライベートメソッドのパラメータが正しいかどうかはわかりませんが、それは私の最初の推測でした。

public void copy(BinarySearchTree<E> bst2){ 
     copy(bst2, root, bst2.root); 
    } 

private void copy(BinarySearchTree<E> bst2, Node node1, Node node2){ 
    } 

私は何かすべての助けに感謝します。

ありがとうございます！

class Tree { 
    //stuff in the tree with a root node, etc... 

    copyTree(Node parentTreeNode, Node copyTreeNode) { 
      if(copyTreeNode == null) 
       return; 
      parentTreeNode = clone(copyTreeNode) //clone just copies the node's values into the node. 
      if(copyTreeNode.leftChild != null) { 
       parentTreeNode.leftChild = new Node(); 
       copyTree(parentTreeNode.leftChild, copyTreeNode.leftChild); 
      } 
      if(copyTreeNode.rightChild != null) { 
       parentTreeNode.rightChild = new Node(); 
       copyTree(parentTreeNode.rightChild, copyTreeNode.rightChild); 
      } 
    } 
} 

そして、あなたはちょうど2つのルートノードでこれを呼び出し、それが再帰させ、それはあなたのためのツリーを構築します：

Answer 1

即時の思考は、（先にラフな擬似コード）です。

したがって、ベースケースがトリガーされると（現在のノードがヌルの場合）、そのノードをスキップして再帰プロセスで移動します（再帰的手法ではベースケースが重要です。そうでない場合、無限再帰が発生します）。したがって、ルートノードから始めてコピーし（ヌルでない場合）、それもヌルでないと仮定して左のサブツリーに移動します。このメソッドでは、このメソッドで一時停止し、サブツリーのメソッドをコールします。サブツリーのメソッドは「一時停止」し、左側には原因があります。戻ってきたら、「一時停止」した各場所が再開し、それらのノードのそれぞれについて、同じ手順で実行します。左のサブツリーが繰り返し再帰すると、一番上のノードで再開し、右のサブツリーに移動して同じことを行います（すべての子ノードで再帰的に行ったのと同じです）。すべて完了したら、正常に戻ります。

再帰は特に難しいことではありませんが、最初は理解するのが慣例になります。

これは大まかなアイデアであり、テストされていませんが、それはおおまかなやり方です。メインツリーにすでにデータが入っている場合、またはルートノード以外のノードを渡した場合、ツリーの処理方法が同じであるとは限りません。しかし、それはそのノードの下から同じでしょう。