트리 이론 기본편 -중위 순회의 특징 응용하기-

1. 이진 탐색 트리의 특징

 

이진 탐색 트리는 어떠한 경우에도 왼쪽 서브 트리의 루트 < 현재 루트 노드 < 오른쪽 서브 트리의 루트을 만족한다.

 

만약에 트리의 노드들이 완전 이진 트리 형태로 주어질때, 이런 규칙을 만족하도록 값을 넣고 싶다면

 

어떻게 넣을 수 있을까?

 

 

2. 중위순회의 특징(inorder traversal)

 

완전 이진 트리를 중위순회하면 왼쪽 서브트리 > 루트 > 오른쪽 서브트리 순서대로 순회를 하게 된다.

 

그렇다면 주어진 이진 트리의 노드를 중위순회한다면, 

 

트리에 넣어야할 데이터의 순서가 주어지며

 

그러한 순서대로 데이터를 작은 값부터 넣으면 "왼쪽 서브 트리의 루트 < 현재 루트 노드 < 오른쪽 서브 트리"을 반드시 만족시킬 수 있다

 

 

위 그림과 같이 1 > 2 > 3 > 4 > 5 > 6 > 7 순서대로 어떤 데이터를 넣는다면(파란색은 노드 번호)

 

이진 탐색 트리의 조건을 만족하는 완전 이진 트리가 된다

 

 

3. 구현 예시

 

#중위순회
def inorder(v):
    
    global i
    
    if v <= n:
        
        inorder(2*v)
        tree[v] = data_list[i]  #v번 노드에 i번째 데이터를 넣는다
        i += 1 #다음 데이터를 넣기 위해 증가시키고
        inorder(2*v+1)

n = 10 # 노드의 총 개수

tree = [0] * (n+1) #완전이진트리

data_list = [4,2,8,6,9,5,10,11,3,7] #트리 노드에 넣을 값

data_list.sort() #작은 값부터 넣기 위해 오름차순 정렬

i = 0

inorder(1)

print(tree)
[0, 8, 5, 10, 3, 7, 9, 11, 2, 4, 6]

 

완성된 트리를 그려보면 실제로 "왼쪽 서브 트리의 루트 < 현재 루트 노드 < 오른쪽 서브 트리"의 조건을 만족시킨다.

 

 

4. 연습문제

 

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

5. 풀이

 

중위순회한 순서대로 데이터를 넣으면 된다

 

중위순회한 순서가 order_list에 들어가고, 그 값의 index+1이 그 노드번호에 저장된 값이 될 것이다.

 

n//2번 노드에 저장된 값을 찾고 싶다면, i를 1번부터 n번까지 순회하여

 

order_list[i-1] == n//2가 되는 i를 찾으면 될 것이다.

 

def inorder(v):
    
    if v <= n:
        
        inorder(2*v)
        order_list.append(v)
        inorder(2*v+1)

T = int(input())

for t in range(1,T+1):
    
    n = int(input())

    tree = [0]*(n+1)

    order_list = []

    inorder(1)

    ans = [0,0]

    for i in range(1,n+1):
        
        if order_list[i-1] == n//2:

            ans[1] = i
        
        if order_list[i-1] == 1:
            
            ans[0] = i

    print('#'+str(t),*ans)