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

我不确定这是否特别有效，但一种可能的解决方案是将深度参数传递给您的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 回答
2

我希望你的sortedArrayToBST方法是从给定的数组构建一个平衡的二叉树。在这种情况下，您尝试实现的方法将模拟 BST 上的 DFS（深度优先搜索）迭代。但是您的实现是错误的，正确的实现将如下所示：

void bstIterate(int[] array, int start, int end) {
  if (start > end) return;
  int mid = start + (end - start) / 2; //it should not be array.lenght/2 because we are not updating the array at any point

  bstIterate(array, start, mid-1); // mid is already printed so we no longer need it
  bstIterate(array, mid+1, end);
}

//Now Call the method from you main
bstIterate(array, 0, array.length-1); //it should be array.length-1, as it is the last index of last element of the array

但是从问题标题中，我了解到您正在通过将数组假设为平衡二叉树来寻找对排序数组的 BFS 遍历。

假设我们的排序数组是 {1, 2, 3, 4, 5, 6, 7}。在这种情况下，平衡的 BST 将如下所示：

    4
   / \
  2   6
 / \ / \
1  3 5  7

上面树上的 BFS 遍历应该输出如下： 4 2 6 1 3 5 7 我为此编写了一个快速的 C++ 实现，它将完成O(n)复杂的工作（希望您可以轻松地将其转换为 java）：

#include <stdio.h>
#include <queue>
using namespace std;
class Node {
public:
    int start;
    int end;
};

void BFSiterate(int *arr, int start, int end) {
    queue<Node>que;
    Node n;
    n.start = start;
    n.end = end;
    que.push(n);

    while(!que.empty()) {
        n = que.front();
        que.pop();
        int mid = n.start + (n.end - n.start) / 2;
        printf("%d\n", arr[mid]);
        Node x;
        x.start = n.start;
        x.end = mid-1;
        if (x.start<=x.end)
            que.push(x); //left

        x.start = mid+1;
        x.end = n.end;
        if (x.start<=x.end)
            que.push(x); //right
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int len = sizeof(arr)/4;
    BFSiterate(arr, 0, len-1);
    return 0;
}
于 2013-05-27T07:44:15.803 回答