Java:数组上的广度优先遍历顺序

Question

如果我将数组放入二叉树并对其执行 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);
}

这可以在没有额外内存开销的情况下完成吗？或者我是否必须将项目存储在堆栈、 vector 或队列中？如果是这样，它如何以及是否需要比二叉树更少的内存？

Answer 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

你就是这么想的吗？