2

주어진 배열이 있고 그것이 BST의 순차적 순회를 나타내는 지 알아야합니다. (예 : 질문이 순서가 아닌 순서로 된 경우 배열의 시간이 o (n)으로 정렬되어 있는지 확인하기 만하면됩니다.주어진 배열이 이진 검색 트리의 후행 순회를 나타내는 지 확인하는 방법?

+0

흥미로운 숙제 문제 같은데. 그것을 해결하려는 시도에서 무엇을 생각해 냈습니까? –

+0

거의 * 무엇이든 나타낼 수 있습니다 (예 : 엄마가 가장 좋아하는 복권 번호) ... 질문을 명확히하십시오. –

+0

@KarolyHorvath "OP"는 기본적으로 OP가 "있는 것"이라고 생각합니다. 바이너리 검색 트리에서 시작하여 순차 정렬 (post-order traversal)을하고 어레이의 요소를 방문한 순서대로 노드의 값으로 채워 어레이를 얻을 수 있습니까? 나는 그 질문이 충분히 명확하다고 생각하지만 연구 노력을 보이지 않는다. –

답변

0

빠른 정당성 검사 : 배열의 마지막 항목이 아닌 경우 루트 노드는 post-order traversal의 결과가 아닙니다. 마찬가지로 선주문 탐색이 수행 된 경우 배열의 첫 번째 항목이 루트입니다.

0

후행 탐색은 {LEFT Subtree} {Right Subtree} {ROOT}에 의해 수행됩니다. 따라서 여기에서 아이디어는 오른쪽 끝에서 배열을 횡단하기 시작하는 것입니다. 배열의 마지막 요소는 루트이고, 오른쪽에서 왼쪽으로 작은 요소를 만나면 왼쪽 하위 트리로 시작하도록 경계를 표시하고 BST에는이 인덱스의 더 큰 요소가 없습니다. 이것은 각 하위 트리에 적용됩니다 . C++의 알고리즘은 다음과 같이 간다 -

bool isBST(int arr[], int n){ 

//Set root to the max integer value. 
int root = INT_MAX; 

//Stack used to keep track of current subtree 
std::stack<int>s; 

//Start at the end of the array because Postorder traversal is 
// <L><R><D> 
for (int i = n-1; i>=0; i--) { 
    //False if any larger number in the left subtree 
    if (arr[i]> root) { 
     return false; 
    } 

    //Reset the root for boundary of every subtree, 
    //when current item is smaller than top, 
    //that means we are starting with left subtree of this root 
    while (!s.empty() && arr[i] < s.top()) { 
     root = s.top(); 
     s.pop(); 
    } 
    //Keep pushing the elements otherwise 
    s.push(arr[i]); 
    } 
    return true; 

}