주어진 배열이 있고 그것이 BST의 순차적 순회를 나타내는 지 알아야합니다. (예 : 질문이 순서가 아닌 순서로 된 경우 배열의 시간이 o (n)으로 정렬되어 있는지 확인하기 만하면됩니다.주어진 배열이 이진 검색 트리의 후행 순회를 나타내는 지 확인하는 방법?
2
A
답변
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;
}
흥미로운 숙제 문제 같은데. 그것을 해결하려는 시도에서 무엇을 생각해 냈습니까? –
거의 * 무엇이든 나타낼 수 있습니다 (예 : 엄마가 가장 좋아하는 복권 번호) ... 질문을 명확히하십시오. –
@KarolyHorvath "OP"는 기본적으로 OP가 "있는 것"이라고 생각합니다. 바이너리 검색 트리에서 시작하여 순차 정렬 (post-order traversal)을하고 어레이의 요소를 방문한 순서대로 노드의 값으로 채워 어레이를 얻을 수 있습니까? 나는 그 질문이 충분히 명확하다고 생각하지만 연구 노력을 보이지 않는다. –