자바 : 배열 우선 순회 검색

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); 
} 

이 추가 메모리 오버 헤드없이 할 수있는, 또는 스택, 벡터 또는 대기열에 항목을 저장해야합니까? 그렇다면 어떻게하면 2 진 트리보다 메모리가 적게 듭니까?

Answer 1

나는이 특히 효과적이다 모르겠지만, 하나 개의 가능한 솔루션은 bstIterate 방법에 깊이 매개 변수를 전달하고 반복적으로 호출하는 것입니다 : O(n) 복잡성 작업 (쉽게 자바로 변환 할 수 있기를 바랍니다) 더 이상 결과를 반환하지 않을 때까지 깊이가 증가합니다. 이 같은

뭔가 :

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++; 

이 배열을 감안할 때 :

   13 
     4     25 
    3  9   23 30 
1  7   18 

:이 나무를 생산

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

17,451,515,

이 출력 :

13 
4 
25 
3 
9 
23 
30 
1 
7 
18 

당신이 생각했던 무엇인가요?

Answer 2

sortedArrayToBST 메서드가 지정된 배열에서 균형 이진 트리를 작성하기를 바랍니다. 이 경우 구현하려는 메소드는 BST에 대한 DFS (Depth first search) 반복을 모방합니다. 그러나 구현이 버그는 올바른 구현은 다음과 같이 것입니다 :

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++ 구현을 썼다

#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; 
}