이진트리 순회(깊이우선탐색)

완전탐색 (백트랙킹, 상태트리와 CUT EDGE)-DFS(깊이우선탐색)기초

문제 ✏️

이진트리 순회(깊이우선탐색)

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

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

코드 💻

'''
전위순회 : 자기자신(부모)을 먼저 출력 -> 왼쪽, 오른쪽 자식으로 이동
중위순회 : 왼쪽 자식 -> 부모 -> 오른쪽 자식
후위순회 : 왼쪽 자식 -> 오른쪽 자식 -> 부모

부모가 D(1)이라면,
왼쪽 자식은 D(1*2), 오른쪽 자식은(D*2+1)

대부분의 방식은 전위순회이나, 병합정렬에서는 후위순회 쓰임
'''
import sys

def DFS(v):         # 깊이 : v
    if v > 7:
        return
    else:
        print(v, end = " ")     # 전위순회
        DFS(v*2)                # 왼쪽 자식 노드
        print(v, end = " ")     # 중위순회
        DFS(v*2+1)              # 오른쪽 자식 노드
        print(v, end = " ")     # 후위순회 

if __name__ == "__main__":
    DFS(1)

참고

• 인프런 : 파이썬 알고리즘 문제 풀이