2

並べ替えられた配列を、配列をバイナリ ツリーに入れて BFT を実行した場合に幅優先トラバーサルが与える順序で反復処理したいと考えています (これが現在の方法です)。バイナリ ツリーに配列を再度構築して格納する必要があるため、明らかにこれには追加のメモリ オーバーヘッドが伴います。これは二分探索に似ているはずですが、正しい順序付けができません。

私が現在これを達成する方法は次のとおりです。

BTree bst = sortedArrayToBST(array);
Queue<BTree> queue = new LinkedList<BTree>();
queue.add(bst);
while(!queue.isEmpty()) {
    BTree node = queue.remove();
    System.out.println(node.data);
    if(node.left != null) queue.add(node.left);
    if(node.right != null) queue.add(node.right);
}

これが私が現在持っているものです（ただし、これは明らかに間違った順序になります）：

public void bstIterate(int[] array, int start, int end) {
    if(array.length == 0) return;
    int med = array.length /2;
    System.out.println(array[med]);
    bstIterate(array,start,mid);
    bstIterate(array,mid+1,array.length);
}

これは追加のメモリ オーバーヘッドなしで実行できますか、またはアイテムをスタック、ベクトル、またはキューに格納する必要がありますか?もしそうなら、バイナリ ツリーよりも少ないメモリしか必要としませんか?

4

2 に答える 2

2

これが特に効率的かどうかはわかりませんが、考えられる解決策の 1 つは、深さパラメーターをbstIterateメソッドに渡し、結果が返されなくなるまで深さを増やしながら繰り返し呼び出すことです。

このようなもの：

public static boolean bstIterate(int array[], int start, int end, int depth) {
  if (end <= start)
    return false;
  else {
    int mid = start + (end-start)/2;
    if (depth == 0) {
      System.out.println(array[mid]);
      return true;
    }
    else {
      boolean res1 = bstIterate(array, start, mid, depth-1);
      boolean res2 = bstIterate(array, mid+1, end, depth-1);
      return res1 || res2;
    }
  }
}

次のように呼び出します。

int depth = 0;
while (bstIterate(array, 0, array.length, depth))
  depth++;

この配列を考えると：

int array[] = {1, 3, 4, 7, 9, 13, 18, 23, 25, 30};

このツリーを生成します：

                13
       4                 25
   3       9          23    30
1       7          18

そしてこの出力：

13
4
25
3
9
23
30
1
7
18

それはあなたが念頭に置いていたことですか？

于 2013-05-27T08:01:02.847 に答える