알고리즘 – 이진 트리 (Python)

이진 트리(Binary Tree) 란?

트리란 부모와 자식이 상하 구조로 나뉘어진 그래프입니다.
이진 트리는 트리의 종류 중 하나이며 자식 노드를 왼쪽과 오른쪽에 하나씩 배치할 수 있는 형태의 그래프입니다.

• 탐색 방식 종류
  • 전위 순회
  • 후위 순회
  • 중위 순회
  • 층별 순회

• 전위 순회
  • (루트) -> (왼쪽 자식 노트) -> (오른쪽 자식 노드) 순 탐색
  • 탐색 순서 A – B – D – C – E – F – G
  • 전위 순회 예시 코드

# python code
def preOrder(cur):
    if cur == ".":
        return 0

    print(cur,end="")
    preOrder(graph[cur][0])
    preOrder(graph[cur][1])

• 후위 순회
  • (왼쪽 자식 노트) -> (오른쪽 자식 노드) -> (루트) 순 탐색
  • 탐색 순서 D – B – E – G – F – C – A
  • 후위 순회 예시 코드

# python code
def postOrder(cur):
    if cur == ".":
        return 0

    postOrder(graph[cur][0])
    postOrder(graph[cur][1])
    print(cur,end="")

• 중위 순회
  • (왼쪽 자식 노트) -> (오른쪽 자식 노드) -> (루트) 순 탐색
  • 탐색 순서 D – B – A – E – C – F – G
  • 중위 순회 예시 코드

# python code
def inOrder(cur):
    if cur == ".":
        return 0

    inOrder(graph[cur][0])
    print(cur,end="")
    inOrder(graph[cur][1])

• 층별 순회
  • 부모 노드 층에서 자식 노드 층으로 순차적 탐색 방식 (BFS 탐색 방식)
  • 탐색 순서 A – B – C – D – E – F – G