[Python] 이진트리 순회

오늘은 DFS를 이용하여 이진트리를 순회하는 대표적인 3가지 방법을 구현하고 경로를 출력해보겠습니다.

순회의 종류

순회에는 전위순회, 중위순회, 그리고 후위순회가 있습니다.

전위순회는 부모(자기자신) → 왼쪽자식 → 오른쪽자식
중위순회는 왼쪽자식 → 부모(자기자신) → 오른쪽자식
후위순회는 왼쪽자식 → 오른쪽자식 → 부모(자기자신)
입니다.

보통 전위순회를 많이 사용하고, 후위순회는 병합정렬(합병정렬, merge sort) 때 사용합니다.

접근 방법

위와 같은 이진트리가 있을 때, 각 순회 방법에 따른 경로는 다음과 같습니다.

전위순회 : 1 2 4 5 3 6 7
중위순회 : 4 2 5 1 6 3 7
후위순회 : 4 5 2 6 7 3 1

후위순휘를 예로 들어 설명해보겠습니다.

1. 1로 처음 들어왔지만, 왼쪽자식으로 가야 하니 2로 갑니다.
2. 2로 들어왔지만, 왼쪽자식으로 가야 하니 4로 갑니다.
3. 4로 들어왔는데, 4가 가장 마지막 노드이므로 4를 출력합니다.
4. 2로 복귀하지만, 오른쪽자식으로 가야하니 5로 갑니다.
5. 5로 들어왔는데, 5가 가장 마지막 노드이므로 5를 출력합니다.
6. 2로 복귀했는데, 2가 가장 마지막 노드(=자식 노드는 이미 다 출력함)이므로 2를 출력합니다.
   (이하 반복)

부모 자식을 DFS(v)라 하면, 왼쪽 자식은 DFS(v+1), 오른쪽 자식은 DFS(v*2+1)가 되겠죠? 각각의 순회방법을 코드를 짜면 아래와 같습니다.

def DFS_1(v): #전위순회
    if v>7:
        return
    else:
        print(v,end=' ') #부모, 자기자신
        DFS_1(v*2) #왼쪽자식
        DFS_1(v*2+1) #오른쪽 자식

def DFS_2(v): #중위순회
    if v>7:
        return
    else:
        DFS_2(v*2) #왼쪽자식
        print(v,end=' ') #부모, 자기자신
        DFS_2(v*2+1) #오른쪽 자식

def DFS_3(v): #후위순회
    if v>7:
        return
    else:
        DFS_2(v*2) #왼쪽자식
        DFS_2(v*2+1) #오른쪽 자식
        print(v,end=' ') #부모, 자기자신


if __name__=="__main__":
    print("전위순회 : 부모 -> 왼쪽자식 -> 오른쪽자식")    
    DFS_1(1)
    print()
    print("중위순회 : 왼쪽자식 -> 부모 -> 오른쪽자식")
    DFS_2(1)
    print()
    print("후위순회 : 왼쪽자식 -> 오른쪽자식 -> 부모")
    DFS_3(1)

오늘의 게시글 끝!