5639_이진검색트리

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

 

 

 

자 이번에는 이진검색트리이다. 

 

이진검색트리는 루트 노드가 왼쪽노드보다는 무조건 크고, 오른쪽 노드보다는 무조건 작은 수가 들어있는 트리이다.

 

결국 전위탐색이던 중위탐색이던 후위탐색이던 다른 탐색으로 찾으려면 왼쪽노드와 오른쪽 노드가 갈라지는 경계점과 루트노드를 찾아야 한다.

 

전위탐색으로 시작을 했으므로 값을 담아둔 해당 리스트에서 가장 앞의 값이 루트노드일 것이고, 해당 노드의 값보다 더 커지는 값이 나오는 순간이 왼쪽과 오른쪽 트리를 나누는 구분점일 것이다.

 

그렇다면 루트노드를 뺀 시작점 ~ 1 부터 왼쪽노드로 갈라지는 경계점 은 왼쪽트리의 시작과 끝,

오른쪽노드로 갈라지는 경계점 ~ 검색하는 범위의 끝이 오른쪽 트리가 될 것이다.

당연히 루트노드는 검색하는 범위의 시작점이 될 것이다.

 

이를 구현하면 아래처럼 구현할 수 있다.

 

import sys
sys.setrecursionlimit(10**5)
preorder = []
while True:
    try:
        preorder.append(int(input()))
    except:
        break

def postorder(start,end):

    if start>end:
        return
    div = end + 1

    for i in range(start,end+1):
        if preorder[start] < preorder[i]:
            div=i
            break

    postorder(start+1,div-1)
    postorder(div,end)
    print(preorder[start])

postorder(0,len(preorder)-1)

재밌는건 여기서 print를 왼쪽노드와 오른쪽 사이로 옮기면 중위탐색을 하는것이 된다!