입증 또는 반증 : 이진 검색 트리를 미리 주문하면 이진 검색 트리

Question

을 고유하게 결정할 수 있습니다. 이전 테스트에서 찾은 작업이므로 비슷한 질문을 할 수 있기 때문에 해결하려고 시도합니다. 금요일에.

해결책으로는 값싼 솔루션이 있지만 이진 검색 트리의 정의가 중요하다고 생각합니다. .. 같은 요소 때문에 여기

1 
\ 
    1 
    \ 
    1 

하고 당신이 사전 주문 통과하면 두 나무에 대한 동일한 출력을 할 두 번째 트리

1 
/
    1 
/
1 

, 둘 다 있습니다

은 내가 먼저 트리 만들기 퇴화 된 나무. 하지만 당신은 같은 나무가 없습니다! 그래서 진술은 거짓입니다.

내 트리 바이너리 검색 트리 만 문제입니다 ... 이진 검색 트리 요소가 더 크거나 같은 요소를 가질 수 있으므로 예라고 생각하십니까?

방학이 끝났을 때,하지만 휴가가 끝나면, 물어볼 수 있다고 선생님에게 물었을 때 멈춰주세요. 시험이 끝났습니다 .... 나에게 좋은 점은 없습니다.

Answer 1

귀하의 답변은 BST의 표준 정의에서 볼 때 완벽합니다. 표준 정의에 따라 BST는 반복되는 요소를 가질 수 있고 동일한 요소는 하위 트리에 포함될 수 있습니다.

중복이 없거나 왼쪽 (또는 오른쪽 만) 하위 트리에만 중복이 있어야하는 경우 질문을하는 경우 트리를 재구성하기 위해 선결제 순회로 충분합니다.

중복이 허용되지 않는 경우 다음과 같이 반복적으로 트리를 구성합니다. 루트를 첫 번째 노드로 만든 다음 원래 트래버스의 부분보다 적은 수의 노드를 사용하여 반복적으로 왼쪽 및 오른쪽 하위 트리를 만듭니다 (왼쪽 하위 트리)와 루트 노드보다 큼 (오른쪽 하위 트리의 경우)입니다. 중복이 허용되지만 왼쪽 또는 오른쪽 하위 트리에 제약이있는 경우 동일한 절차를 사용하지만 작거나 같음을 모두 또는 둘 이상에 추가하지 마십시오.