3

私が抱えている問題は、署名付きのメソッドを書くことです

public static BinaryTree generate(BinaryTree root)

（他のパラメータを追加することは可能です）

このメソッドは、パラメーターとして指定されたようなもの (同じサイズなど) を返すBinaryTree必要があります。ノードの値を変更する場合にのみ必要です。結果のツリーの各ノードは、 で preorder traversal を使用するときに、同等のノードが処理された位置と等しい値を持つ必要がありますroot。1から数え始めます。

public class BinaryTree {
    public int value;
    public BinaryTree left;
    public BinaryTree right;

    public BinaryTree(int value, BinaryTree left, BinaryTree right)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

以下を試してみましたが、正しく動作しません。

public static BinaryTree preOrder(BinaryTree root, int num)
{
    //We ALWAYS give 1 as num value!!
    if (root == null)
        return null;

    root.value = num;       
    preOrder(root.left, ++num);         
    preOrder(root.right, ++num);

    return root;
}

たとえば、BinaryTree がある場合:

             3
         /      \
       2           1
    /     \
  1         0

(ノードにどんな値があるかは問題ではありません!)

メソッドは次のツリーを返す必要があります。

             1
         /      \
       2           5
    /     \
  3         4
4

2 に答える 2

0

再帰的な方法でこれを行うのが最も簡単です。ノード値を割り当てるには、再帰のすべてのレベルでアクセスできる静的カウンターを使用するのが最も簡単です。手順は簡単です。入力ツリーのノードにアクセスするたびに、静的カウンターに設定された値で出力ツリーに対応するノードを作成し、左右のサブツリー (存在する場合) で再帰する前にカウンターをインクリメントします。 .

(現在のコードのように) 引数を渡す代わりに静的変数を使用することintで、再帰が戻ったときに再帰のより深いレベルで行われたインクリメントが表示されます。

静的カウンターを使用したくない場合 (または規則に違反している場合) はint[1]、値を返すだけでなく値を渡すために使用できる配列を使用しintます。

これが明確でない場合は、さらに詳しく説明することができますが、これは学校の課題のように聞こえるため、コードは投稿しません。

編集これは学校の課題ではないため、必要なことを行うコードを次に示します。

public class BinaryTree {
    public int value;
    public BinaryTree left;
    public BinaryTree right;

    public BinaryTree(int value, BinaryTree left, BinaryTree right)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public static BinaryTree generate(BinaryTree root) {
        // allocate a counter and delegate to the recursive method
        int[] counter = {1};
        return generate(root, counter);
    }

    /**
     * Recursive method to generate a copy of a binary tree
     * with values indicating the preorder traversal order.
     *
     * @param root
     *        the root of the tree to copy
     * @param counter
     *        an array containing the traversal order counter as its
     *        first element. On entry, it should contain the value to
     *        use for the root of the generated (sub)tree. On return,
     *        it will contain one more than the last value used.
     */
    private static BinaryTree generate(BinaryTree root, int[] counter) {
        // recursion base case
        if (root == null) {
            return null;
        }

        // capture current value and increment the counter
        int value = counter[0];
        ++counter[0];

        // generate left subtree - this will change the counter unless
        // the left subtree is null
        BinaryTree left = generate(root.left, counter);

        // generate right subtree - may change the counter
        BinaryTree right = generate(root.right, counter);

        // Complete the copy by generating the root node;
        // return the result
        return new BinaryTree(value, left, right);
    }
}
于 2013-07-30T00:46:01.860 に答える
0

サンプル ツリーの場合、コードは次のようなものを返します。

      1
    /   \
   2     3
 /  \
3    4

もしそうなら、あなたは正しい軌道に乗っており、おそらく再帰を使用して事前にノードを訪問することを理解していますが、int が値型であることを忘れている可能性があります! 私は思う...私のJavaは錆びています。とにかく、参照によってintを渡すことができ、問題が私が思うものであれば、あなたは良いはずです。簡単なGoogle検索から、「変更可能なint」を作成する簡単な方法は、Ted Hoppが提案した（int [1]）のように単一のセルでラップするか、MutableIntを使用できるようです（回答のフルパス：Java：最善の方法int を参照渡しします)。

于 2013-07-30T03:16:18.017 に答える