트리 내역의 순회를 사용하여 BST 또는 힙이 있는지 여부를 결정합니다.

Question

이 순서대로 목록을 감안할 때 :
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17

해당 목록 중 하나가 유효한 BST / MIN 또는 MAX 힙을 나타내는지 여부를 확인해야합니다. 나는 이것에 접근하는 방법을 알아 두려고했지만, 무력적으로 무력을 강제하는 것 외에도, 이것을 해결할 수있는 "똑똑한"방법을 알 수 없었습니다.

어떤 지표를 사용할 수 있습니까? 또는 해결 방법을 사용할 수있는 방법은 문자 그대로 모든 옵션을 강요하는 것입니다.

Answer 1

그 중 누구도 BST 일 수 없습니다.BST의 순서대로가 키가 없음으로 정점을 방문합니다 (이것은 유도에 의해 증명하기 쉽기 때문에).

힙이 있는지 여부를 결정하려면 목록의 토폴로지를 이미 알고있는 목록의 요소 수가 이미 있음을 알 수 있습니다 (힙은 일대일 수준까지 완전히 이진된 나무가 완전히 이진이며,마지막 레벨은 왼쪽에 포장됩니다.)그런 다음 운동은 주어진 키를 동일한 순서로 쓰고 힙 속성이 보유하고 있는지 확인하기 위해 주어진 키를 기록하는 것입니다.

특정 예제에서 첫 번째 시퀀스는 결과 트리가 키 $ 23, 1, 53 $ 키가있는 경로가 있기 때문에 힙의 순서 순위가 될 수 없습니다.(깊이의 순서가 증가 함). 동일한 인수는 키 $ 71, 32, 49 $ 의 경로에 대한 두 번째 시퀀스에 적용됩니다.