[김태원 알고리즘] 이진트리 순회 (깊이우선탐색)

사용 언어: Python3

문제

이진트리 순회 개념

• 종류
  • 전위 순회
    • 부모 -> 왼쪽 -> 오른쪽
    • 자식들 호출하기 전에 자기 본연의 일(여기서는 print())을 먼저 처리
  • 중위 순회
    • 왼쪽 -> 부모 -> 오른쪽
  • 후위 순회
    • 왼쪽 -> 오른쪽 -> 부모
• 대부분 전위순회가 많이 쓰인다.
  • “병합 정렬”은 후위순회를 사용해야 한다.
  • 중위순회는 잘 쓰이지 않는다.

풀이

def DFS(v): # v: vertex
    if v > 7:
        return
    else:
        print(v, end = ' ') # 전위순회 (부 -> 왼 -> 오)
        DFS(v*2) # 왼쪽 자식 호출
        # print(v, end = ' ') # 중위순회 (왼 -> 부 -> 오)
        DFS(v*2+1) # 오른쪽 자식 호출
        # print(v, end = ' ') # 후위순회 (왼 -> 오 -> 부)

DFS(1)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기