1 
 root = new TreeNode(N);
 constructTree(N, root);

 private void constructTree(int N, TreeNode node) {
    if (N > 0) {
        node.setLeft(new TreeNode(N-1));
        constructTree(N-1, node.getLeft());
    }
    if (N > 1) {
        node.setMiddle(new TreeNode(N-2));
        constructTree(N-2, node.getMiddle());
    }
    if (N > 2) {
        node.setRight(new TreeNode(N-3));
        constructTree(N-3, node.getRight());
    }

N がルート番号であると仮定すると、3 つは N-1、N-2、N-3 の左中右ノードを作成します。

元：

     5
   / | \
  4  3  2
 /|\
3 2 1

等

私の TreeNode クラスには次の変数があります。

private int number;
private TreeNode left, middle, right;

28 より大きい整数でツリーを構築するたびに、OutOfMemoryError が発生します。私の再帰的方法は信じられないほど非効率的ですか、それともこれは自然なことですか? ありがとう！

4

1 に答える 1

2

理論的には、深さ N の完全な三分木には(3^(N+1) - 1) / 2ノードがあります。N が 28 の場合、34,315,188,682,441 ノードです。各ノードが何らかの理由で 1 バイトしか使用しなかったとしても、それでも 31.2 テラバイトの RAM です。その前にメモリ不足になります。

編集:ただし、コードは完全なツリーを生成するようには見えません。次のプログラムを実行して、新しいノードの数をカウントしたとき:

static long nodes = 0;

static void constructTree(int N) {
   if (N > 0) {
       ++nodes;
       constructTree(N-1);
   }
   if (N > 1) {
       ++nodes;
       constructTree(N-2);
   }
   if (N > 2) {
       ++nodes;
       constructTree(N-3);
   }
}

public static final void main (String[] args) throws Exception {
    nodes = 1;
    constructTree(28);
    System.out.println(nodes);
}

コンストラクTreeNodeターが新しいノードを作成しないと仮定すると、N=28 で 34,850,335 個の新しいノードを作成し、N=29 で 64,099,760 個の新しいノードを作成していることがわかります。N=28 が成功することを暗示していることを考えると、これはより理にかなっています。表示されていないため、TreeNode使用するメモリの量を正確に知ることはできませんが、これらの数値は、通常の JVM メモリ制限と同じ桁数に収まります。最大 JVM メモリを少し増やして、さらに 1 つまたは 2 つのレベルを絞り出すことができます。

ただし、なぜこのツリーを生成するのかを正確に考えて、自分がしていることを行うための別のアルゴリズムを考え出すことをお勧めします。

于 2013-11-04T03:41:00.013 に答える